最新【考研计算机专业课】天津大学 编译原理讲义 LALR(1)分析表(共11张PPT课件).pptx

4.3.5 LALR(1)分析分析(fnx)表表对于一种语言，对于一种语言，SLR分析表分析表一般一般(ybn)要用几百个状态，但若要用几百个状态，但若用用LR(1)分析表分析表，却要用几千个状态。，却要用几千个状态。一种折衷的方法就是构造一种折衷的方法就是构造LALR分析分析(fnx)表表，它比规范，它比规范LR分析分析表要小得多，能力也差一些，但它却能对付一些表要小得多，能力也差一些，但它却能对付一些SLR所不所不能解决的冲突问题。能解决的冲突问题。对于同一个文法，对于同一个文法，LALR分析表和分析表和SLR分析表永远具有相同分析表永远具有相同数目的状态。数目的状态。第一页，共十一页。例例，设文法，设文法(wnf)G:(0) SS (1) SBB(2) BaB BaB (3) BbBb第二页，共十一页。1. LALR(1)项目项目(xingm)集集 LR(1)的两个项目集除去搜索符之外都相同的两个项目集除去搜索符之外都相同(xin tn)，则，则称两个称两个LR(1)项目集具有相同项目集具有相同(xin tn)的的心心。具有相同心的项目集称为具有相同心的项目集称为(chn wi)同心集同心集。上上例例中，中，I4和和I7、I3和和I6、I8和和I9分别为同心集。分别为同心集。一文法的一文法的LR(1)项目集规范族合并同心集就得到同一文项目集规范族合并同心集就得到同一文法的法的LALR(1)项目集规范族。项目集规范族。 第三页，共十一页。(1) 假设假设(jish)LR(1)项目集为项目集为: I0，I1，Im，合并同心集，合并同心集以后可得的以后可得的LALR(1)项目集为项目集为: J0，J1，Jn。合并同心集。合并同心集的的原则原则如下如下: 设设I i0，Ii1，Iik，具有相同的心，其中，项目集的右下角标，具有相同的心，其中，项目集的右下角标ij，将将I i0，Ii1，Iik合并成一个合并成一个LALR(1)项目集项目集Ji0。Ji0中任一项目的搜索中任一项目的搜索(su su)符集合等于符集合等于Ii0，Iik中搜索符的并集。中搜索符的并集。 上上例例，I3和和I6合并同心集后为合并同心集后为: : J3BaB，a/b/#BaB，a/b/#Bb，a/b/#第四页，共十一页。 LR(1)(1)项目集导入同心集项目集导入同心集I i0，Ii1，Iik的弧，现导入合并的弧，现导入合并(hbng)(hbng)后的项目集后的项目集Ji0，弧上标记不变；由同心集，弧上标记不变；由同心集I i0，Ii1，Iik导出的弧，改由导出的弧，改由Ji0导出，弧上标记不变。导出，弧上标记不变。 上上例例，I0有弧有弧“a”导入导入I3，I2有弧有弧“a”导入导入I6，现改成，现改成(i chn)(i chn)I0和和I2有弧导入有弧导入JP。 说明说明: : 状态映象函数状态映象函数GO ( (I，X) )仅与项目集的仅与项目集的LR(0)(0)项目及文法符号项目及文法符号X有有关，与搜索符无关。所以，合并同心集后的新项目集导入、导出弧关，与搜索符无关。所以，合并同心集后的新项目集导入、导出弧与原与原LR(1)(1)项目集合项目集合(jh)(jh)规范族的状态映象没有矛盾。规范族的状态映象没有矛盾。 第五页，共十一页。( (2) ) 同心集合并后，会不会同心集合并后，会不会(b hu)(b hu)引起文法动作的冲突？引起文法动作的冲突？ 同心集合同心集合(jh)(jh)并后，不可能引起新的并后，不可能引起新的归约与移进归约与移进冲突。冲突。 所谓所谓LR(1)(1)项目集有项目集有移进归约移进归约冲突是指此项目集冲突是指此项目集 中，中，a1 am X1Xn 若合并同心集后的项目若合并同心集后的项目(xingm)(xingm)集有集有移进归约移进归约冲突，那么合并前，至少有一同冲突，那么合并前，至少有一同心集有心集有移进归约移进归约冲突。冲突。 第六页，共十一页。 合并同心集，可能合并同心集，可能(knng)(knng)引起新的归约与归约冲突引起新的归约与归约冲突 例例，文法，文法G: (0) SS (1) SaAd|bBd|bAe|aBe(2) Ac (3) Bc 的部分的部分LR(1)(1)项目集为项目集为 I3和和I5合并得合并得: : 此项目集显然有归约冲突。此项目集显然有归约冲突。 第七页，共十一页。2. LALR(1)分析表的构造分析表的构造(guzo)(guzo)算法算法 (1)(1) 任给一文法任给一文法G，首先，首先(shuxin)(shuxin)构造文法构造文法G拓广文法拓广文法G的的LR(1)(1)项目集规范族；项目集规范族； ( (2) ) 合并合并(hbng)(hbng)LR(1)(1)项目集的同心集，设合并后的项目集项目集的同心集，设合并后的项目集为为: : C=J0，J1，Jm；( (3) ) 若不存在语法冲突动作，则按项目集规范族构造分析表。若不存在语法冲突动作，则按项目集规范族构造分析表。此表为此表为LALR(1)分析表，相应的文法为分析表，相应的文法为LALR(1)文法。文法。 第八页，共十一页。LALR(1)(1)项目项目(xingm)(xingm)集规范族集规范族 例例，设文法，设文法G:(0) SS (1) SBB(2) BaB BaB (3) BbBb第九页，共十一页。LALR(1)(1)分析分析(fnx)(fnx)表表 状态状态ACITON表表GOTO表表 ab#SB0S3S4 121 acc 2S3S4 53S3S4 64r3r3r3 5 r1 6r2r2r2 第十页，共十一页。内容(nirng)总结4.3.5 LALR(1)分析表。对于同一个文法，LALR分析表和SLR分析表永远具有相同数目的状态。具有相同心的项目集称为同心集。上例中，I4和I7、I3和I6、I8和I9分别为同心集。设I i0，Ii1，。BaB，a/b/#。Bb，a/b/#。由同心集I i0，Ii1，。所以，合并同心集后的新项目集导入、导出弧与原LR(1)项目集合规范(gufn)族的状态映象没有矛盾。Xn。r2第十一页，共十一页。