建立与转移减少解析的解析树

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. shifting 意味着按下堆栈上的第一个输入令牌并从输入中移除它
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

要做的简单和明显的事情是在每次减少时创建树节点，然后从减少到该树节点的语法元素中添加树节点。

这很容易用一个节点堆栈管理，该节点堆栈并行运行到原始解析器使用的“Shift令牌”堆栈。对于长度n的每次减少，换档脚跟堆栈由n缩短，并且在换档堆栈上推动了非终端令牌。同时，通过删除顶部n个节点来缩短节点堆栈，为非终端创建一个节点，将删除的n节点连接为子节点，然后将该节点推到节点堆栈上。

此策略甚至适用于具有零长手右侧的规则：创建树节点并将空集的子组与其附加到它（例如，创建叶节点）。

如果您认为终端节点上的“移位”作为终端节点的减少（形成终端的字符），则终端节点换档拟合拟合。为终端创建一个节点，然后将其推到堆栈。

如果您这样做，您可以获得一个“具体的语法/解析树”，它与语法正常匹配。 （我们为我提供的商业工具这样做）。有很多人不喜欢这样的具体树木，因为它们包含关键字等的节点，这并不真正增加了很多值。真实的，但这种树木易于构建，并且易于理解的是语法是树结构。当你有2500规则时（正如我们为完整的COBOL解析器所做的那样），这就是这个问题。这也是方便的，因为所有机制都可以完全构建到解析基础架构中。语法工程师简单地写规则，解析器运行，voila，一棵树。还有很容易改变语法：只需改变它，瞧，你仍然可以解析树木。

但是，如果您不想要一个具体树，例如，您想要一个“抽象语法树”，那么您要做的是让语法工程师控制哪些减少生成节点;通常会在减少步骤中向每个语法规则添加一些程序附件（代码）。然后，如果任何此类程序附件产生节点，则会保留在节点堆栈上。产生节点的任何程序附件必须附加由右手元件产生的节点。如果有的话是什么YACC / Bison / ...大多数转移减少解析器发动机都这样做。阅读关于YACC或野牛并检查语法。该方案为您提供了很多控制，以坚持认为您控制的价格。 （对于我们所做的而言，我们不希望在建立语法中的这种巨大的工程工作）。

在生产CST的情况下，它在概念上简单，以从树木中删除“无用”节点;我们在我们的工具中这样做。结果很像AST，如果没有手动努力写下所有这些程序附件。

Answer 2

您的麻烦的原因是您在语法中换班/减少冲突：

expr: expr OP expr
    | number

.

您可以在2种方式中解析：

expr: expr OP number
    | number

.

对于左联想运算符，或

expr: number OP expr
    | number

.

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

减少通常在检测到一个子句完成时完成。在正确的关联案例中，您将从期望数字的状态1开始，将其推动到值堆栈并转移到状态2.在状态2中，如果令牌不是OP，则可以减少一个数字到expr 。否则，将运算符按钮和转移到状态1.一旦状态1完成，您可以将数字，运算符和表达式减少到另一个表达式。注意，您需要一个机制在减少后“返回”。然后将整个解析器从状态0开始，例如，立即转到状态1并在减少后接受。

请注意，像YACC或北极等工具使这种东西更容易，因为它们带来了所有低级机械和堆栈。