编译原理第4章7.ppt

1、，4.5.5 LALR(1)分析法，LR(1)分析法可以解决SLR(1)法难以解决的移位约简或约简冲突，但对于相同的语法，当搜索者不同时，同一项集被分割成多个项集，这导致状态数急剧增加，导致时间和内存空间急剧增加，从而使其应用受到一定限制。4.5.5 LALR(1)分析法是SLR(1)分析法和LR(1)分析法之间的一种语法分析方法，能够解决SLR(1)分析法不能解决的冲突行为，其分析表的状态数与SLR(1)分析表的状态数一样多。LALR(1)分析方法的基本思想是将LR(1)项集规范族中的所有同心项集合并为一个，以减少项集的数量。4.5.5 LALR(1)分析方法，所谓同心LR(1)项集是指在两

2、个LR(1)项集中，除了不同的搜索者之外，核心部分是相同的。例如，通过分析先前语法的LR(1)项集，我们可以发现同心集如下：0.ss3.l * r1.s l=r4.li2.s r5.r l，i4和I11，I5和I12，I7和I13，I8和I10，除了搜索字符的差异。将同心集组合成：4.5.5 LALR(1)分析方法、4.5.5 LALR(1)分析方法，我们可以看到，同心集合并后的项集的核心部分是不变的，只搜索匹配和合并。同心集合并后的项集的变换函数是GO(I，X)本身的合并，因为同一颗心的变换函数仍然属于同心集。例如，go (i4，11，I)=go (i4，I) go (i11，I)=i5，1

3、2，go (i4，11，r)=go (i11，r)=i7，13，go()。重要的是要指出，如果语法是LR(1)语法，也就是说，在其LR(1)项集中没有动作冲突。如果在合并同心集合后有冲突，它只能是一个约简冲突，而不是一个移动的约简冲突。LR(1)文法的项集Ik和Ij被假定为同心集，其中Ik=A，a1 Ba，b1，Ij=A，a2 Ba，b2，合并同心集后的项集，Ikj=a，a1/a2ba，B1/B2，4 . 5 . 5 LR(1)分析法，因为它是假定的，但可能存在约简冲突。例如，我们可以想象有两个同心LR(1)项集：4.5.5 LALR(1)分析方法。现在我们可以根据同心集合并后的项集构造LAL

4、R (1)语法分析表，其构造方法如下：Ik=A，A，B，B，Ij=A，B，B，A，B，B，B，B，4.5.5 LALR(1)分析方法，2。如果LR(1)项集族中没有冲突项集，则所有同心集被合并以构造LALR(1)项集族语法。1.构造扩展文法g的LR(1)项集.例如，上例中通过将同心集与中文方法G的LALR(1)项集族相结合而构建的LALR(1)项集族如下图所示。4.5.5 LALR (1)分析方法，4。LALR(1)项集以与LR(1)分析表相同的方式构造该语法的LALR(1)分析表。由图构成的LALR(1)语法分析表如下表所示。如果LALR(1)项集族中不存在约简冲突，则该语法为LALR(1)

5、语法。对于示例中的语法，因为在合并同心集之后没有缩减冲突，所以语法是LALR(1)语法。4.5.5 LALR(1)分析方法，对于给定的语法G，其LALR(1)分析表比LR(1)分析表具有更少的状态(在这种情况下，LALR(1)的状态数比LR(1)分析表减少了4)，但是当分析语法G中有错误的符号串时，LALR(1，4.5.6对于二进制语法的应用，其对应的LR分析表必须包含多个定义的元素。然而，对于一些歧义语法，足够的歧义规则被添加到具有多个定义的LR分析表中，从而可以构建优于相应的非歧义语法的LR分析器。任何歧义语法都不是LR语法。我们知道4.5.6适用于歧义语法，EE E | E*E | (E

6、) | id，相应的非歧义语法是：EE T | T，TT*F | F，F(E) | id，例如，考虑算术表达式2。二进制语法的LR分析表中的状态数肯定比非二进制语法的少，因为非二进制语法包含规则ET和TF，在右边只有一个非终结符，占用了状态，降低了分析器的分析效率。与它们相比，二进制语法的优势在于：如果您需要更改操作符的优先级或组合，您不需要更改语法本身。4.5.6二进制语法的应用，现在我们构造如下图所示的算术表达式二进制语法的LR(0)项集规范族：4.5.6二进制语法的应用从图中可以看出，I1、I7和I8州存在移动约简冲突，I1的冲突可以用SLR(1)解决。对于I7和I8:因为FOLLER(E)，*=，也就是说，当输入符号是$，接受它，当它是或*时移入。FOUND(E)，*=$，*，)，*，由于将，4.5.6应用于二进制语法，I7和I8中的冲突不能用SLR(1)方法解决，也不能用其他LR(K)方法解决，但我们可以用*的优先级和组合来解决这样的冲突。4.5.6，然后在I7中，因为*具有更高的优先级，所以状态7面临*移动，并且因为它服从左组合，所以它被EEE减少。如果我们规定*的优先级高于，并且它们都服从左组合，4.5.6。二进制语法的应用，在I8中，因为*优先于并且*服从左组合，所以状态