Python 简单解析树解释器

Question

您好，我有一个函数 parse()，它接受一个运算符列表和操作数(例如 ['+', '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() 来制作上面的树？

Answer 1

当您将 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。