LR（1）直接解析为抽象语法树
所以我最近问了一个问题，并收到了很好的答案。 但是，所描述的步骤似乎更像是创建具体语法树的步骤。
LR解析过程中的每个缩减对应于分析树中的内部节点。 减少的规则是内部AST节点，从堆栈弹出的项目对应于该内部节点的子项。 为goto推送的项目对应于内部节点，而由移位操作推送的项目对应于AST的叶子（令牌）。
把所有这些放在一起，你可以轻松地创建一个AST，每次你做一个缩减的时候创建一个新的内部节点，并且适当地把所有东西连接在一起。 〜克里斯多德
我知道，所分析的步骤隐含了解析树，但我不想明确构建解析树。 每减少一个节点就会产生整个解析树。 我曾考虑过，如果看到某个状态，我只会建立一个节点。 但是，这似乎不能正常工作。
您不需要在每次缩减时都创建一个节点，并且您构建的节点不需要包含每个缩小的符号。 缩减的符号也不需要以与解析相同的顺序出现。
在很多情况下，AST是完全分析树的简化，与上面相对应。
简单的例子，对于表达式语法，使用类似yacc的解析器生成器：
expr: term { $$ = $1; /* see below */ }
| expr '+' term { $$ = new_sum_node($1, $3); }
term: factor { $$ = $1; /* see below */ }
| term '*' factor { $$ = new_product_node($1, $3); }
factor: '(' expr ')' { $$ = $2; /* See below */ }
| ID { $$ = new_variable_node($1); }
| NUMBER { $$ = new_literal_node($1); }
AST被构建为非终端的语义值。 期望函数new_*_node返回指定类型的新分配的节点。 （这里我们假设有一些机制可以从指针中推断出它是哪种类型的节点，例如，可以使用子类型和虚函数。）
在Yacc（和类似的解析器生成器）中，每个符号（终端或非终端）都有一个关联的“值”，每个生产都有一个相关的操作，当生产减少时执行。 生产动作可以分配非终端的“价值”被降低。 该动作可以利用右侧组件的“值”，因为每一个都是终端（其值由扫描仪设置）或非终端已经减少。 实际上，这是一个S属性语法。
上述一些减少在AST中完全不出现。 尤其是，单位减少量（ expr:term和term:factor ）简单地通过AST的右侧。 同样，括号还原term:'(' expr ')'简单地穿过AST为expr ，其结果是括号有效地从AST消失。 （这在所有语言中都不正确;在某些语言中，明显冗余的括号实际上会影响语义，您需要创建一个AST节点来记录事实。）
在Yacc中，如果没有指定操作，则$$ = $1是默认的减少操作，并且由于大多数单位减少都从AST中消除，所以通常会显示它们而没有减少操作。 为了教学目的，我明确表示他们; 在实践中，你不应该那样做。
上一篇: LR(1) parse straight to Abstract syntax tree
下一篇: Constructing an Abstract Syntax Tree with a list of Tokens