使用Shift-Reduce解析构建解析树

Question

我在空闲时间里尝试解析，想要实现一个非常简单语法的移位-规约解析器。我阅读了许多在线文章，但仍然不清楚如何创建解析树。以下是我想做的一个示例：

---

语法：

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

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

何时应该给新创建的节点添加子节点/何时应该创建新的根节点？

- Vittorio Romeo

Answer 1

简单明了的做法是在每次规约时创建一个树节点，并将从被规约为该树节点的语法元素中添加的树节点添加到该节点中。

这可以通过与原始解析器使用的“移位标记”堆栈并行运行的节点堆栈轻松管理。对于长度为N的规则的每个规约，移位标记堆栈缩短N，非终端标记被推入移位堆栈。同时，通过删除顶部N个节点缩短节点堆栈，为非终端创建一个节点，将删除的N个节点作为子节点附加，并将该节点推入节点堆栈。

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

如果您认为对终端节点的“移位”是对终端节点进行规约（形成终端的字符），那么终端节点移位就很容易理解了。为终端创建一个节点，并将其推入堆栈。

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

但是，如果您不想要具体的树，例如，您想要一个“抽象语法树”，那么您必须让语法工程师控制哪些规约生成节点；通常通过为要在规约步骤上执行的每个语法规则添加一些过程附加（代码）来完成。然后，如果任何此类过程附加产生节点，则将其保留在节点堆栈上。任何产生节点的过程附加必须附加右手元素产生的节点。如果有任何YACC/Bison/...大多数移位-规约解析器引擎都会这样做。去阅读关于Yacc或Bison的文章并检查语法。这种方案为您提供了很多控制权，但代价是坚持要求您掌握这种控制权。（对于我们所做的事情，我们不希望在构建语法时进行如此多的工程化努力）。

在生成CST的情况下，从树中概念上轻松删除“无用”节点；我们在我们的工具中这样做。结果很像AST，而无需编写所有这些过程附加的手动工作。

- Ira Baxter

---

谢谢您详细的回答。还有一个问题：我应该尽可能减少堆栈的使用，还是尽量少减少？（当有两种可能的减少方式时，哪一种优先级更高？） - Vittorio Romeo

尽量减少堆栈的使用。如果您的解析操作没有给出选择，那么您就无法选择堆栈大小。如果您没有冲突，您就不必做出选择。如果您有选择，您可以定义不同的优先级问题答案，并获得不同的移位-归约解析器。如果您确实有冲突，则您的语法不是LALR（1）；通过选择一个，您已经隐含地定义了您指定的BNF的有趣变体为合法。这个问题的正确答案是，“去读一本关于解析的书”，因为细节非常技术化。 - Ira Baxter

Answer 2

你遇到问题的原因是你的语法中存在移位/规约冲突：

expr: expr OP expr
    | number

You can resolve this in 2 ways:

expr: expr OP number
    | number

对于左结合运算符，或。

expr: number OP expr
    | number

对于右结合的情况，这也应该确定您树的形状。

在检测到一个子句完整时，通常进行规约。在右结合的情况下，您将从期望数字的状态1开始，将其推送到值堆栈上并转移到状态2。在状态2中，如果令牌不是OP，则可以将数字规约为表达式。否则，推送运算符并转移到状态1。完成状态1后，可以将数字、运算符和表达式缩减为另一个表达式。请注意，您需要一种机制在规约后“返回”。总体解析器将从状态0开始，立即转到状态1，并在规约后接受。

请注意，像yacc或bison这样的工具使这种类型的事情更加容易，因为它们提供了所有低级机制和堆栈。

- Ingo

---

关于语法的一个问题。如果我想添加括号表达式怎么办？expr: ( expr) - 我可能会遇到这样的情况，堆栈上有 expr OP ( num OP expr ) ，变成了 expr OP ( expr )，然后是 expr OP expr，此时解析器无法继续进行。在这种情况下语法应该怎么样？ - Vittorio Romeo

@VittorioRomeo 您可以将 number 替换为 term，并加入一个新规则 term: number | '(' expr ')'。 - Ingo