【精品】【考研计算机专业课】天津大学 编译原理讲义 lalr(1)分析表（可编辑.ppt

【考研计算机专业课】天津大学 编译原理讲义 LALR(1)分析表例例，设文法，设文法G:(0)SS(1)SBB(2)BaB BaB (3)BbBb1.LALR(1)项目集项目集LR(1)的两个项目集除去搜索符之外都相同，则称两的两个项目集除去搜索符之外都相同，则称两个个LR(1)项目集具有相同的项目集具有相同的心心。具有相同心的项目集称为具有相同心的项目集称为同心集同心集。上上例例中，中，I4和和I7、I3和和I6、I8和和I9分别为同心集。分别为同心集。一一文文法法的的LR(1)项项目目集集规规范范族族合合并并同同心心集集就就得得到到同同一一文法的文法的LALR(1)项目集规范族。项目集规范族。(1)假设假设LR(1)项目集为项目集为:I0，I1，Im，合并同心集，合并同心集以后可得的以后可得的LALR(1)项目集为项目集为:J0，J1，Jn。合并同。合并同心集的心集的原则原则如下如下:设设Ii0，Ii1，Iik，具有相同的心，其中，项目集的右，具有相同的心，其中，项目集的右下角标下角标ij，将，将Ii0，Ii1，Iik合并成一个合并成一个LALR(1)项目集项目集Ji0。Ji0中任一项目的搜索符集合等于中任一项目的搜索符集合等于Ii0，Iik中搜索符的并集。中搜索符的并集。上上例例，I3和和I6合并同心集后为合并同心集后为:J3BaB，a/b/#BaB，a/b/#Bb，a/b/#LR(1)(1)项目集导入同心集项目集导入同心集Ii0，Ii1，Iik的弧，现导入的弧，现导入合并后的项目集合并后的项目集Ji0，弧上标记不变；由同心集，弧上标记不变；由同心集Ii0，Ii1，Iik导出的弧，改由导出的弧，改由Ji0导出，弧上标记不变。导出，弧上标记不变。上上例例，I0有弧有弧“a”导入导入I3，I2有弧有弧“a”导入导入I6，现改成，现改成I0和和I2有弧导入有弧导入JP。说明说明:状态映象函数状态映象函数GO(I，X)仅与项目集的仅与项目集的LR(0)(0)项目及文法项目及文法符号符号X有关，与搜索符无关。所以，合并同心集后的新项目集导有关，与搜索符无关。所以，合并同心集后的新项目集导入、导出弧与原入、导出弧与原LR(1)(1)项目集合规范族的状态映象没有矛盾。项目集合规范族的状态映象没有矛盾。2.LALR(1)分析表的构造算法分析表的构造算法(1)(1)任给一文法任给一文法G，首先构造文法，首先构造文法G拓广文法拓广文法G的的LR(1)(1)项目集规范族；项目集规范族；(2)合并合并LR(1)(1)项目集的同心集，设合并后的项目集为项目集的同心集，设合并后的项目集为:C=J0，J1，Jm；(3)若不存在语法冲突动作，则按项目集规范族构造分若不存在语法冲突动作，则按项目集规范族构造分析表。此表为析表。此表为LALR(1)分析表，相应的文法为分析表，相应的文法为LALR(1)文法。文法。LALR(1)(1)项目集规范族项目集规范族例例，设文法，设文法G:(0)SS(1)SBB(2)BaB BaB (3)BbBbLALR(1)(1)分析表分析表状态状态ACITON表表GOTO表表ab#SB0S3S4121acc2S3S453S3S464r3r3r35r16r2r2r2