第7单元 lr分析法.pptVIP

第7章　LR分析法 算符优先分析法不是规范归约，它归约的是最左素短语。LR分析法是规范归约，它每次归约的是句柄。 第5、6、7章小结 几种语法分析方法 自上而下 递归下降分析法 预测（LL(1)）分析法 自下而上 算符优先分析法 LR分析法：LR(0)、 SLR(1)、 LR(1)、 LALR(1) 求合并后的转移函数 Go (I411,i) =go(I4,i)?go(I11,i) =I5 ?I12 =I512 Jk=I1 ?I2 ?… ?It GO(Jk,x)=GO(I1,x) ?GO(I2,x) ?… ?GO(It,x) =Ij I0: S’?.S,# S?.L=R, # S?.R, # L?.*R, =/# L?.i, =/# R?.L, # I1: S’?S. ,# S I2: S?L.=R ,# R?L. ,# L I3: S?R. ,# R I411: L?*.R ,=/# R?.L , =/# L?.*R, =/# L?.i , =/# * I512: L?i., =/# i i * I6: S?L=.R ,# R?.L,# L?.*R,# L?i,# = I713: L?*R.,=/# R I810: R?L.,=/# L I9: S?L=R.,# R * L i R 合并后可能出现新的冲突 归约与归约的冲突 Ex: 合并后： Ii: [A?? . , a] [B?? . , b] Ij: [A?? . , b] [B?? . , a] Iij: [A?? . , a/b] [B?? . , a/b] 产生归约与归约的冲突！ 移进与归约的冲突 Ex:设合并后有移归冲突，则必定形如： 那么合并前应可写成： Iij: [A?? . , a/a’] [B?? . a ?, c/c’] Ii: [A?? . , a] [B??.a ?, c] Ij: [A?? . , a’] [B?? . a ?, c’] 可以看出Ii中已经存在移归冲突，但对LR(1)文法来说是不可能存在的。所以合并后不会出现移归冲突。 7.6.2 构造LALR(1)分析表 拓广文法 求LR（0）项目 求LR（1）项目集 由上作DFA 合并同心集 求GO，改写DFA 由DFA填写分析表（若表中无归约与归约冲突，则该文法为LALR（1）文法）。 r3 13 r4 12 13 10 S11 S12 11 r5 10 r1 9 r5 r5 810 r3 R3 713 9 810 S411 S512 6 r4 R4 512 713 810 S411 S512 411 r2 3 S6 2 Acc 1 3 2 1 S4 S5 0 R L S # = * i S r1 9 r5 r5 8 r3 r3 7 9 8 S4 S5 6 r4 r4 5 7 8 S4 S5 4 r2 3 S6 2 Acc 1 3 2 1 S4 S5 0 R L S # = * i S 最终得如下LALR（1）分析表： 第17讲 上一讲复习 LR分析法的分析过程 LR（0）分析表的构造 基本思想 规范句型活前缀的概念 构造识别规范句型活前缀的DFA的方法 分析表的构造 LR（0）分析法的局限性 解：第一步，拓广文法G为G’： 0：E’?E 1：E?E+T 2：E?T 3：T?T*F 4：T?F 5：F?(E) 6：F?I Ex:已知文法G： E?E+T E?T T?T*F T?F F?(E) F?I　　　　请构造它的LR(0)分析表。 第二步，求DFA（综合前述步骤二、三、四） I0： E’?.E E?.E+T E?.T T?.T*F T?.F F?.(E) F?.i I1： E’?E. E?E.+T I2: E?T. T?T.*F I3: T?F. I4: F?(.E) E?.E+T E?.T T?.T*F T?.F F?.i I5: F?i. E T ( F i I7: T?T*.F F?.(E) F?.i * 第三步，填表 … … r6 r6 r6 r6 r6 r6 5 4 3 r2 r2 r2 r2 S7 r2 r2 2 1 0 # ) ( * + i … 3 2 1 F T E 0：E’?E 1：E?E+T 2：E?T 3：T?T*F 4：T?F 5：F?(E) 6：F?i 冲突！！ 7.4 　SLR(1)分析法 7.4.1 发生冲突的原因 I0： E’?.E E?.E+T E?.T T?.T*F T?.F F?.(E) F?.i I1： E’?E. E?E.+T I2: E?T. T?T.*F E T 对输入串中当前所有的终结符VT进行归约。 对输入串中当前的终结符 * 号进行移进。 矛盾解