parsing - 如何理解 LALR Shift/Reduce 算法

Question

我正在尝试阅读 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' 的第一个“或”，因此可以发生另一个缩减 -> T。如果那是对的(我不是确定是吗？)，那么为什么不将 T 也替换为 E，因为 T 代表规则“E”的 RHS 的第一个“OR”。是不是因为规则 E 有一个隐含的“EOF”可以这么说(因为我们还没有达到 EOF，所以不能减少)？或者是因为它在这一点上不明确(T 也代表规则 T 的 RHS 的第二个“OR”的第一个部分......即 T“*”F)？还是完全不同？

谢谢!

Answer 1

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

请注意，一些不明确的语法可能导致移位和归约操作均有效。在这些情况下，Bison 决定支持“转变”。查看Bison docs了解更多详情。但是，上面给出的语法没有歧义；一个前瞻标记足以使其明确无误。