《【考研计算机专业课】天津大学编译原理讲义LALR(1)分析表》由会员分享，可在线阅读，更多相关《【考研计算机专业课】天津大学编译原理讲义LALR(1)分析表（10页珍藏版）》请在金锄头文库上搜索。
1、4.3.5 LALR(1)分析表,对于一种语言，SLR分析表一般要用几百个状态，但若用LR(1)分析表，却要用几千个状态。,一种折衷的方法就是构造LALR分析表，它比规范LR分析表要小得多，能力也差一些，但它却能对付一些SLR所不能解决的冲突问题。,对于同一个文法，LALR分析表和SLR分析表永远具有相同数目的状态。,例，设文法G:,(0) SS (1) SBB,(2) BaB (3) Bb,1. LALR(1)项目集,LR(1)的两个项目集除去搜索符之外都相同，则称两个LR(1)项目集具有相同的心。,具有相同心的项目集称为同心集。,上例中，I4和I7、I3和I6、I8和I9分别为同心集。,一
2、文法的LR(1)项目集规范族合并同心集就得到同一文法的LALR(1)项目集规范族。,(1) 假设LR(1)项目集为: I0，I1，Im，合并同心集以后可得的LALR(1)项目集为: J0，J1，Jn。合并同心集的原则如下:, 设I i0，Ii1，Iik，具有相同的心，其中，项目集的右下角标ij，将I i0，Ii1，Iik合并成一个LALR(1)项目集Ji0。Ji0中任一项目的搜索符集合等于Ii0，Iik中搜索符的并集。, LR(1)项目集导入同心集I i0，Ii1，Iik的弧，现导入合并后的项目集Ji0，弧上标记不变；由同心集I i0，Ii1，Iik导出的弧，改由Ji0导出，弧上标记不变。,上
3、例，I0有弧“a”导入I3，I2有弧“a”导入I6，现改成I0和I2有弧导入JP。,说明: 状态映象函数GO (I，X)仅与项目集的LR(0)项目及文法符号X有关，与搜索符无关。所以，合并同心集后的新项目集导入、导出弧与原LR(1)项目集合规范族的状态映象没有矛盾。,(2) 同心集合并后，会不会引起文法动作的冲突？, 同心集合并后，不可能引起新的归约与移进冲突。,若合并同心集后的项目集有移进归约冲突，那么合并前，至少有一同心集有移进归约冲突。, 合并同心集，可能引起新的归约与归约冲突,2. LALR(1)分析表的构造算法,(1) 任给一文法G，首先构造文法G拓广文法G的LR(1)项目集规范族；,(2) 合并LR(1)项目集的同心集，设合并后的项目集为: C=J0，J1，Jm；,(3) 若不存在语法冲突动作，则按项目集规范族构造分析表。此表为LALR(1)分析表，相应的文法为LALR(1)文法。,LALR(1)项目集规范族,LALR(1)分析表,
