编译原理5.3.4-规范LR分析表的构造.ppt

5.3.4 规范LR分析表的构造 通过例子引入LR(k)项目 1.LR(k)项目定义 2.有效LR(1)项目 3.构造LR(1)项目集规范族 4.构造LR(1)分析表 5.LR(1)文法 文法5.9 p113 (0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L I2:移进-归 约冲突 例: I0: SS S L=R S R L *R L i R L I6: SL=R R L L *R L i I2: SL=R R L I4:L*R R L L *R L i I1: SS I3:SR I7:L*R I8:RL I5:Li I9:SL=R = R * R L i R S * i i L * L FOLOW(R) = # , = 文法不含有以 R= 为前缀的规范句型, 因此不能用 RL 对于栈顶的L进行归约 (0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e I0: SS S aAd S bAc S aec S bed I1: SS S I2: S aAd S aec A e I3: S bAc S bed A e ab A e I4: S aAd I5:S aec A e A e I6: S bAc I7:S bed A e d I8: S aAd c I9: S aec c I10: S bAc d I11: S bed FOLLOW(A)=c,d I5,I7中冲 突不能用 SLR(1)方 法解决 补充例1 (0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e I5:S aec A e I7:S bed A e 所有可能的规范推导序列: S= S = aAd = aed S= S = bAc = bec S= S = aec S= S = bed I5识别活前缀ae,不存在规范句型aAc, 当面临输入符号为c时应移进 面临d时应用产生式Ae归约 I7识别活前缀be,不存在规范句型bAd, 当面临输入符号为d时应移进 面临c时应用产生式Ae归约 结论: 并不是FOLLOW(A)的每个元素, 在含A的所有句型中,在A的后面都会出现 小结: SLR(1)分析法中的无效归约 I2: SL =R R L (0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L FOLLOW(R) = # , = (0) S S (1) S aAd (2) S bAc (3) S aec (4) S bed (5) A e I5:S aec A e I7:S bed A e FOLLOW(A) = c,d 在SLR(1)方法中,若项项目集Ik含有 A ,则则在状态态k时时,只 要所面临临的输输入符号aFOLLOW(A)，就用A归约归约 栈栈里的符号串所构成的活前缀缀未必允许许把归约为归约为 A，因 为为可能没有一个规规范句型含有前缀缀Aa。因此，在这这种情况 下，用A进进行归约归约 未必有效。 1.LR(K)项目定义 重新定义项目: A，a1a2ak A是一个LR(0)项目, 称为心, a1a2ak 称为它的向前搜索符串(展望串), ai是终结符, 这样的一个项目称为一个LR(k)项目。 向前搜索符串仅对归约项目A， a1a2ak有意义.对于任何移进或待约项目不 起作用。 若存在规范推导 则项目 A 对活前缀 是有效的。 若aFirst()， 若= 则 a=# 则LR(1)项目A, a对于活前缀 是有效的。 注: 1)如果aFirst(),即使aFollow(A), 项目A, a也是无效的。 2)规范LR分析法仅考虑有效的LR(1)项目。 2.有效LR(1)项目 * R R A S 例5.12 : S BB B aB | b S R BB R BaB R Bab R aBab R aaBab R aaaBab R S * R aaBabaaaBab BaB, a 对活前缀 = aaa是有效的 * R R A S R S * R BaBBaaB BaB, # 对活前缀 = Baa是有效的 3.构造LR(1)项目集规范族 一、项目集I的闭包CLOSURE(I) (1)I的任何项目都属于CLOSURE(I) (2)若项目AB，a属于CLOSURE(I) 如果B,b原来不在CLOSURE(I)中， 则把它加进去。 B是一个产生式, bFIRST(a) (3)重复执行步骤(2),直到CLOSURE(I)不再增大为止 二、GO函数 令I是一个项目集，X是一个文法符号， GO(I,X) = CLOSURE(J)，其中 J= 任何形如AX,a的项目 | AX,aI 注：在执行转换函数GO时，搜索符并不改变。 三、构造G的LR(1)项目集族C的算法 BEGIN C:= CLOSURE( SS, # ) ; REPEAT FOR C中的每个项目集I和G的每个文法符号X IF GO(I, X)非空 且不属于 C THEN 把GO(I, X)加入C中； UNTILL C不再增大； END 例5.13 考虑如下拓广文法 p115 (0)S S (1)S BB (2)B aB (3)B b 构造LR(1)项目集规范族 I0 : CLOSURE(SS,#) S S, # S BB, # B aB, a/b B b, a/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 图5.10 LR(1)项目集和GO函数 p116 更正教材 (0)S S (1)S BB (2)B aB (3)B b I1：S S , # 4.构造LR(1)分析表 (1)若项目Aa,bIk 且GO(Ik,a)=Ij ， 置 ACTIONk,a为 sj。 (2)若项目A ,aIk ，j是产生式A的编号 置 ACTIONk,a为rj ， (3)若项目SS ，#Ik， 置 ACTIONk,#为 acc。 (4) 若GO(Ik,A)=Ij，置 GOTOk,A=j。 (5)分析表中凡不能用规则(1)(4)填入的空白格均置 为“出错标志”。 表5.5 例5.13 的 LR分析表 p116 状 态态 ACTIONGOTO ab#SB 0s3s412 1acc 2s6s75 3s3S48 4r3r3 5r1 6s6s79 7r3 8r2r2 9r2 5.LR(1)文法 若文法G按构造LR(1)分析表算法构造出来的 分析表不包含多重定义项，则该文法G是 LR(1)文法。 注: 1）每个SLR(1)文法都是LR(1)文法， 反之不一定成立； 2）一个文法的规范LR分析表比其SLR分析 表含有更多的状态。在严重的情况下，状态 数可能成倍增长。因此需要简化。 文法5.9 p113 (0)S S (1)S L=R (2)S R (3)L *R (4)L i (5)R L 例 求LR(1)项目集规范族 S S, # SL=R, # SR, # L*R, =/# L i, =/# RL, # I0初态 简化为 S S,# SL=R,# SR, # L*R, = L i, = RL, # L*R, # L i, # I0初态 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初态 状态态ACTIONGOT