LR(1) 直接解析为抽象语法树

Question

所以我最近问了一个 close this，并得到了很好的回答。然而，所描述的步骤似乎更像是创建具体语法树的步骤。

Each reduction in the LR parsing process corresponds to an internal node in the parse tree. The rule being reduced is the internal AST node, and the items popped off the stack correspond to the children of that internal node. The item pushed for the goto corresponds to the internal node, while those pushed by shift actions correspond to leaves (tokens) of the AST.

Putting all that together, you can easily build an AST by createing a new internal node every time you do a reduction and wiring everything together appropriately. ~Chris Dodd

我知道所采取的步骤隐含了解析树，但是我不想显式构建解析树。并且每次减少都生成一个节点似乎会产生整个解析树。我考虑过，如果看到某个状态，我只会构建一个节点。然而，这似乎无法正常工作。

Answer 1

不需要在every reduction上构建节点，你构建的节点也不需要包含every 符号被减少。减少的符号也不需要以与解析相同的顺序出现。

在很多情况下，AST 是完整解析树的简化，对应于上述。

简单示例，对于表达式语法，使用类似 yacc 的解析器生成器：

expr: term            { $$ = ; /* see below */ }
    | expr '+' term   { $$ = new_sum_node(, ); }
term: factor          { $$ = ; /* see below */ }
    | term '*' factor { $$ = new_product_node(, ); }
factor: '(' expr ')'  { $$ = ; /* See below */ }
      | ID            { $$ = new_variable_node(); }
      | NUMBER        { $$ = new_literal_node(); }

AST 被构建为非终结符的语义值。函数 new_*_node 预期 return 指定类型的新分配节点。（这里我们假设有某种机制可以从指针推断出它是什么类型的节点。例如，可以使用子类型化和虚函数。）

在 Yacc（和类似的解析器生成器）中，每个符号（终结符或非终结符）都有一个关联的 "value"，并且每个产生式都有一个关联的动作，该动作在产生式减少时执行。生产的动作可以分配被减少的非终端的 "value" 。该操作可以使用右侧组件的 "values"，因为每个组件要么是终端（其值由扫描器设置），要么是已经减少的非终端。实际上，这是一个 S-attributed grammar。

上面的一些归约在 AST 中根本没有出现。特别是，单位缩减（expr:term 和 term:factor）只是通过右侧的 AST。类似地，括号缩减 term:'(' expr ')' 简单地通过了 expr 的 AST，结果是括号从 AST 中有效地消失了。（这在所有语言中都不正确；在某些语言中，明显冗余的括号实际上会影响语义，您需要创建一个 AST 节点来记录事实。）

在 Yacc 中，如果没有指定动作，$$ = 是默认的缩减动作，并且由于大多数单位缩减都从 AST 中删除，因此它们通常会在没有缩减动作的情况下显示。为了教学目的，我把它们说清楚了；实际上，你不应该那样做。

LR(1) 直接解析为抽象语法树

LR(1) parse straight to Abstract syntax tree

java

parsing

tree

abstract-syntax-tree

lr