《编译原理(第2版)6-lr(1)》由会员分享，可在线阅读，更多相关《编译原理(第2版)6-lr(1)（31页珍藏版）》请在金锄头文库上搜索。
1、6.4 LR(1)和LALR(1)分析 规范LR分析例1文法G 0）SS (1) SaAd (2) SbAc(3) Saec (4) Sbed (5) AeI0: SS I1: SS I2: SaAd SaAd Saec SbAc Ae Saec Sbed I3: SbAc I4: I5: Sbed SaAd Saec Ae Ae I6: I7: I8: SbAc Sbed SaAdAe I9: Saec I10: SbAc I11: Sbed ACTION GOTOa c e b d # S A 0 S2 S3 1 1 acc 2 S5 4 3 S7 6 4 S8 5 r5 r5S9 r5
2、r5 r5 r5 6 S10 7 r7 r7 r7 r7 r7 S11 r7 8 r1 r1 r1 r1 r1 r1 9 r3 r3 r3 r3 r3 r3 10 r2 r2 r2 r2 r2 r2 11 r4 r4 r4 r4 r4 r4( 0）SS (1) SaAd (2) SbAc(3) Saec (4) Sbed (5) Ae 非 LR(0),非SLR(1)I5: S aec I7: S bed A e A e S=S=aAd=aed S=S=bAc=bec S=S=aec S=S=bed ae是活前缀 be是活前缀aAc不是规范句型 , bAd不是规范句型不作无效归约 ？信息 在特定
3、的规范推导中，哪些输入符号 能跟在句柄之后 GS: 若S = A = r是的前缀，则称r是G的一个活前缀. 哪个项目在什么条件下对某个活前缀有效RRR RRRRRRRRR*例2 GS: (0) SS (1) SL=R (2) SR (3) L *R (4) Lid (5) RLI0: S SS L = RS RR LL id L *RI1: S SI2: S L = R R LI3: S RI4: L *RR LL *RL id I5: L id I6: S L =RR LL *RL idI7: L *R I8: R L I9: S L=RI2: S L = RR L 考虑分析表达式 id =
4、 id时，在工作到 I2 处已经 把第一个 id 归约到 L了, 看到下一个输入 = 要作决策，第一个项目要设置 Action2,= 为 S6, 即把赋值的其它部分找到. 但 =也是属于 Follow(R) 的. 第二个项目要用 RL归约.出 现 shift-reduce 冲突.若将栈顶的符号序列归约到 R,会有问题！因 为不可能有规范句型以 R = 开头 (有以 *R = . 开头的规范句型).SLR（1）的局限follow 集包含了在任何句型中跟在 R 后的符号但没 有严格地指出在一个特定的推导里哪些符号跟在 R后.所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状
5、态最恰当的归约依据.处在状态 2时，试图构建句子有两条路：1.S L = R 或 2.S R L. 如下一符号是 =, 那就不能用第二个选择，必须用 第一个,即移进. 只有下一个符号是#时才能归约. 尽 管 = 属于 Follow(R) ，那是因为一个 R 可以出现 在别的上下文中，在现在这个特定的情况，它不 合适,因为在用S R L推导句子时, = 不能跟 在R后.讨论例2后有以下结果：v不是LR(0)文法 I2 SL=R RL.中存在移进/ 归约冲突vSLR能否解决I2中的冲突FOLLOW（R）=#,=与=交不为空 不 是SLR（1）文法v 如早有信息告知： 若用 RL 归约 则 形成R=
6、 而 R=不是活前缀，SLR（1）的局限在SLR 分析中,若项目集Ik含有项目 A .,那么在相应的状态 下,只要当前输入符号afollow(A) 集,就确定采用A 进行 归约.但在某些情况下,当状态k呈现于栈顶时,栈内的串所 构成的活前缀未必允许把归约为A,.因为可能没有一个规 范句型含有前缀Aa.即在这种情况下,用A 归约未必有效 . . 所以需要扩充状态以包含更多的信息：follow 集的哪些部 分 才是进到该状态最恰当的归约依据.必须重新定义项目. LR（1）方法的思路: 若 A .B I 则 B . I （ B 是一产生式）把FIRST（ ）中的符号作为用B 归约的搜索符，向前搜索符
7、 .LR（1）项目( 配置）的一般形式 A . ， a a 称作该项目( 配置） 的向前搜索符（ lookahead ） 向前搜索符（ lookahead ）只对圆点在最后的项目起 作用A , a .意味着处在栈中是 的相应状态，但只有当下一个 输入符是a时才能进行归约. a 是一个终结符，或是 输入结束标记# 有多个向前搜索符，比如a,b,c时，可写作 A u, a/b/cLR(0)项目对某个活前缀有效定义 项目A 1.2对活前缀r=1是有效的,如果存在 一个规范推导S = A =12 若项目A .B对活前缀r=是有效的且B是 一个产生式,则项目B.对r=也是有效的. 因为由假定,存在一个规
8、范推导 S = A = B 设 =,则对B有规范推导 S = A=B=B = 于是项目B.对r=也是有效的R*R*R* R*R*LR(1)项目对某个活前缀有效定义 一个LR(1)项目A .,a对活前缀r=是 有效的,如果存在一个规范推导S = A = 其中或的第一个符号为a,或=而a为# 若LR(1)项目A .B,a对活前缀r=是有 效的且B是一个产生式,则项目B.,b 对r=也是有效的.其中b或者是从推出的 第一个终结符,或者= 而b=a,两者结合在 一起,即:b FIRST(a)R*构造LR(1)项目集规范族和G0函数closure(I)按如下方式构造 (1) I的任何项目属closure
9、(I)； (2)若A1B2，aclosure(I)，B是一产生式，那么 对于FIRST(2a)中的每个终结符b，如果B,b不在 closure(I)中，则把它加进去； (3)重复（1）（2），直至closure(I)不再增大。 GO函数： 若I是一个项目集，X是一个文法符号 GO(I, X)= closure(J) 其中 J= 任何形如AX,a的项目A.X,aILR(I)项目规范族C的构造算法类同LR(0)的，只是初始时： C= closure(SS,#);例1的LR(1)项目集规范族I0: SS, # I5: S aec,#S aAd, # A e,d S bAc, # I6: S bAc, # S aec, # I7: S bed, # S bed, # A e,c I1: S S,# I8: S aAd, # I2: S aAd, # I9: S aec, # S aec, # I10: S bAc, # A e, d I11: S bed, # I3: S bAc, # S bed, # Ae,c I4: S aAd, # 规范的LR(1)分析表的构造假定LR(1)项目集规范族C=I0, I1,，In，令每个项目集Ik的下标
