使用 shift-reduce 解析构建解析树

Question

我在空闲时间尝试解析，并且我想为一个非常非常简单的语法实现一个 shift-reduce 解析器。我已经阅读了许多在线文章，但我仍然对如何创建解析树感到困惑。这是我想要做的一个例子：

---

语法：

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

这是一个示例输入：

1 + 1 + 1 + 1

标记化后，变为：

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

---

我明白那个：

1. 换挡意味着将第一个输入标记压入堆栈并将其从输入中移除
2. 减少意味着用语法元素替换堆栈中的一个或多个元素

所以，基本上，这应该发生：

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

除了“减少什么？” 怀疑，我不知道如何正确构建解析树。这棵树应该看起来像这样：

1    +    o
          |
     1    +    o
               |
          1    +    1

我应该在减少时创建一个新节点吗？

什么时候应该向新创建的节点添加子节点/什么时候应该创建新的根节点？

Answer 1

简单而明显的做法是在每次归约时创建一个树节点，并将已归约的语法元素中的树节点添加到该树节点。

这可以通过与原始解析器使用的“移位令牌”堆栈并行运行的节点堆栈轻松管理。对于长度为 N 的规则的每次缩减，移位令牌堆栈都会缩短 N，并且非终结符会被推送到移位堆栈上。同时，通过删除顶部 N 个节点来缩短节点堆栈，为非终结符创建一个节点，将删除的 N 个节点附加为子节点，并将该节点推送到节点堆栈上。

该策略甚至适用于右侧长度为零的规则：创建一个树节点并将空的子节点集附加到它（例如，创建一个叶节点）。

如果您将终端节点上的“移位”视为（形成终端的字符）到终端节点的减少，那么终端节​​点移位就很合适。为终端创建一个节点，并将其推入堆栈。

如果这样做，您将得到一个与语法同构匹配的“具体语法/解析树”。（我们这样做是为了我提供的商业工具）。有很多人不喜欢这种具体的树，因为它们包含关键字等节点，而这并没有真正增加太多价值。确实如此，但是这样的树非常容易构造，并且非常容易理解，因为语法就是树结构。当您有 2500 条规则时（正如我们对完整 COBOL 解析器所做的那样），这很重要。这也很方便，因为所有机制都可以完全构建到解析基础设施中。语法工程师只需编写规则，解析器运行，瞧，一棵树。更改语法也很容易：只需更改它，瞧，您仍然可以获得解析树。

然而，如果你不需要具体的树，例如你想要一个“抽象语法树”，那么你要做的就是让语法工程师控制哪些约简生成节点；通常会向每个语法规则添加一些程序附件（代码）以在缩减步骤上执行。然后，如果任何此类过程附件生成节点，它将保留在节点堆栈上。任何生成节点的程序附件都必须附加由右侧元素生成的节点。如果有的话，这就是 YACC/Bison/...大多数移位归约解析器引擎所做的事情。去阅读 Yacc 或 Bison 并检查语法。这个方案给了你很多控制权，但代价是你必须坚持要获得这种控制权。（对于我们所做的事情，我们不希望在构建语法方面花费这么多的工程精力）。

在生成 CST 的情况下，从概念上讲，从树中删除“无用”节点是很简单的；我们在我们的工具中做到了这一点。结果很像 AST，无需手动编写所有这些程序附件。