Python 简单解析树解释器

嗨，我有一个函数 parse()，它接受运算符和操作数(ex ['+', '20', '10'])标记的列表和索引 i，并从中构造一棵树。当找到一个操作符(一个带有 .left 和 .right 的节点)时，函数会停止运行，直到它到达一个文字(一个数字)或一个字母变量。问题是当左侧的递归完成并且函数移到右侧时，我希望在递归中更改的索引 i 保持修改。例如，要从 [-,//, y, 2, x] 获取这棵树:

我写过这个:

def parse(tokens, i):
    """parse: tuple(String) * int -> (Node, int)
    From an infix stream of tokens, and the current index into the
    token stream, construct and return the tree, as a collection of Nodes,
    that represent the expression."""

    if tokens[i].isdigit():
        return mkLiteralNode(tokens[i])

    elif tokens[i] == "+":
        return mkAddNode(parse( tokens, i + 1 ), parse( tokens, i + 2 )) # first argument is the node.left, second is the node.right
    elif tokens[i] == "-":
        return mkSubtractNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))
    elif tokens[i] == "*":
        return mkMultiplyNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))
    elif tokens[i] == "//":
        return mkDivideNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))

    else:
        return mkVariableNode(tokens[i])

当创建 SubtractNode 时，i 为 0，然后正常递增，但是当左侧完成时，i 再次为 0 并且 parse(tokens, i + 2) 指向 y 而不是 x，如下所示:

如何在 token 中不使用 pop() 的情况下制作上述树？

最佳答案

编写这样的东西要容易得多，当您将 tokens 列表视为一个对象时，它本身负责存储其位置。这就是为什么通常 tokens 应该来自 Lexer，它通常只有一种方法: next_token 。我们将用迭代器模拟这个:

def parse(tokens):
    """parse: tokens_iter or generator -> Node
    From an infix stream of tokens, and the current index into the
    token stream, construct and return the tree, as a collection of Nodes,
    that represent the expression."""

    next_tok = next(tokens)

    if next_tok.isdigit():
        return ('literal', next_tok)

    elif next_tok == "+":
        return ('add', parse( tokens ), parse( tokens )) # first argument is the node.left, second is the node.right
    elif next_tok == "-":
        return ('sub', parse( tokens ), parse( tokens ))
    elif next_tok == "*":
        return ('mul', parse( tokens ), parse( tokens ))
    elif next_tok == "//":
        return ('div', parse( tokens ), parse( tokens ))

    else:
        return ('variable', next_tok )

# And, example:
print(parse(iter(['-', '//', 'y', '2', 'x'])))

这将打印:

('sub', ('div', ('variable', 'y'), ('literal', '2')), ('variable', 'x'))

您还需要处理 StopIteration 异常，并将其转换为有意义的 ParseError 。

关于Python 简单解析树解释器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20086381/