《编译原理分析表的构造》由会员分享，可在线阅读，更多相关《编译原理分析表的构造（20页珍藏版）》请在金锄头文库上搜索。
1、5.3.5 LALR分析表的构造w 对 LR(1) 来说, 存在着某些状态, 这些状态除向前 搜索符不同外, 其核心部分都是相同的.w 同心集: 两个LR(1)项目集具有相同的心, 即除去搜 索符之后, 这两个集合是相同的。w 能否将核心部分相同的诸状态合并为一个状态? w 这种合并是否会产生冲突? w LALR方法 : 在LR(1)项目集规范族基础上, 合并同心集.能 可能图5.10 LR(1)项目集和GO函数 p116(0)S S (1)S BB (2)B aB (3)B b该文法产生的是语言 a*ba*b SI0：S S, #S BB, #B aB, a/bB b, a/bBI2：S B
2、B, #B aB, #B b, #I4：B b, a/bbI3：B aB, a/bB aB, a/bB b, a/bbbI7：B b, #I8：B aB, a/baBI5：S BB, #I6：B aB, #B aB, #B b, #Ba aI9：B aB, #baBI1：S S , #例5.13合 并 同 心 集I4：B b, a/bI3：B aB, a/bB aB, a/bB b, a/bI7：B b, #I8：B aB, a/bI6：B aB, #B aB, #B b, #I9：B aB, #I47: Bb , a/b/# I89: BaB , a/b/# I36: BaB , a/b/#
3、BaB , a/b/# Bb , a/b/# 表5.5 例5.13 的 LR分析表 p116 状 态ACTIONGOTO ab#SB 0s3s412 1acc 2s6s75 3s3s48 4r3r3 5r1 6s6s79 7r3 8r2r2 9r2状 态ACTIONGOTO ab#SB 0s3s412 1acc 2s6s75表5.6 例5.13 的 LALR分析表 p119合 并 同 心 集36 47 589s36 s47s36 s47s36s4789 r3r3r3 r1r2r2r2是 否 会 产 生 冲 突 ？1、合并GOTO表例如：设 Im和In 同心 同心集遇某文法符号X进行状态转换后,
4、 仍然同心. 所 以合并GOTO表的过程中不会出现冲突Im: AX, aIn: AX, bIm : AX, aIn : AX, bXXImn: AX, a/bIm n: AX, a/bX(1)出错与出错合并 结果仍为出错，无冲突 (2)移进与移进合并 无冲突 (3)出错与移进合并 不会出现此情况 (4)移进与归约合并 不会出现此情况 (5)归约与出错合并 人为规定它做归约 放松了报错条件 (6)归约与归约合并 A) 按同一产生式归约，无冲突B) 按不同产生式归约，将造成冲突2、合并ACTION表合并同心项目集可能会引起冲突 w 同心集的合并不会引起新的移进归约冲突 w 同心集的合并有可能产生新
5、的归约归约冲突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为分
6、析表的初态。构造 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)填入信息的空白格均 填上“出错标志”。更正教材更正教材w 经上述步骤构造的分析表若不存在冲突，则 称它为文法的LALR分析表w 存在这种分析表的文法称为LALR文法w 对于同一个文法，LAL
7、R分析表和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 w 写出此文法的LALR分析表 w 并根据文法的LALR分析表分析输入串 “ i=*i= # ”LR(1)项目集规范族I1: G
8、o(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:
9、 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 S S, # SL=R, # SR, # L*R, =/# L i, =/# RL, #I0初态合并同心集合并 I4与I11合并 I5与I12合并 I7与I13合并 I8与I10I4,11:L* R, =/#R L, =/#L *R, =/#L i, =/#I5,12: L i , =/#I7,13: L* R , =/#I8,1
10、0: R L , =/#状 态ACTIONGOTO =i*#S LR 0S5S4123 1acc 2S6r53r24S5S487 5r4r4 6S12S111097r3r3 8r5r5 9r1 10r5 11S12S1110 1312r4 13r3原 LR 分 析 表LALR分析表状 态ACTIONGOTO =i*#S LR 0S5S4123 1acc 2S6r53r2 4S5S487 5r4r4 6S5S489 7r3r3 8r5r5 9r1步骤状态符号栈剩余输入串动作 10#i=*i=# 移进 S5 205#i=*i=# 归约 r4 Li 302#L=*i=# 移进 S6 4026#L=*
11、i=# 移进 S4 50264#L=*i=# 移进 S5 602645#L=*i=# 归约 r4 Li 702648#L=*L=# 归约 r5 R L 802647#L=*R=# 归约 r3 L *R 90268#L= L=# 归约 r5 R L 100269#L= R=# 报错i = * i = # 的LALR分析过程i = * i = # 的LR分析过程步骤状态符号栈剩余输入串动作 10#i=*i=# 移进 S5 205#i=*i=# 归约 r4 Li 302#L=*i=# 移进 S6 4026#L=*i=# 移进 S11 5026 11#L=*i=# 移进 S12 6026 11 12#
12、L=*i=# 报错步骤状态符号栈剩余输入串动作 10#i=*i# 移进 S5 205#i=*i# 归约 r4 Li 302#L=*i# 移进 S6 4026#L=*i# 移进 S4 50264#L=*i# 移进 S5 602645#L=*i# 归约 r4 Li 702648#L=*L# 归约 r5 RL 802647#L=*R# 归约 r3 L*R 90268#L= L# 归约 r5 RL 100269#L= R# 归约 r1 S L=R 1101#S# 接受i = * i # 的LALR分析过程i = * i # 的LR分析过程步骤状态符号栈剩余输入串动作 10#i=*i# 移进 S5 20
13、5#i=*i# 归约 r4 Li 302#L=*i# 移进 S6 4026#L=*i# 移进 S11 5026 11#L=*i# 移进 S12 6026 11 12#L=*i# 归约 r4 Li 7026 11 10#L=*L# 归约 r5 RL 8026 11 13#L=*R# 归约 r3 L*R 9026 10#L= L# 归约 r5 RL 100269#L= R# 归约 r1 S L=R 1101#S# 接受LR分析小结w LR分析过程是_ w 符号栈中的符号串是_ w 分析决策依据_ w 为构造LR分析表，可先构造_DFA w LR分析器的关键是_ w LR(0) 、SLR(1) 、 LALR(1) 、 LR(1) 功能_ w 四种LR类型的文法是_关系 w LR类型文法是_二义的规范归约过程 活前缀 栈顶状态和现行输入符号 识别活前缀的分析表的构造 逐个增强无真包含
