编译原理与实践：LR(1)分析方法

如上所述，SLR（1）方法无法解决例5.14中项目I2中含有的移进-归约冲突。此外，SLR（1）方法解决动作冲突时，对于归约项目A→α·，只要当前输入符号a∈FOLLOW（A）时，就采用产生式A→α进行归约。但是，如果栈中的符号串为βα，归约后变为βA，再移进输入符号a，分析栈将变为βAa，而βAa未必是文法规范句型的活前缀。这种情况下，用A→α进行归约并不正确。例如，图5-7所示的识别表达式文法的活前缀DFA，项目集I2存在移进-归约冲突，即{E→T·，T→T·*F}。若栈顶状态为2，栈中符号为#T，当前输入符为‘）’。）∈FOLLOW（E）。此时，按SLR（1）方法将使用产生式E→T进行归约，归约后栈顶符号为#E。再移进当前符‘）’后，栈中为#E），不是文法规范句型的活前缀。

LR（1）方法可以解决SLR（1）方法在某些情况下存在的动作冲突和无效归约问题。LR（1）方法是一种规范的LR分析法，其功能最强，适用于大多数上下文无关文法，但实现代价比较高。

1.LR（1）项目

LR（1）分析需要重新定义项目以包含更多的信息，项目一般形式为

[A→α·β,a]

其中，A→α·β是一个LR（0）项目；a∈VT，称为项目的向前搜索字符。

LR（1）每个项目附加1个终结符a以确切地指出，对于产生式A→αβ，β后跟哪些终结符时才允许将αβ归约为A。a将可以保证归约后分析栈呈现下一句型的活前缀。例如，项目[S→S，#]表示当面临句子右端结束标识时，才可以将S归约为S。

一个LR（1）项目[A→β1·β2，a]对活前缀αβ1是有效的，如果存在规范推导

其中，搜索字符a=FIRST（ω）；或者，当ω为ε时，a为‘#’。

例5.15 考虑文法。

S→BB

B→bB|a

文法的LR（0）项目B→b·B，针对不同的搜索字符对不同的活前缀是有效的。由此可得文法的LR（1）项目。例如，LR（1）项目[B→b·B，b]，有

其中，ω=ba。因此，项目对活前缀γ=bbb是有效的。

对于相同的LR（0）项目B→b·B，还存在LR（1）项目[B→b·B，#]，有

其中，ω=ε。因此，LR（1）项目[B→b·B，#]对活前缀Bbb是有效的。

注意，向前搜索字符串仅对归约项目[A→α·，a]有意义，对于移进或待约项目不起作用。归约项目[A→α·，a]意味着，当它所属的状态呈现在栈顶，而且当前输入符号为a时，才可以将栈顶的句柄α归约为A。

2.LR（1）项目集规范族

有效的LR（1）项目集规范族的构造方法与LR（0）项目集规范族的构造方法类似，同样需要Closure（I）和GOTO（I，X）这两个函数。

对于项目集I，构造LR（1）项目集的闭包Closure（I）方法如下：

（1）将I中的所有项目都加入Closure（I）。

（2）若项目[A→α·Bβ，a]∈Closure（I），对于任何b=FIRST（βa），若[B→·γ，b]不在Closure（I）中，则将其加进去。

（3）重复执行步骤（2），直到Closure（I）不再增大为止。

LR（1）项目集的闭包Closure（I）的含义为，如果项目集中的项目[A→α·Bβ，a]对活前缀δα是有效的，将存在规范推导

其中，a=FIRST（ω）。那么，对于形如B→γ的产生式，将存在规范推导

由此，项目[B→·γ，b]对活前缀δα也是有效的。其中，b=FIRST（βω），即b=FIRST（βa）。

假设项目集I中的项目形如[A→α·Xβ，a]，项目集I的转换函数GOTO（I，X）定义为

GOTO(I,X)=Closure({[A→αX·β,a]})

构造LR（1）项目集规范族仍以项目[S→·S，#]为初态集的初始项目，然后利用Closure对其求闭包得到初态项目集，进而应用GOTO函数构造新的项目集，直至项目集规范族不再增大为止。LR（1）项目集规范族的构造方法如算法5.7所示。

算法5.7 构造LR（1）项目集规范族及识别活前缀的DFA。(www.xing528.com)

(1)C={Closure({[S→·S,#]})};

（2）重复执行动作（3），直到C不再增大为止；

（3）for（C中的每个项目集I和G的每个符号X）

例5.16 构造例5.14文法的LR（1）项目集规范族和识别句型活前缀的DFA。

对于例5.14来说，I2的冲突不能用SLR（1）方法予以解决。使用算法5.7可以有效地解决I2中的移进-归约冲突。

由于归约项目的搜索字符集合与移进项目的移进符号不相交，因此，在I2中，当面对输入符“#”时进行归约，面对“=”时移进，冲突可以解决，该文法是LR（1）文法。

3.LR（1）分析表

LR（1）分析表的构造方法如算法5.8所示。

图5-8　识别例5.14文法的LR（1）项目活前缀的DFA

算法5.8 构造LR（1）分析表。

假定C={I0，I1，…，In}，Ik的下标k表示分析表的状态，含有[S→·S，#]的状态为分析器的初态。

（1）若项目[A→α·aβ，b]∈Ik，且GOTO（Ik，a）=Ij，其中a∈VT，则置ACTION[k，a]=Sj，即将输入符号a和状态j分别移入文法符号栈和状态栈。

（2）若项目[A→α·，a]∈Ik，其中a∈VT，则置ACTION[k，a]=rj，即用产生式A→α进行归约，j是在文法中对产生式A→α的编号。

（3）若项目[S→S·，#]∈Ik，则置ACTION[k，#]=acc，表示接受。

（4）若GOTO（Ik，A）=Ij，其中A∈VN，则置GOTO[k，A]=j，表示当栈顶符号为A时，从状态k转换到状态j。

（5）凡不能用规则（1）～（4）填入分析表中的位置，均置“出错标志”。

依据算法5.8构造的分析表，若不存在多重定义入口，则称为文法的规范LR（1）分析表。规范LR（1）分析表功能最强，适用于多种文法，但实现代价比较高。具有规范LR（1）分析表的文法称为LR（1）文法。注意，若用上述方法构造的分析表出现冲突时，则文法不是LR（1）文法。使用规范LR（1）分析表的分析器称为LR（1）分析器或规范LR分析器。

例5.17 构造如下拓广文法的LR（1）分析表：

(0)S→S (2)B→bB

(1)S→BB (3)B→a

首先，将[S→·S，#]作为初态集的项目，然后，利用闭包和GOTO函数计算该文法的LR（1）项目集规范族。图5-9给出了项目集族和GOTO函数表示的识别活前缀的DFA。注意，[B→·bB，a/b]是[B→·bB，a]和[B→·bB，b]两个项目的简化表示。

图5-9　识别例5.17文法的DFA

最后，执行算法5.8可以得到如表5-14所示的LR（1）分析表。

表5-14　例5.17文法的LR（1）分析表

续表

在多数情况下，同一文法的LR（1）项目集数比LR（0）项目集数要多，甚至可能多好几倍。之所以这样，是因为同一个LR（0）项目集的搜索字符集合可能不同，多个搜索字符集合则对应着多个LR（1）项目集。例5.17中的文法是一个LR（0）文法，其LR（0）项目集规范族中只有7个状态，而LR（1）项目集规范族中有10个状态。

有时，LR分析需要向前查看k个输入才能够确定冲突解决策略，称为LR（k）分析。LR（k）每个项目需要附带有k个终结符，项目的一般形式为

[A→α·β,a1a2…ak]

其中，A→α·β是一个LR（0）项目，ai∈VT，a1a2…ak是项目的向前搜索字符串，或称为展望串。归约项目[A→α·，a1a2…ak]意味着当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2…ak时，才可以将栈顶的句柄αβ归约为A。对多数程序语言的语法来说，向前搜索一个符号就可以确定移进还是归约。