рекурсивного синтаксического анализа для сюсюкать как синтаксис

Question

им пытаются разобрать строки в виде:

(OP something something (OP something something)) (OP something something) 

Где OP является символом для логического ворот (AND, OR, NOT) и что-то есть, что я хочу, чтобы оценить ,

Выход им ищет что-то вроде:

{ 'OPERATOR': [condition1, condition2, .. , conditionN] } 

Если само условие может быть сама по себе (вложенные условия) ДИКТ/список пар. До сих пор я пытался что-то вроде:

 tree = dict() 
     cond = list() 
     tree[OP] = cond 


    for string in conditions: 
     self.counter += 1 
     if string.startswith('('): 
      try: 
       OP = string[1] 
      except IndexError: 
       OP = 'AND' 
      finally: 
       if OP == '?': 
        OP = 'OR' 
       elif OP == '!': 
        OP = 'N' 

      # Recurse 
      cond.append(self.parse_conditions(conditions[self.counter:], OP)) 
      break 

     elif not string.endswith(")"): 
      cond.append(string) 

     else: 
      return tree 

    return tree 

Я попробовал другие способы как хорошо, но я просто не могу обернуть мою голову вокруг этого вся рекурсии вещь так что им интересно, если я мог бы получить некоторые указатели здесь, я посмотрел вокруг сети и Я нашел кое-что о рекурсивном синтаксическом анализе спуска, но все учебники пытались сделать что-то более сложное, чем нужно.

PS: Я понимаю, что могу сделать это с существующими библиотеками python, но что бы я узнал, выполнив это?

Answer 1

Я отправляю это без дальнейших комментариев, для учебных целей (в реальной жизни, пожалуйста, используйте библиотеку). Обратите внимание, что проверка ошибок (домашняя работа для вас!)

Не стесняйтесь спросить, есть ли что-то, что вы не понимаете.

# PART 1. The Lexer 

symbols = None 

def read(input): 
    global symbols 
    import re 
    symbols = re.findall(r'\w+|[()]', input) 

def getsym(): 
    global symbols 
    return symbols[0] if symbols else None 

def popsym(): 
    global symbols 
    return symbols.pop(0) 

# PART 2. The Parser 
# Built upon the following grammar: 
# 
#  program = expr* 
#  expr = '(' func args ')' 
#  func = AND|OR|NOT 
#  args = arg* 
#  arg  = string|expr 
#  string = [a..z] 

def program(): 
    r = [] 
    while getsym(): 
     r.append(expr()) 
    return r 

def expr(): 
    popsym() # (
    f = func() 
    a = args() 
    popsym() #) 
    return {f: a} 

def func(): 
    return popsym() 

def args(): 
    r = [] 
    while getsym() != ')': 
     r.append(arg()) 
    return r 

def arg(): 
    if getsym() == '(': 
     return expr() 
    return string() 

def string(): 
    return popsym() 

# TEST = Lexer + Parser 

def parse(input): 
    read(input) 
    return program() 

print parse('(AND a b (OR c d)) (NOT foo) (AND (OR x y))') 
# [{'AND': ['a', 'b', {'OR': ['c', 'd']}]}, {'NOT': ['foo']}, {'AND': [{'OR': ['x', 'y']}]}]