更新时间:2022-09-22 22:58:18
本节书摘来自华章出版社《编译与反编译技术》一书中的第3章,第3.4节自下而上的语法分析,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.4 自下而上的语法分析
所谓自下而上的语法分析就是从左向右扫描输入串,逐步进行“归约”,直到文法的开始符号,或者从树末端开始,自下而上为输入串构造语法分析树。这里的归约是指根据文法的产生式规则,把产生式的右部替换成左部符号。
3.4.1 移进与归约
自下而上的语法分析法是一种“移进–归约”法,移进–归约的基本思想是用一个寄存符号的先进后出栈,把输入符号一个一个地移进栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)该产生式的左部符号。移进–归约分析程序的结构与预测分析程序的结构类似,也是采用表驱动的方式实现。其包含一个输入缓冲区、一个输出缓冲区、一个符号栈、一个分析表和一个总控程序。
1)输入缓冲区用来存放待分析的符号串,它以界符“#”作为结束标志。
2)输出缓冲区用来存放分析结果,通常是产生式序列或者语法分析树。
3)分析栈中存放分析过程中的文法符号,栈底符号为“#”,分析开始时栈里面只含有“#”。当分析栈中仅剩“#”和文法的开始符号S,输入串指针也指向输入串尾的“#”时,分析成功。
4)分析表用来存放不同情况下的分析动作,分析动作有四种:
① 移进:将下一输入符号移入栈。
② 归约:用产生式左侧的非终结符替换栈顶的可归约串(某产生式右部)。
③ 接受:分析成功。
④ 出错:出错处理。
5)移进–归约分析的总控程序按照如下方式进行工作:把输入符号自左至右逐个移进分析栈,并且边移入边分析,一旦栈顶的符号串形成某个句型的可归约串时就进行一次归约,即用相应产生式的左部非终结符替换当前可归约串。接下来继续查看栈顶是否形成新的可归约串,若为可归约串则再进行归约;若栈顶不是可归约串则继续向栈中移进后续输入符号。不断重复这一过程,直到将整个输入串处理完毕。若此时分析栈只剩有“#”和文法的开始符号则分析成功,即确认输入串是文法的一个句子;否则,即认为分析失败。如图3-6所示为移进–归约语法分析器模型。
1. 将#和初始状态s0压入栈,将w#放入输入缓冲区;
2. 令输入指针ip指向w#的第一个符号;
3. 令s是栈顶状态,a是ip所指向的符号;
4. repeat
5. if ACTION[s,a]= =sj then /* sj表示将下一个状态j和现行的输入符号a移进栈*/
6. { 把状态j和符号a分别压入栈;
7. 令ip指向下一输入符号;}
8. else if ACTION[s,a ]=rj then /* rj表示按第j个产生式A→β归约 */
9. { 从栈顶弹出|β|个符号;
10. 令s'是现在的栈顶状态;
11. 把GOTO[s',A]和A先后压入栈中;
12. 输出产生式 A→β;}
13. else if ACTION[s,a]= acc then
14. return;
15. else
16. error();
例3.27 考虑式(3.2)文法,其LR分析表如表3-4所示。表中所引用的记号的意义是:acc表示接受,空白符表示出错。另外,若a为终结符,则GOTO[s,a]的值已列在ACTION[s,a]的sj之中(即状态j),因此GOTO表仅对所有非终结符(比如A)列出GOTO[s,A]的值。假定输入串为i1+i2*i3,则LR分析器的工作过程如表3-5所示。
i + * ( ) # E T F
状态 ACTION GOTO
i + * ( ) # E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
表3-5 i+i*i的LR分析过程
步骤 状态 符号 输入串 动作说明
1 0 # i1+i2*i3# s5: 状态5和i1入栈
2 0 5 # i1 +i2*i3# r6: 用F→i归约且GOTO(0,F)=3入栈
3 0 3 # F +i2*i3# r4: 用T→F归约且GOTO(0,T)=2入栈
4 0 2 # T +i2*i3# r2: 用E→T归约且GOTO(0,E)=1入栈
5 0 1 # E +i2*i3# s6: 状态6和+入栈
6 0 1 6 # E+ i2*i3# s5: 状态5和i2入栈
7 0 1 6 5 # E+i2 *i3# r6: 用F→i归约且GOTO(6,F)=3入栈
8 0 1 6 3 # E+F *i3# r4: 用T→F归约且GOTO(6,T)=9入栈
9 0 1 6 9 # E+T i3# s7: 状态7和入栈
10 0 1 6 9 7 # E+T* i3# s5: 状态5和i3入栈
11 0 1 6 9 7 5 #E+T*i3 # r6: 用F→i归约且GOTO(7,F)=10入栈
12 0 1 6 9 7 10 # E+TF # r3: 用T→TF归约且GOTO(6,T)=9入栈
13 0 1 6 9 # E+T # r1: 用E→E+T归约且GOTO(0,E)=1入栈
14 0 1 # E # acc:分析成功
定义3.14(LR文法) 对于一个给定的文法G(S),如果能够构造一张上述的LR分析表,使得它的每个入口均是唯一确定的,则称该文法为LR文法。
对于一个LR文法,当分析器对输入串进行自左至右扫描时,一旦句柄呈现于栈顶,就能及时对它实行归约。
定义3.15(LR(k)文法) 对于一个给定的文法G(S),如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析,则称该文法为LR(k)文法。
对于多数语言而言,k=0或1就够了。LR文法肯定是无二义的,一个二义文法决不会是LR文法;但是,LR分析技术可以进行适当修改以适用于分析一定的二义文法。
3.4.3 LR(0)分析
采用LR(0)分析表进行语法分析的方法称为LR(0)分析方法,LR(0)分析方法不需要向前查看输入符号,分析器根据当前的栈顶状态即可确定下一步所应采取的动作。
在未讨论LR(0)分析表的构造之前,首先需要定义一些相关概念。
定义3.16(活前缀) 活前缀是指规范句型的一个前缀,这种前缀不含句柄之后的任何符号。也就是说,对于规范句型αβδ,β为句柄,如果αβ=u1u2…ur,则符号串ε,u1u2…ui(1≤i≤r)是αβδ的活前缀(δ必为终结符串)。
之所以称为活前缀,是因为在其右边增添一些终结符号之后,就可以使它成为一个规范句型。活前缀与句柄之间有如下关系之一:
1)活前缀不含有句柄的任何符号,期望从剩余输入串中能够看到由某产生式A→α的右部α所推导出的符号串。
2)活前缀只含有句柄的部分符号,某产生式A→α1α2的右部子串α1已经出现在栈顶,期待从剩余的输入串中能够看到α2推导出的符号串。
3)活前缀已经含有句柄的全部符号,某一产生式A→α的右部符号串α已经出现在栈顶,用该产生式进行归约。
LR分析法分析过程中,只要已分析的符号串是正确的,符号栈里的文法符号由底到顶就构成规范句型的一个活前缀,当这个活前缀包含句柄时就归约,否则移进。因此,只要能识别出所有活前缀,识别活前缀是否包含句柄,就能决定什么时候移进,什么时候归约。下面的问题就是,给定一个文法,如何识别该文法的所有活前缀以及活前缀与句柄之间的关系。为此,引入LR(0)项目的概念。
定义3.17(LR(0)项目) 给定一个文法G(S),右部某个位置上标有圆点的产生式称为该文法的一个LR(0)项目。其中,圆点在产生式最右端的LR(0)项目称为归约项目;对文法开始符号的归约项目又称接受项目;圆点后第一个符号为非终结符号的LR(0)项目称为待约项目;圆点后第一个符号为终结符号的LR(0)项目称为移进项目。
注意:产生式A→ε只有一个LR(0)归约项目“A→·”。LR(0)项目中的圆点符分割已获取的内容和待获取的内容,点的左边代表历史信息,右边代表展望信息。直观地讲,LR(0)项目表示在分析过程的某一阶段,已经看到了产生式的多大部分以及希望看到的部分。
例3.28 产生式S→bBB对应有4个LR(0)项目
S→·bBB
S→b·BB
S→bB·B
S→bBB·
其中,
1)S→·bBB是移进项目,表示活前缀不包含句柄,分析过程中应将b移进符号栈。
2)S→b·BB是待约项目,表示活前缀不包含句柄,期待在继续分析过程中进行归约而得到B。
3)S→bB·B也是待约项目,表示活前缀不包含句柄,期待在继续分析过程中进行归约而得到B。
4)S→bBB·是归约项目,表示已从输入串看到能由bBB推导出的符号串,联系到可将bBB归约为S,bBB是句柄,此时活前缀包含句柄。
为了保证文法开始符号只出现在一个产生式的左边,亦即保证分析器只有一个接受状态,对该文法进行拓广,构造其拓广文法。便会有一个仅含项目S'→S·的状态,这就是唯一的“接受”态。
定义3.18(拓广文法) 假定文法G是一个以S为开始符号的文法,构造一个文法G',它包含了整个G,但它引进了一个不出现在G中的非终结符S',并加进一个新产生式S'→S,而这个S'是G'的开始符号。那么,称G'是G的拓广文法。
下面介绍识别文法所有活前缀的方法,算法3.8给出了利用DFA来识别文法所有活前缀的方法。
算法3.8 构造识别文法所有活前缀的DFA方法
输入:文法G=(VT,VN,P,S)的拓广文法G'
输出:识别文法G'所有活前缀的DFA
步骤:
1.拓广文法的每个项目表示一个状态,规定包含拓广文法开始符号的待归约项目所对的状态为初态,其余的任何状态均可认为是NFA的终态(活前缀识别态)。
2.状态之间转换关系的确定方法如下:
① 若状态i为X→X1 … Xi-1·Xi … Xn,状态j为X→X1 … Xi-1Xi·Xi+1 … Xn,则从状态i画一条标志为Xi的有向边到状态j;
② 若状态i为X→α·Aβ,A为非终结符,则从状态i画一条ε边到所有状态A→·γ。
3.把识别文法所有活前缀的NFA确定化,就可以得到一个以项目集合为状态的识别文法G'所有活前缀的DFA。
定义3.19(LR(0)项目集规范族) 构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。
例3.29 已知文法G(A):
A→aA
A→b
构造识别该文法所有活前缀的DFA。
解:先对G(A)进行拓广,拓广后的文法G'(S')为
S'→A
A→aA
A→b(3.12)
G'(S')的LR(0)项目有
(1)S'→·A
(2)A→·aA
(3)A→a·A
(4)A→·b
(5)A→b·
(6)S'→A·
(7)A→aA·
依据算法3.8可以得到识别文法G'(S')活前缀的NFA,如图3-8所示。
对图3-8中的NFA进行确定化,得到识别文法G'(S')的活前缀的DFA,如图3-9所示。
图3-8 识别例3.29中文法G'(S')的 图3-9 识别例3.29中文法G'(S')的
活前缀的NFA 活前缀的DFA
从而可以得到,文法G'(S')的LR(0)项目集规范族C为:
C = {{S'→·A,A→·aA,A→·b},{A→a·A,A→·aA,A→·b},
{A→b·},{S'→A·},{A→aA·}}
通过列出拓广文法的所有LR(0)项目,进而构造识别活前缀的NFA,再确定化为DFA的方法,工作量较大,不实用,实用的方法是直接构造以项目集为状态的识别活前缀的DFA。在未介绍这个方法之前先介绍几个概念。
定义3.20 (LR(0)项目集的闭包(CLOSURE)) 假定I是文法G的任一LR(0)项目集合,定义I的闭包CLOSURE(I)如下:
1)I的任何项目都属于CLOSURE(I)。
2)若A→α·Bβ属于CLOSURE(I),那么,对任何关于B的产生式B→γ,项目B→·γ也属于CLOSURE(I)。
3)重复执行上述两步骤直至CLOSURE(I)不再增大为止。
为了识别活前缀,还需要定义一个状态转换函数GO。
定义3.21 (LR(0)项目集的转换函数GO) 假定I是文法G的一个LR(0)项目集,X是文法G的一个文法符号,函数值GO(I,X)定义为:
GO(I,X)=CLOSURE(J)
其中J={任何形如A→αX·β的项目| A→α·Xβ属于I}。GO(I,X)称为转移函数,项目A→αX·β称为A→α·Xβ的后继。
通过CLOSURE和GO函数很容易构造文法G的拓广文法G'的LR(0)项目集规范族,具体见算法3.9。
算法3.9 构造文法的LR(0)项目集规范族
输入:文法G=(VT,VN,P,S)的拓广文法G'
输出:G'的LR(0)项目集规范族C
步骤:
例3.30 对式(3.12)文法,利用算法3.9计算其LR(0)项目集规范族。
解:I0= CLOSURE ({S'→·A})={S'→·A,A→·aA,A→·b}
GO(I0,a)= CLOSURE ({A→a·A})={A→a·A,A→·aA,A→·b}=I1
GO(I0,b)= CLOSURE ({A→b·})={A→b·}=I2
GO(I0,A)= CLOSURE ({S'→A·})={S'→A·}=I3
GO(I1,a)= CLOSURE ({A→a·A})=I1
GO(I1,b)= CLOSURE ({A→b·})={A→b·}=I2
GO(I1,A)= CLOSURE ({A→aA·})={A→aA·}=I4
由于I2、I3 和I4都是归约项目,所以计算结束,故G'(S')的LR(0)项目集规范族C={I0,I1,I2,I3,I4}。
我们希望从识别文法活前缀的DFA建立LR分析器。因此需要研究这个DFA的每个项目集中项目的不同作用。
定义3.22(LR(0)有效项目) 项目A→β1·β2对活前缀γ=αβ1是有效的,如果存在一个规范推导:
S?αAω ? αβ1β2ω,ω∈VT
一个项目可能对好几个活前缀都是有效的(当一个项目出现在LR(0)项目集规范族的好几个不同的项目集合中时便是这种情形)。若归约项目A→ β1·对活前缀αβ1是有效的,则它告诉我们应把符号串β1归约为A,即把活前缀αβ1变为αA。若移进项目A→ β1·β2对活前缀αβ1是有效的,则它告诉我们句柄尚未形成,因此下一步动作应是移进。但是,可能存在如下情形,即对同一个活前缀存在不止一个有效项目,并且有的是移进项目,有的是归约项目,这就有可能存在冲突,这种冲突通过向前多看几个输入符号或许能够获得解决。
若项目A→α·Bβ对活前缀γ=δα是有效的,并且B→η是一个产生式,则项目
B →·η对γ=δα也是有效的。那是因为如果A→α·Bβ对γ=δα是有效的,则存在规范推导
S?δAω?δαBβω,ω∈VT
假定存在规范推导βω?φω,φω∈VT,则对任意的B→η,有规范推导
S?δAω?δαBβω?δαBφω?δαhφω
由定义3.22可知,项目B →·η对γ=δα也是有效的。依据该结论,对于每个活前缀,就可以构造它的有效项目集。实际上,一个活前缀γ的有效项目集就是从上述DFA的初态出发,沿着标记为γ的路径到达的那个项目集(状态)。也即,在任何时候,分析栈里的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一个基本定理,我们不打算在这里证明该定理,而是通过一个例子对其进行说明。
例3.31 考虑式(3.12)文法及图3-9中它的识别活前缀自动机。符号串aa是一个活前缀,这个自动机在读出aa后到达的状态包含有三个项目,它们分别是
A→a·A
A→·aA
A→·b
下面说明这三个项目都对aa有效。考虑下面三个规范推导
S'?A ? aA ? aaA
S'? A ? aA ? aaA ? aaaA
S'? A ? aA ? aaA ? aab
第一个推导表明A→a·A的有效性,第二个推导表明A→·aA的有效性,第三个推导表明A→·b的有效性。显然对活前缀aa不再存在其他有效项目了。
定义3.23(LR(0)文法) 对于一个给定的文法G,假若识别其拓广文法G'活前缀的自动机中的每个状态(项目集)不存在下述情况:
1)既含有移进项目又含有归约项目。
2)含有多个归约项目。
则称G是一个LR(0)文法。
对于LR(0)文法,我们可直接从它的项目集规范族C和识别活前缀自动机的状态转换函数GO构造出LR分析表。算法3.10是构造LR(0)分析表的算法。
由于假定LR(0)文法规范族的每个项目集不含冲突项目,因此按上述方法构造的分析表的每个入口都是唯一的(即不含多重定义)。我们称如此构造的分析表是一张LR(0)分析表,使用LR(0)分析表的分析器叫做LR(0)分析器。
算法3.10 构造LR(0)分析表
输入:文法G=(VT,VN,P,S)的拓广文法G'(S')
输出:文法G'的LR(0)分析表
步骤:
1.构造G'的LR(0)项目集规范族C={I0,I1,…,In}和识别活前缀自动机的状态转换函数GO,令每个项目集Ik的下标k作为分析器的状态,包含项目S'→·S的集合Ik的下标k为分析器的初态。
2.ACTION子表的构造:
① 若项目A→α·aβ∈Ik且GO(Ik,a)=Ij,a为终结符,则置ACTION[k,a]为sj,表示将(j,a)移进栈。
② 若项目A→α·∈Ik,则对任何终结符a(或结束符#),置ACTION[k,a]为rj,表示用产生式A→α进行归约,其中j是产生式的编号,即A→α是文法G'(S')的第j个产生式。
③ 若项目S'→S·∈Ik,则置ACTION[k,#]为acc表示分析成功。
3.GOTO子表的构造:
若GO(Ik,A)=Ij,A为非终结符,则置GOTO[k,A]=j。
4.分析表中凡不能用规则2~3填入的空白格均置为“出错标志”。
例3.32 对于式(3.12)文法,依据算法3.10可以得到其LR(0)分析表如表3-6所示。
4.分析表中凡不能用规则2~3填入的空白格均置为“出错标志”。
定义3.24(SLR(1)文法和SLR(1)分析器) 对于一个给定的文法G,如果按算照3.11构造出的ACTION与GOTO表不含多重入口,则称该文法为SLR(1)文法。数字“1”的意思是,在分析过程中顶多只要向前看一个符号。使用SLR(1)表的分析器称为SLR(1)分析器。
例3.34 构造式(3.2)文法的SLR(1)分析表。
解:例3.33已给出识别式(3.2)文法的拓广文法所有活前缀的DFA,见图3-10。其中项目集I1、I2和I9都含有“移进–归约”冲突。
i + * ( ) # E T F
状态 ACTION GOTO
i + * ( ) # E T F
0 s5 s4 1 2 3
1 s7 acc
2 r2 s6 r2 r2
3 r4 r4 r4 r4
4 s5 s4 10 2 3
5 r6 r6 r6 r6
6 s5 s4 8
7 s5 s4 9 3
8 r3 r3 s11
9 r1 s6 r1 r1
10 s7 s11
11 r5 r5 r5 r5
例3.35 文法G(S)具有如下产生式:
S→L=R
S→R
L→*R
L→id
R→L(3.14)
该文法为无二义性,对其进行拓广,得到拓广文法G'( S')的产生式如下:
(0)S'→S
(1)S→L=R
(2)S→R
(3)L→*R
(4)L→id
(5)R→L(3.15)
解:I0 = CLOSURE({[S'→·S,#]})
= { [S'→·S,#],[S→·L=R,#],[S→·R,#],[L→·*R,=/#],[L→·i,/#],
[R→·L,#] }
I1 = GO(I0,S)= CLOSURE({[S'→S·,#]})={[S'→S·,#]}
I2 = GO(I0,L)= CLOSURE({[S →L·=R,#],[R →L·,#]})
={[S →L·=R,#],[R →L·,#]}
I3 = GO(I0,R)= CLOSURE({[S→R·,#]})={[S→R·,#]}
I4 = GO(I0,)= CLOSURE({[L →·R,=/#]})
= {[L →·R,=/#],[R →·L,=/#],[L →·i,=/#],[L →·R,=/#]}
I5 = GO(I0,i)= CLOSURE({[L→i·,=/#]})={[L→i·,=/#]}
I6 = GO(I2,=)= CLOSURE({[S →L=·R,#]})
= {[S →L=·R,#],[R →·L,#],[L →·*R,#],[L →·i,#]}
I7 = GO(I4,R)= CLOSURE({[L→R ·,=/#]})={[L→R ·,=/#]}
I8 = GO(I4,L)= CLOSURE({[R→L·,=/#]})={[R→L·,=/#]}
I9 = GO(I6,R)= CLOSURE({[S→L=R·,#]})={[S→L=R·,#]}
I10=GO(I6,L)= CLOSURE({[R→L·,#]})={[R→L·,#]}
I11=GO(I6,i)= CLOSURE({[L→i·,#]})={[L→i·,#]}
I12=GO(I6,)= CLOSURE({[L →·R,#]})
={[L →·R,#],[R →·L,#],[L →·R,#],[L →·i,#]}
I13=GO(I12,R)= CLOSURE({[L→R·,#]})={[L→R·,#]}
综上可得,式(3.15)文法的LR(1)项目集规范族C如表3-8所示。根据该项目集可以得到识别式(3.15)文法所有活前缀的DFA,如图3-12所示。
表3-8 式(3.15)文法的LR(1)项目集规范族C
I0: S'→·S,#
S →·L=R,#
S →·R,#
L →·*R,=/#
L →·i,=/#
R →·L,# I3: S→R·,# I6: S →L=·R,#
R →·L,#
L →·*R,#
L →·i,# I10: R→L·,#
I4: L →*·R,=/#
R →·L,=/#
L →·i,=/#
L →·*R,=/# I11: L→i·,#
I12: L →*·R,#
R →·L,#
L →·*R,#
L →·i,#
I1: S'→S·,# I5: L→i·,=/# I7: L→R ·,=/# I13: L→R·,#
I2: S →L·=R,#
R →L·,# I8:
I9: R→L·,=/#
S→L=R·,#
② 若项目[A→α·,a]∈Ik,则ACTION[k,a]为rj,其中,假定A→α为文法G'的第j个产生式。
③ 若项目[S'→S?·?,?#]∈Ik,则置ACTION[k,#]为acc 表示分析成功。
4.分析表中凡不能用规则2~3填入的空白格均置为“出错标志”。
定义3.30(LR(1)文法和LR(1)分析器) 对于一个给定的文法G,如果按算法3.13构造出的ACTION与GOTO表不含多重入口,则称它是文法G的LR(1)分析表;具有LR(1)分析表的文法称为LR(1)文法;使用LR(1)分析表的分析器称为LR(1)分析器。
例3.37 基于例3.36中的计算结果,利用算法3.13可以得到式(3.15)文法的LR(1)分析表,如表3-9所示。从而可知,式(3.15)文法不能用SLR(1)技术解决冲突,但能用LR(1)技术解决。
表3-9 式(3.15)文法的LR(1)分析表
状态 ACTION GOTO
= * i # S L R
0 s4 s5 1 2 3
1 acc
2 s6 r5
3 r2
4 s4 s5 8 7
5 r4 r4
6 s12 s11 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 r4
12 s12 s11 10 13
13 r3
S→·aBc,# B→·e,c I5: S→aC·d,# C→e·,c
S→·bCc,# C→·e,d I6: B→e·,c I10: S→aBc·,#
S→·aCd,# I3: S→b·Cc,# C→e·,d I11: S→aCd·,#
S→·bBd,# S→ b·Bd,# I7: S→bC·c,# I12: S→bCc·,#
I1: S'→S·,# C→·e,c I8: S→bB·d,# I13: S→bBd·,#
I2: S→a·Bc,# B→·e,d
5.分析表中凡不能用步骤3~4填入信息的空白格均填上“出错标志”。
定义3.31(LALR(1)文法和LALR(1)分析器) 对于一个给定的文法G,如果按照算法3.14构造出的ACTION与GOTO表不含多重入口,则称它是文法G的LALR(1)分析表;具有LALR(1)分析表的文法称为LALR(1)文法;使用LALR(1)分析表的分析器称为LALR(1)分析器。
对于同一个文法,LALR(1)分析表和LR(0)分析表以及SLR(1)分析表永远具有相同数目的状态。由例3.39可知,LALR(1)分析方法比LR(1)分析方法能力差一点,但它却能对付一些SLR(1)分析方法所不能对付的情况(见例3.40),也即LALR(1)分析方法的能力介于SLR(1)分析方法和LR(1)分析方法之间。
例3.40 由例3.38可知,式(3.15)文法的LR(1)项目集族C中I4和I12、I5和I11、I7和I13、I8和I10为同心集。I4和I12合并同心集后的项目集为
I4/12: {[L→·R,=/#],[R→·L,=/#],[L→·i,=/#],[L→·R,=/#]}
I5和I11合并同心集后的项目集为
I5/11: {[L→i·,=/#]}
I7和I13合并同心集后的项目集为
I7/13: {[L→*R·,=/#]}
I8和I10合并同心集后的项目集为
I8/10: {[R→L·,=/#]}
合并同心集后得到的项目集仍然不含有冲突,所以,式(3.15)文法也是LALR(1)文法。相应的识别式(3.15)文法的所有规范句型活前缀的DFA如图3-13所示。根据这个DFA,利用算法3.14很容易构造出式(3.15)文法的LALR(1)分析表,如表3-11所示。
LALR(1)分析方法与LR(1)分析方法还有一点不同之处,当输入串有误时,LR(1)分析方法能够及时发现错误,而LALR分析方法则可能还需继续做一些不必要的归约动作,但决不会执行新的移进,即LALR(1)分析方法能够像LR(1)分析方法一样准确地指出出错的地点。
= * i # S L R
0 s4/12 s5/11 1 2 3
1 acc
2 s6 r5
3 r2
4/12 s4/12 s5/11 8/10 7/13
5/11 r4 r4
6 s4/12 s5/11 8/10 9
7/13 r3 r3
8/10 r5 r5
9 r1
例3.41 假设输入串为i1=i2=#,则表3-9所对应的LR(1)分析器的分析过程如表3-12所示,表3-11所对应的LALR(1)分析器的分析过程如表3-13所示。从表3-12和表3-13中可以看出LALR(1)分析方法多做了一些不必要的归约动作。
表3-13 LALR(1)分析器对i=i=#的分析过程
步骤 状态 符号 输入串 步骤 状态 符号 输入串
0 0 # i1=i2=# 4 0265/11 #L=i2 =#
1 05/11 #i1 =i2=# 5 0268/10 #L=L =#
2 02 #L =i2=# 6 0269 #L=R =#
3 026 #L= i2=# 7 报错
3.4.7 分析方法比较
至此,我们已经讨论了常用的语法分析方法,即LL(1)分析方法和LR(k)分析方法。下面我们就这些方法做一个比较。LR分析方法能分析的文法类是LL(1)分析方法能分析的文法类的真超集。对于LR(k)分析方法,分析程序只要求在看见了产生式右部推出的所有符号以及从输入串中预测k个符号后,就能够识别产生式右部的出现。这个要求比LL(k)分析方法的要求弱,LL(k)分析方法要求看见了右部推出的前k个符号后就识别所使用的产生式。所以,LR文法比LL文法能够描述、识别更多的语言。
针对本章所介绍的常用的LR分析方法,LR(0)分析方法不考虑搜索符,SLR(1)分析方法在归约时考虑搜索符,因此,SLR(1)分析方法比LR(0)分析方法的能力强,但是两种方法有相同的状态数,然而SLR(1)分析方法对搜索符所含信息量的利用有限,未考虑栈中内容。LR(1)分析方法考虑对于产生式A→α的归约,不同使用位置的A要求不同的后继符号,所以LR(1)分析方法比SLR(1)分析方法更精确,功能更强,但由于状态的细化,LR(1)分析方法比SLR(1)分析方法和LR(0)分析方法存在更多的状态,代价更高。通过对LR(1)分析方法中LR(1)项目集族的同心项目集进行合并所得到的LALR(1)分析方法,其状态数目与SLR(1)分析法和LR(0)分析方法中的相同,功能比LR(1)分析方法弱但比SLR(1)分析法强。