编译原理-LALR分析表的构造.ppt

5.3.5 LALR分析表的构造,对 LR(1) 来说, 存在着某些状态, 这些状态除向前搜索符不同外, 其核心部分都是相同的. 同心集: 两个LR(1)项目集具有相同的心, 即除去搜索符之后, 这两个集合是相同的。 能否将核心部分相同的诸状态合并为一个状态? 这种合并是否会产生冲突? LALR方法 : 在LR(1)项目集规范族基础上, 合并同心集.,能,可能,图5.10 LR(1)项目集和GO函数 p116,(0)S S (1)S BB (2)B aB (3)B b,该文法产生的是语言 a*ba*b,S,I,0,：S S, #,S BB, #,B aB, a/b,B b, a/b,B,I,2,：S BB, #,B aB, #,B b, #,I,4,：B b, a/b,b,I,3,：B aB, a/b,B aB, a/b,B b, a/b,b,b,I,7,：B b, #,I,8,：B aB, a/b,a,B,I,5,：S BB, #,I,6,：B aB, #,B aB, #,B b, #,B,a,a,I,9,：B aB, #,b,a,B,I,1,：S S , #,例5.13,合并同心集,表5.5 例5.13 的 LR分析表 p116,表5.6 例5.13 的 LALR分析表 p119,合并同心集,36,47,5,89,s36,s47,s36,s47,s36,s47,89,r3,r3,r3,r1,r2,r2,r2,是否会产生冲突？,1、合并GOTO表,例如：设 Im和In 同心,同心集遇某文法符号X进行状态转换后, 仍然同心. 所以合并GOTO表的过程中不会出现冲突,Im: AX, a,In: AX, b,Im : AX, a,In : AX, b,X,X,Imn: AX, a/b,Im n: AX, a/b,X,(1)出错与出错合并 结果仍为出错，无冲突 (2)移进与移进合并 无冲突 (3)出错与移进合并 不会出现此情况 (4)移进与归约合并 不会出现此情况 (5)归约与出错合并 人为规定它做归约 放松了报错条件 (6)归约与归约合并 A) 按同一产生式归约，无冲突 B) 按不同产生式归约，将造成冲突,2、合并ACTION表,合并同心项目集可能会引起冲突 同心集的合并不会引起新的移进归约冲突 同心集的合并有可能产生新的归约归约冲突,G: (0) S S (1) S aAd (2) S bBd (3) S aBe (4) S bAe (5) A c (6) B c,对ac有效的项目集,A c , d B c , e,对bc有效的项目集,A c , e B c , d,合并同心集,A c , d/e B c , d/e,该文法是LR(1)文法 但不是LALR(1)文法,LALR的能力弱于LR,构造LR(1)项目集规范族 (见黑板),产生归约-归约冲突,(1)构造文法的LR(1)项目集族 C=I0,I1, ,In (2)把所有的同心集合并在一起， 记 C =J0, J1, , Jm为合并后的新族， 含有项目 SS, # 的Jk为分析表的初态。,构造 LALR(1)分析表算法,(3) 从C 构造ACTION表 若AaB, bJk ，且GO(Jk, a)= Jj， 则置ACTIONk, a为 sj 若A, aJk，j是产生式A的编号 则置ACTIONk, a为 rj， 若SS, # Jk，则置ACTIONk, #为 acc (4) GOTO表的构造 若GO(Jk, A)=Ji，则置GOTOk, A = i (5) 分析表中凡不能用(3)、(4)填入信息的空白格均填上“出错标志”。,更正教材,更正教材,经上述步骤构造的分析表若不存在冲突，则称它为文法的LALR分析表 存在这种分析表的文法称为LALR文法 对于同一个文法，LALR分析表和LR(0)以及SLR分析表永远具有相同数目的状态。,例：写出输入符号串 aab 的LR分析过程和LALR分析过程,(0)S S (1)S BB (2)B aB (3)B b,例5.13,过程见黑板, 分析表,结论： 对于错误的输入串,LALR会比LR执行一些多余归约,但不会比LR移进更多的符号. 对于正确的输入串,LR和LALR分析器始终如影相随,例 ：有如下文法GS: (0) S S (1) S L=R (2) S R (3) L *R (4) L i (5) R L 写出此文法的LALR分析表 并根据文法的LALR分析表分析输入串 “ i=*i= # ”,LR(1)项目集规范族,I1: Go(I0 , S) S S , #,I2: Go(I0 , L) SL =R, # RL , #,I3: Go(I0 , R) SR , #,I4: Go(I0 , *) L* R, =/# R L, =/# L *R, =/# L i, =/#,I5: Go(I0 , i) L i , =/#,I6: Go(I2 , =) SL= R, # R L, # L *R, # L i, #,I7: Go(I4 , R) L* R , =/#,I8: Go(I4 , L) R L , =/#,Go(I4 , *) 同 I4,Go(I4 , i) 同 I5,I9: Go(I6 , R) SL=R, #,I10: Go(I6 , L) R L , #,I11: Go(I6 , *) L* R, # R L, # L *R, # L i, #,I12: Go(I6 , i) L i , #,I13: Go(I11 , R) L* R , #,Go(I11 , L) 同 I10,Go(I11 , *) 同 I11,Go(I11 , i) 同 I12,合并同心集,合并 I4与I11,合并 I5与I12,合并 I7与I13,合并 I8与I10,I4,11: L* R, =/# R L, =/# L *R, =/# L i, =/#,I5,12: L i , =/#,I7,13: L* R , =/#,I8,10: R L , =/#,原 LR 分析表,LALR分析表,i = * i = # 的LALR分析过程,i = * i = # 的LR分析过程,i = * i # 的LALR分析过程,i = * i # 的LR分析过程,LR分析小结,LR分析过程是_ 符号栈中的符号串是_ 分析决策依据_ 为构造LR分析表，可先构造_DFA LR分析器的关键是_ LR(0) 、SLR(1) 、 LALR(1) 、 LR(1) 功能_ 四种LR类型的文法是_关系 LR类型文法是_二义的,规范归约过程,活前缀,栈顶状态和现行输入符号,识别活前缀的,分析表的构造,逐个增强,无,真包含,