类似lisp语法的递归解析

Question

我试图解析以下格式的行:

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

其中OP是逻辑门(AND, OR, NOT)的符号，something是我想要评估的东西。

我寻找的输出类似于:

{ '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']}]}]