python - 使 while 解析函数递归

Question

我有一个解析 lisp 表达式的基本函数。它使用 while 循环，但作为练习，我想将其转换为递归函数。但是，这对我来说有点棘手。这是我到目前为止所拥有的:

def build_ast(self, tokens=None):
    # next two lines example input to make self-contained
    LEFT_PAREN, RIGHT_PAREN = '(', ')'
    tokens = ['(', '+', '2', '(', '*', '3', '4', ')', ')']
    while RIGHT_PAREN in tokens:
        right_idx = tokens.index(RIGHT_PAREN)
        left_idx = right_idx - tokens[:right_idx][::-1].index(LEFT_PAREN)-1
        extraction = [tokens[left_idx+1:right_idx],]
        tokens = tokens[:left_idx] + extraction + tokens[right_idx+1:]
    ast = tokens
    return ast

所以它会解析这样的东西:

(+ 2 (* 3 4))

进入这个:

[['+', '2', ['*', '3', '4']]]

如何使上述函数递归的示例是什么？到目前为止，我已经开始使用类似的东西:

def build_ast(self, ast=None):
    if ast is None: ast=self.lexed_tokens
    if RIGHT_PAREN not in ast:
        return ast
    else:
        right_idx = ast.index(RIGHT_PAREN)
        left_idx = right_idx - ast[:right_idx][::-1].index(LEFT_PAREN)-1
        ast = ast[:left_idx] + [ast[left_idx+1:right_idx],] + ast[right_idx+1:]
        return self.build_ast(ast)

但它给人的感觉有点奇怪(好像递归在这里没有帮助)。构建它的更好方法是什么？或者也许是更好/更优雅的算法来构建这个简单的 ast？

Answer 1

您可以使用递归生成器函数:

def _build_ast(tokens):
   LEFT_PAREN, RIGHT_PAREN = '(', ')'
   #consume the iterator until it is empty or a right paren occurs
   while (n:=next(tokens, None)) is not None and n != RIGHT_PAREN:
      #recursively call _build_ast if we encounter a left paren
      yield n if n != LEFT_PAREN else list(_build_ast(tokens))
   

def build_ast(tokens):
   #pass tokens as an iterator to _build_ast
   return list(_build_ast(iter(tokens)))

tokens = ['(', '+', '2', '(', '*', '3', '4', ')', ')']
print(build_ast(tokens))

输出:

[['+', '2', ['*', '3', '4']]]