LR分析法的LR(1)分析表的构造

如题所述

前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少,造表算法简单,大多数程序设计语言基本上都可用SLR(1)文法来描述。然而,也的确存在这样的文法,其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。
例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中,P由如下的产生式组成:
0? S′→S4?B→C
1?S→CbBA5?B→Db
2?A→Aab6?C→a
3?A→ab7?D→a
识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突,但因FOLLOW(S)={#},故上述冲突可通过SLR(1)规则得到解决。然而,在项目集I8={C→a·,D→a·}中,由于FOLLOW(C)={a,b},FOLLOW(D)={b},即FOLLOW(C)∩FOLLOW(D)≠?,故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证,对于任何K>0,上述文法也是非SLR(k)的,故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此,我们需要更强的LR分析法,即LR(1)分析方法来解决这一问题。
对SLR(1)规则稍作分析即可发现,它对某些文法失效的原因,在于当所给的文法出现冲突的分析动作时,SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A),以确定是否应按产生式A→α进行归约,而没有考察符号串α所在规范句型的“环境”,即没有考察α在规范句型中的“上下文”,这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα),且当前的输入符号a也属于FOLLOW(A),就贸然将α归约为A,此时分析栈中的符号串将变成#δA,但若文法中并不存在以δAa为前缀的规范句型,那么,这种归约无效。例如,对于上述文法中的规范句型Cbabab,当分析达到格局
I0I2I4I8[]#Cbabab(4?50)
时,如果仅根据当前输入符号b∈FOLLOW(C),就将栈顶符号a按产生式C→a归约为C,则有如下的格局:
I0I2I4I6[]#CbCbab
但在该文法中,根本不存在以CbCb为前缀的规范句型,因此在执行下一动作将b移进之前,分析器将报告“出错”。由此可见,在分析过程中,当试图用某一产生式A→α归约栈顶符号串α时,不仅应查看栈中符号串δα,还应向前扫视一输入符号a (我们将a称为向前搜索符号),只有当δAa的确构成文法某一规范句型的前缀时,才能用此产生式进行归约。为了指明上述事实,应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a,使之成为[A→α·β,a]的形式,我们将此种项目称为一个LR(1)项目。同时,为了使分析的每一步都能在栈中得到一个规范句型的活前缀,还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外,为了克服分析动作的冲突,在必要时,我们还可将某些项目集进行分解,以便使每一个状态都能确切地指明: 当α已出现在栈顶,且面临哪些输入符号时,才能按产生式A→α将α归约为A。
所谓一个LR(1)项目[A→α·β,a]对活前缀γ=δα有效,是指存在规范推导
S?*δAy?δαβyy∈V*T
且满足下列条件:
(1) 当y≠ε时,a是y的首符号;
(2) 当y=ε时,a=#。
例如,对于例4?8所给文法,因有
S?CbBA?CbBab?CbDbab
其中,δ=Cb,α=D,β=b,y=ab,A=B,故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因
S?*CbDbab?Cbabab
其中,δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出,当分析器所处的格局为式(4?50)时,应当将栈顶符号a归为D,而不应将它归约为C。
与LR(0)文法的情况相类似,识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示,而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族,我们同样需要用到两个函数,即CLOSURE(I)及GO(I,X)。
对每一LR(1)项目集I,相应的CLOSURE(I)的定义如下:
(1) I中的任何LR(1)项目都属于CLOSURE(I)。
(2) 设项目[A→α·Bβ,a]∈CLOSURE(I),并假设它对活前缀γ=δα有效,则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa),形如[B→·η,b]的全部项目也都对γ有效,故若[B→·η,b]原不在CLOSURE(I)中,则应将其放入。事实上,因为[A→α·Bβ,a]对γ=δα有效,则由定义我们有:
s?*δAy?δαBβyy∈V*T
且a∈FIRST(y)∪{#},故可将上面的推导写成
S?*δAy?δαBβaωω∈V*T∪{#}
现设文法已经过化简,故不论β是否为ε,从βaω总能推出终结符号串,于是可假定
βaω?*bω′
又因a≠ε,有FIRST(βaω)=FIRST(βa),从而就得到推导
S?*δαBbω′
由此可见,一切形如[B→·η,b]的项目也对活前缀γ=δα有效。
(3) 重复步骤(2)直到没有新的项目加入为止。
至于函数GO(I,X),其中I为一LR(1)项目集,X为某一文法符号,与LR(0)文法类似,我们也将它定义为:
GO(I,X)=CLOSURE(J)
其中J是由这样的一些LR(1)项目组成: 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目,其后继项目[A→αX·β,a]∈J。注意,每一LR(1)项目与其后继项目有相同的向前搜索符号。
有了上述CLOSURE(I)和GO(I,X)的定义之后,采用与LR(0)类似的方法,可构造出所给文法G的LR(1)项目集族C及状态转换图。例如,对于上述文法,其LR(1)项目集及状态转换图如图419所示。
对于给定的文法G,当相应的LR(1)项目集族C及GO函数构造出来之后,便可按如下的算法构造它的LR(1)分析表:
(1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目,若GO(Ii,X)=Ij,且当X为一终结符号a时,置ACTION[i,a]=sj。但若X为一非终结符号时,则置GOTO[i,X]=j。
(2) 若归约项目[A→α·,a]∈Ii,A→α为文法的第j个产生式,则置ACTION[i,a]=rj。
(3) 若项目[S′→S·,#]∈Ii,则置ACTION[i,#]=acc。
(4) 在分析表中,凡不能照上述规则填入信息的元素,均置为“出错”。
对于一个文法G来说,若按上述算法所构造的分析表不含有多重定义的元素,则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如,上述文法的LR(1)分析表见表416,所以它是一个LR(1)文法。

温馨提示:答案为网友推荐,仅供参考