使用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/......大多数shift-reduce分析器引擎所做的。阅读Yacc或Bison，并检查语法。这个计划给你很多控制权，但坚持要你控制这个控制权。 （对于我们所做的，我们不希望在构建语法方面做这么多工程努力）。

在生成CST的情况下，从树上删除“无用的”节点在概念上很简单;我们在我们的工具中这样做。结果很像AST，没有人工编写所有这些程序附件。

Answer 2

你麻烦的原因是，你有一个转变/减少冲突在你的语法：

expr: expr OP expr 
    | number 

您可以通过两种方式解决此问题：对于左结合运营商

expr: expr OP number 
    | number 

，或者

expr: number OP expr 
    | number 

对于正确的关联的。这也应该确定你的树的形状。

通常在检测到一个子句完成时进行缩减。在正确的关联情况下，您将从状态1开始，期望一个数字，将其推入数值堆栈并切换到状态2.在状态2中，如果令牌不是OP，则可以将数字减少到expr 。否则，按下操作员并切换到状态1.状态1完成后，可以将数字，运算符和表达式减少到另一个表达式。请注意，您需要一种机制在减少后“返回”。然后整个解析器将以状态0开始，比如立即进入状态1并在缩减之后接受。

请注意，像yacc或bison这样的工具使得这类东西变得更加容易，因为它们带来了所有低级别的机器和堆栈。