如何理解LALR移位/归约算法

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’的第一个"OR“，所以另一个缩减可能发生在-> T。如果这是正确的(我不确定它是正确的？)，那么为什么T不也被E代替，因为T代表规则'E‘的RHS的第一个"OR”。是不是因为规则E有一个隐含的" EOF“，也就是说(既然我们还没有达到EOF，它就不能减少)？或者是因为它在这一点上是模棱两可的(T也代表规则T的RHS的第二个" Or“的第一部分……例如，T "*“F)？或者是完全不同的东西？

谢谢!

Answer 1

解析器使用两个标准来确定下一步要采取的操作(shift或reduce)。第一种情况是堆栈上的令牌与产品的右侧匹配。在步骤4之后，堆栈上的T与E=T的结果相匹配，因此如果这是唯一的标准，那么它可以在该点上减少。但是，解析器也会查看前视(即“剩余”中的第一个标记)，以决定采取什么操作。没有以E "*“作为前缀的规则，因此归约是无效的，唯一的操作是移位。在步骤20之后，E=T结果是有效的，因为(正如您所猜测的)那里的先行标记实际上是一个EOF，它确实匹配。

请注意，一些模棱两可的语法可能会导致移位和缩减操作都有效。在这些情况下，Bison选择了"shift“。有关更多详细信息，请参阅Bison docs。然而，上面给出的语法并不是模棱两可的；一个先行标记就足以使它明确。