在 LL(1) 解析过程中如何构造解析树？

Question

我想知道是否有一种方法可以在 LL(1) 解析期间构造解析树。我已经尝试了好几天，但一直找不到解决方案。 This 问题类似，但没有提供足够的实现细节，而且是针对 AST，而不是解析树。

详情：

我正在使用堆栈

Answer 1

我会这样做：

示例语法：

statement -> number
statement -> '(' statement '+' statement ')'
number-> 'n'

结果为：

RULES = [
    ["number"],
    ['(', "statement", '+', "statement", ')'],
    ['n'],
]

执行ll解析： "((n+n)+n)" -> ll -> [1,1,0,2,0,2,0,2] 您将获得已执行规则的列表

现在你可以造一棵树了

def tree(input, ll_output):
    rule = ll_output.pop(0)
    tokens = []
    for item in RULES[rule]:
        if len(item) > 1: tokens.append(tree(input, ll_output))
        else: tokens.append(input.pop(0))
    return tokens

input = ['(','(','n','+','n',')','+','n',')'] # "((n+n)+n)"
ll_output = [1,1,0,2,0,2,0,2]
tree(input, ll_output)
# -> ['(', ['(', [['n']], '+', [['n']], ')'], '+', [['n']], ')']

在 LL(1) 解析过程中如何构造解析树？

How do you construct a parse tree during LL(1) parsing?

compiler-construction

stack

abstract-syntax-tree

ll

parse-tree