6-LR(1)lhtaw.pptVIP免费

6.4LR(1)和LALR(1)分析规范LR分析例1文法G0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→eI0:S`→．SI1:S`→S．I2:S→a．AdS→．aAdS→a．ecS→．bAcA→．eS→．aecS→．bedI3:S→b．AcI4:I5:S→b．edS→aA．dS→ae．cA→．eA→e．I6:I7:I8:S→bA．cS→be．dS→aAd．A→e．I9:S→aec．I10:S→bAc．I11:S→bed．ACTIONGOTOacebd#SA0S2S311acc2S543S764S85r5r5S9r5r5r5r56S107r7r7r7r7r7S11r78r1r1r1r1r1r19r3r3r3r3r3r310r2r2r2r2r2r211r4r4r4r4r4r4(0）S’→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→e非LR(0),非SLR(1)I5:S→ae．cI7:S→be．dA→e．A→e．S’==>S==>aAd==>aedS’==>S==>bAc==>becS’==>S==>aecS’==>S==>bedae是活前缀be是活前缀aAc不是规范句型,bAd不是规范句型不作无效归约？信息－在特定的规范推导中，哪些输入符号能跟在句柄之后G[S]:若S=>αAω=>αβωr是αβ的前缀，则称r是G的一个活前缀.哪个项目在什么条件下对某个活前缀有效RRRRRRRRRRRR*****例2G[S]:(0)S`→S(1)S→L=R(2)S→R(3)L→*R(4)L→id(5)R→LI0:S'–>•SS–>•L=RS–>•RR–>•LL–>•idL–>•*RI1:S'–>S•I2:S–>L•=RR–>L•I3:S–>R•I4:L–>*•RR–>•LL–>•*RL–>•idI5:L–>id•I6:S–>L=•RR–>•LL–>•*RL–>•idI7:L–>*R•I8:R–>L•I9:S–>L=R•I2:S–>L•=RR–>L•考虑分析表达式id=id时，在工作到I2处已经把第一个id归约到L了,看到下一个输入=要作决策，第一个项目要设置Action[2,=]为S6,即把赋值的其它部分找到.但=也是属于Follow(R)的.第二个项目要用R–>L归约.出现shift-reduce冲突.若将栈顶的符号序列归约到R,会有问题！因为不可能有规范句型以R=…开头(有以*R=...开头的规范句型).SLR（1）的局限follow集包含了在任何句型中跟在R后的符号但没有严格地指出在一个特定的推导里哪些符号跟在R后.所以需要扩充状态以包含更多的信息：follow集的哪些部分才是进到该状态最恰当的归约依据.处在状态2时，试图构建句子有两条路：1.SL=R或2.SRL.如下一符号是=,那就不能用第二个选择，必须用第一个,即移进.只有下一个符号是#时才能归约.尽管=属于Follow(R)，那是因为一个R可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用SRL推导句子时,=不能跟在R后..讨论例2后有以下结果：不是LR(0)文法 I2S→L．=RR→L.中存在移进/归约冲突SLR能否解决I2中的冲突∴FOLLOW（R）={#,=}与{=}交不为空不是SLR（1）文法如早...