1

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

LR 解析过程中的每个缩减都对应于解析树中的一个内部节点。减少的规则是内部 AST 节点，从堆栈中弹出的项目对应于该内部节点的子节点。为 goto 推送的项目对应于内部节点，而由 shift 操作推送的项目对应于 AST 的叶子（令牌）。

将所有这些放在一起，您可以通过在每次进行缩减时创建一个新的内部节点并将所有内容适当地连接在一起来轻松构建 AST。~克里斯·多德

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

4

1 回答 1

1

您不需要在每次归约时都构建一个节点，并且您构建的节点不需要包含每个被归约的符号。减少的符号也不需要以与解析相同的顺序出现。

在许多情况下，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 中消除，因此它们通常会在没有减少操作的情况下显示。出于教学目的，我将它们明确表示；在实践中，你不应该那样做。

于 2015-05-27T02:57:09.670 回答