3

我正在尝试阅读Niklaus Wirth 的Compiler Construction。在第 23 页，他开始描述 LALR 如何在x*(y+z)给定以下语法的情况下解析表达式：

E  = T  | E "+" T. expression 
T  = F  | T "*" F. term 
F  = id | "(" E ")". factor

他继续将减少显示为：

     Action   Stack     Remaining
1             x         * (y + z) 
2    S        x         * (y + z) 
3    R        F         * (y + z) 
4    R        T         * (y + z) 
6    S        T*          (y + z) 
7    S        T*(          y + z) 
8    S        T*(y           + z) 
9    R        T*(F           + z) 
10   R        T*(T           + z) 
11   R        T*(E           + z) 
12   S        T*(E+            z) 
13   S        T*(E + z          ) 
14   R        T*(E + F          ) 
15   R        T*(E + T          ) 
16   R        T*(E              ) 
17   S        T*(E) 
18   R        T*F 
19   R        T 
20   R        E

动作是 S（表示移位）或 R（表示减少……为了清楚起见，我添加了行号）。所以我想我了解如何从步骤 1 到 4 以及从 4 到 20，但我不了解 4 本身。例如，步骤 1 将 x 压入堆栈。x 表示规则“F”的 RHS，因此会发生缩减 -> F。F 表示规则“T”的第一个“OR”，因此可能会发生另一个缩减 -> T。如果这是正确的（我不是确定是吗？），那么为什么不将 T 也替换为 E，因为 T 代表规则“E”的 RHS 的第一个“或”。是不是因为规则 E 有一个隐含的“EOF”可以这么说（因为我们还没有达到 EOF，所以它不能减少）？或者是因为它在这一点上是模棱两可的（T也代表规则T的RHS的第二个“OR”的第一部分......即，T "*" F)? 还是完全是别的东西？

谢谢！

4

1 回答 1

5

解析器使用两个标准来决定下一步采取什么行动（移位或减少）。第一种是当堆栈上的标记与产生式的右侧匹配时。在第 4 步之后，堆栈上的 T 与 E = T 产生式相匹配，因此如果这是唯一的标准，那么它可以在该点减少。然而，解析器也在查看前瞻（即“剩余”中的第一个标记）来决定采取什么行动。没有以 E "*" 作为前缀的规则，因此归约是无效的，唯一的动作是移位。在第 20 步之后，E = T 产生式是有效的，因为（如您所料）那里的前瞻标记实际上是一个 EOF，它确实匹配。

请注意，一些模棱两可的语法可能导致 shift 和 reduce 操作都有效。在这些情况下，Bison 决定支持“转变”。有关更多详细信息，请参阅Bison 文档。但是，上面给出的语法并没有歧义；一个前瞻标记足以使其明确。

于 2011-03-29T03:39:20.110 回答