《编译原理(第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) Ae,I0: SS I1: SS I2: SaAd SaAd Saec SbAc Ae Saec SbedI3: SbAc I4: I5: Sbed SaAd Saec Ae Ae I6: I7: I8: SbAc Sbed SaAd Ae I9: Saec I10: SbAc I11: Sbed,( 0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae非 LR(0),非SLR(1),I5: S ae
2、c I7: S bed A e A eS=S=aAd=aed S=S=bAc=bec S=S=aec S=S=bed ae是活前缀 be是活前缀 aAc不是规范句型 , bAd不是规范句型 不作无效归约 ？信息 在特定的规范推导中，哪些输入符号能跟在句柄之后GS:若S = A = r是的前缀，则称r是G的一个活前缀. 哪个项目在什么条件下对某个活前缀有效,R,R,R,R,R,R,R,R,R,R,R,R,*,*,*,*,*,例2 GS:(0) SS (1) SL=R (2) SR(3) L *R (4) Lid (5) RL,I0: S S S L = R S R R L L id L *RI1
3、: S SI2: S L = R R LI3: S R,I4: L *R R L L *R L idI5: L idI6: S L =R R L L *R L idI7: L *RI8: R LI9: S L=R,I2: S L = R R L,考虑分析表达式 id = id时，在工作到 I2 处已经把第一个 id 归约到 L了, 看到下一个输入 = 要作决策，第一个项目要设置 Action2,= 为S6, 即把赋值的其它部分找到. 但 =也是属于 Follow(R) 的. 第二个项目要用 RL归约.出现 shift-reduce 冲突. 若将栈顶的符号序列归约到 R,会有问题！因为不可能有规
4、范句型以 R = 开头 (有以 *R = . 开头的规范句型).,SLR（1）的局限,follow 集包含了在任何句型中跟在 R 后的符号但没有严格地指出在一个特定的推导里哪些符号跟在 R后.所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 处在状态 2时，试图构建句子有两条路： 1.S L = R 或 2.S R L. 如下一符号是 =, 那就不能用第二个选择，必须用第一个,即移进. 只有下一个符号是#时才能归约. 尽管 = 属于 Follow(R) ，那是因为一个 R 可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用S R L推
5、导句子时, = 不能跟在R后.,.,讨论例2后有以下结果：不是LR(0)文法 I2 SL=R RL.中存在移进/归约冲突SLR能否解决I2中的冲突 FOLLOW（R）=#,=与=交不为空 不是SLR（1）文法 如早有信息告知： 若用 RL 归约 则形成R= 而 R=不是活前缀，,SLR（1）的局限,在SLR 分析中,若项目集Ik含有项目 A .,那么在相应的状态下,只要当前输入符号afollow(A) 集,就确定采用A 进行归约.但在某些情况下,当状态k呈现于栈顶时,栈内的串所构成的活前缀未必允许把归约为A,.因为可能没有一个规范句型含有前缀Aa.即在这种情况下,用A 归约未必有效. 所以需要
6、扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 必须重新定义项目.LR（1）方法的思路:若 A .B I则 B . I（ B 是一产生式）把FIRST（ ）中的符号作为用B 归约的搜索符，向前搜索符 .,LR（1）项目( 配置）的一般形式 A . ， a a 称作该项目( 配置） 的向前搜索符（ lookahead ）向前搜索符（ lookahead ）只对圆点在最后的项目起作用 A , a.意味着处在栈中是 的相应状态，但只有当下一个输入符是a时才能进行归约. a 是一个终结符，或是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作 A u, a
7、/b/c,LR(0)项目对某个活前缀有效,定义项目A 1.2对活前缀r=1是有效的,如果存在一个规范推导S = A =12 若项目A .B对活前缀r=是有效的且B是一个产生式,则项目B.对r=也是有效的.因为由假定,存在一个规范推导S = A = B 设 =,则对B有规范推导S = A=B=B = 于是项目B.对r=也是有效的,LR(1)项目对某个活前缀有效,定义一个LR(1)项目A .,a对活前缀r=是有效的,如果存在一个规范推导S = A = 其中或的第一个符号为a,或=而a为#若LR(1)项目A .B,a对活前缀r=是有效的且B是一个产生式,则项目B.,b对r=也是有效的.其中b或者是从
8、推出的第一个终结符,或者= 而b=a,两者结合在一起,即:b FIRST(a),构造LR(1)项目集规范族和G0函数,closure(I)按如下方式构造(1) I的任何项目属closure(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)的，只是初始时：
9、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,，
10、In，令每个项目集Ik的下标k 为分析器的一个状态，G 的LR（1）分析表含有状态0，1，n。1.令那个含有项目SS ，#的Ik的下标k为状态0（初态）.ACTION表和GOTO表可按如下方法构造2.若项目A,b属于Ik, 那么置ACTIONk, b为“用产生式A进行规约”，简记为“rj”;(假定A为文法G的第j个产生式)3.若项目Aa,b属于Ik且GO (Ik, a)= Ij,则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”;4.若项目SS,#属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”; 5.若GO (Ik, A)= Ij, A为非终结符，则置GOT
11、O(k, A)=j;分析表中凡不能用规则1至5填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张规范的LR(1)分析表。具有规范的LR(1)表的文法G称为一个LR（1）文法。,LR(1) 文法满足下面两个条件1.如果一个项目集里有项目 A uxv , a ， x是终结符，那就不会有项目B u, x 2.项目集里所有归约项目 的向前搜索符不相交，即不能同时含有项目 A u, a 和B v , a,LR（K）分析,LR（K）项目 A . ， a1 a2 aK a1 a2 aK 向前搜索符串移进项目 A . a， a1 a2 aK 待约项目 A . B， a1 a2 aK 归约项目 A . ， a1 a2 aK ,
