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？

标签： pythonalgorithmparsingabstract-syntax-tree

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