如何理解LALR移位/减少算法

Question

我正在尝试阅读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代替T,因为T代表规则'E'的RHS的第一个"OR".是因为规则E有一个暗示的"EOF"可以这么说(因为我们还没有达到EOF它不能减少)？或者是因为它在这一点上是模糊的(T也代表规则T的RHS的第二个"OR"的第一部分...即T"*"F)？或者它完全是另一回事？

谢谢!

Answer 1

解析器使用两个标准来决定接下来要采取的操作(移位或减少).第一种是当堆栈上的令牌与生产的右侧匹配时.在步骤4之后,堆栈上的T与E = T生产匹配,因此如果这是唯一的标准,那么它可能会减少.但是,解析器也在查看前瞻(即"剩余"中的第一个令牌)以决定要采取的操作.没有规则将E"*"作为前缀,因此减少无效,唯一的操作是转移.在步骤20之后,E = T生产是有效的,因为(正如您猜测的)先行标记实际上存在EOF,它确实匹配.

请注意,一些模糊的语法可能导致shift和reduce操作有效.在这些情况下,Bison决定支持"转变".有关更多详细信息,请参阅Bison文档.但是,上面给出的语法并不含糊不清; 一个先行的标记就足以使它明确无误.