5

我正在尝试在空闲时间进行解析，并且我想为一个非常简单的语法实现一个 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

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

什么时候应该将子节点添加到新创建的节点/什么时候应该创建一个新的根节点？

4

2 回答 2

4

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

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

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

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

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

但是，如果您不想要具体的树，例如，您想要“抽象语法树”，那么您要做的就是让语法工程师控制哪些归约生成节点；通常会在每个语法规则中添加一些程序附件（代码）以在缩减步骤中执行。然后，如果任何这样的程序附件产生一个节点，它就会保留在节点堆栈上。任何产生节点的程序连接都必须连接由右手元素产生的节点。如果有的话，这就是 YACC/Bison/... 大多数 shift-reduce 解析器引擎所做的。去阅读 Yacc 或 Bison 并检查语法。这个方案给了你很多控制权，代价是你坚持要控制。（对于我们所做的，我们不希望在构建语法时进行这么多的工程工作）。

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

于 2014-01-11T18:08:59.633 回答
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 或 bison 这样的工具使这类事情变得更容易，因为它们带来了所有低级机器和堆栈。

于 2014-01-12T02:11:20.753 回答