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

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 S I0：S S, # S BB, # B aB, a/b B b, a/b B I2：S BB, # B aB, # B b, # I4：B b, a/b b I3：B aB, a/b B aB, a/b B b, a/b b b I7：B b, # I8：B aB, a/b a B I5：S BB, # I6：B aB, # B aB, # B b, # B a a I9：B aB, # b a B I1：S S , # 例5.13 合 并 同 心 集 I4：B b, a/b I3：B aB, a/b B aB, a/b B b, a/b I7：B b, # I8：B aB, a/b I6：B aB, # B aB, # B b, # I9：B aB, # I47: Bb , a/b/# I89: BaB , a/b/# I36: BaB , a/b/# 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 5 89 s36 s47 s36 s47 s36s4789 r3r3r3 r1 r2r2r2 是 否 会 产 生 冲 突 ？ 1、合并GOTO表 例如：设 Im和In 同心 同心集遇某文法符号X进行状态转换后, 仍然同心. 所 以合并GOTO表的过程中不会出现冲突 Im: AX, a In: AX, b Im : AX, a In : AX, b X X Imn: AX, a/bIm n: AX, a/b X (1)出错与出错合并 结果仍为出错，无冲突 (2)移进与移进合并 无冲突 (3)出错与移进合并 不会出现此情况 (4)移进与归约合并 不会出现此情况 (5)归约与出错合并 人为规定它做归约 放松了报错条件 (6)归约与归约合并 A) 按同一产生式归约，无冲突 B) 按不同产生式归约，将造成冲突 2、合并ACTION表 合并同心项目集可能会引起冲突 w 同心集的合并不会引起新的移进归约冲突 w 同心集的合并有可能产生新的归约归约冲突 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)填入信息的空白格均 填上“出错标志”。 更正教材 更正教材 w 经上述步骤构造的分析表若不存在冲突，则 称它为文法的LALR分析表 w 存在这种分析表的文法称为LALR文法 w 对于同一个文法，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 w 写出此文法的LALR分析表 w 并根据文法的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 S S, # SL=R, # SR, # L*R, =/# L i, =/# RL, # I0初态 合并同心集 合并 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 , =/# 状 态 ACTIONGOTO =i*#S LR 0S5S4123 1acc 2S 6 r5 3r2 4S5S487 5r4r4 6S1 2 S1 1 109 7r3r3 8r5r5 9r1 10r5 11S1 2 S1 1 10 13 12r4 13r3 原 LR 分 析 表 LALR分析表 状 态 ACTIONGOTO =i*#S LR 0S5S4123 1acc 2S6r5 3r2 4S5S487 5r4r4 6S5S489 7r3r3 8r5r5 9r1 步骤状态符号栈剩余输入串动作 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 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#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 205#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# 归约