编译原理清华大学第7章LR分析法解读.ppt

图 7.8 LR(0)识别G′的活前缀的DFA 如果一个文法的LR(1)分析表不含多重入口时，(或任何一个LR(1)项目集中无移进-归约冲突或归约-归约冲突)则称该文法为LR(1)文法，所构造的相应分析表称为LR(1)分析表，能使用LR(1)分析表的分析器称为LR(1)分析器或称规范的LR分析器。 表 7.11 LR(1)分析表 2 5 8 9 1 Acc r1 r3 r2 S4 S7 S4 r3 S7 r2 S3 S6 S3 r3 S6 r2 0 1 2 3 4 5 6 7 8 9 B S # b a GOTO ACTION 状态 结论: LR(1)文法是无二义的。 LR(1)项目集的构造对某些同心集的分裂可能使状态数目剧烈的增长。 一个文法是LR(0)文法一定也是SLR(1)文法，也是LR(1)文法。反之则不一定成立。 7.5 LALR(1) 分析 LR(1)分析表的构造，对归约时向前查看的符号由SLR(1)用的FOLLOW集改为向前有哪些信誉好的足球投注网站符，计算方法比较确切，对文法放宽了要求，也就是适应的文法类广，因此，可以解决SLR(1)方法解决不了的问题。 但是，由于它的构造对某些同心集的分裂可能对状态数目引起剧烈的增长，从而导致存储容量的急剧增加，也使应用受到一定的限制。 为了克服LR(1)的这种缺点，采用对LR(1)项目集规范族合并同心集的方法，若合并同心集后不产生新的冲突，则为LALR(1)项目集。它的状态个数与LR(0) 、SLR(1)的相同。 例如：我们分析图7.8中的项目集可发现同心集如下：　　I3： B→a·B,a/b 　　　　I6：B→a·B,#　　　　 B→·aB,a/b 　　　 　　 B→·aB,#　　　　 B→·b,a/b 　　　　　　 B→·b,#　　I4： B→b·,a/b 　　　　 I7：B→b·,#　　I8： B→aB·,a/b 　　　　I9：B→aB·,# 即I3和I6，I4和I7，I8和I9分别为同心集，将同心集合并后为：　　I3,I6： B→a·B,a/b/#　　　　　　B→·aB,a/b/#　　　　　　B→·b,a/b/#　　I4,I7： B→b·，a/b/#　　I8,I9： B→aB·，a/b/#　　同心集合并后仍不包含冲突，因此该文法满足LALR(1) 要求。 合并同心集有几个问题需要说明： (1)同心集是指心相同的项目集合并在一起，因此同心集合并后心仍相同，只是超前有哪些信誉好的足球投注网站符集合为各同心集超前有哪些信誉好的足球投注网站符集合的并集。 (2)对于合并同心集后的项目集的转换函数仍为同心集，因为相同的心之转换函数的心仍相同，即仍属同心集，所以合并同心集后转换函数为自动合并，如例中I3和I6为同心集，它们的转换函数分别为： I3： GO(I3，a)= I3 I6： GO(I6，a)= I6 　　　　 GO(I3，b)= I4 GO(I6，b)= I7 　　　 　GO(I3，B)= I8 GO(I6，B)= I9 　　然而，I3和I6，I4和I7，I8 和I9分别都为同心集。 (3)若文法是LR(1)文法，合并同心集后若有冲突也只可能是归约-归约冲突，而不可能产生移进-归约冲突。 (4)合并同心集后对某些错误发现的时间会产生推迟现象，但错误的出现位置仍是准确的。这意味着LALR(1)分析表比LR(1)分析表对同一输入串的分析可能会有多余归约。 现在构造上述文法的LALR(1)分析表，对于一个文法是否为LALR(1)文法，通常所采用的方法是首先构造它的LR(1)项目集族，若不含任何冲突，则合并同心集，若仍不产生归约-归约冲突，则该文法便是LALR(1)文法，那么就可以根据合并同心集后的项目集族构造该文法的LALR(1)分析表，其构造步骤如下： 构造文法G的LR(1)项目集族，C={I0，I1，…，In}。 (2) 合并所有的同心集，使C变为C′={J0，J1，…，Jm}，便是LALR(1)的项目集族。 　　由于构造LALR(1)分析表，通常所采用的方法是首先构造它的LR(1)项目集族，若不含任何冲突，则合并同心集，若仍不产生归约-归约冲突，则该文法便是LALR(1)文法，再根据合并同心集后的项目集族构造该文法的LALR(1)分析表。所以LALR(1)分析表的构造除了步骤（2）外，其余步骤与LR(1)分析表的构造相同。 3) 由C′构造动作(ACTION)表，其方法与LR(1)分析表的构造相同。 a)若[A→α·aβ,b]∈Jk，且GO(Jk,a)＝Jj， 其中a∈VT，则置ACTION[k,a]=Sj，其Sj的含义是把输入符号a和状态j分别移入文法符号栈和状态栈。 b) 若项目[A→α·,a]属于