编译原理 第6-2章(清华大学).ppt

《编译原理 第6-2章(清华大学).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SLR（1）的局限例6.5：文法G:（0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→eLR(0)项目集规范族：I0:S`→．SI1:S`→S．I2:S→a．AdS→．aAdS→a．ecS→．bAcA→．eS→．aecS→．bed?SLR0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→eI3: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

2、．I11:S→bed．ACTIONGOTOacebd#SA0S2S311acc2S543S764S85r5r5S9r5r5r5r56S107r7r7r7r7r7S11r78r1r1r1r1r1r19r3r3r3r3r3r310r2r2r2r2r2r211r4r4r4r4r4r4（0）S`→S(1)S→aAd(2)S→bAc(3)S→aec(4)S→bed(5)A→eI5:S→ae．cI7:S→be．dA→e．A→e．S`==>S==>aAd==>aedS`==>S==>bAc==>becS`==>S==>aecS`==>S==>bed？信

3、息在特定的规范推导中，哪些输入符号能跟在句柄之后G[S]:若S=>αAω=>αβωr是αβ的前缀，则称r是G的一个活前缀.哪个项目在什么条件下对某个活前缀有效RRRRRRRRRRRR例6.6G[S]:(0)S`→S(1)S→L=R(2)S→R(3)L→*R(4)L→id(5)R→LLR(0)项目集规范族I0:S'–>•SI5:L–>id•S–>•L=RS–>•RI6:S–>L=•RL–>•*RR–>•LL–>•idL–>•*RR–>•LL–>•idI1:S'–>S•I7:L–>*R•I2:S–>L•=RI8:R–>L•R–>L•I9:

4、S–>L=R•I3:S–>R•I4:L–>*•RR–>•LL–>•*RL–>•idI2:S–>L•=RR–>L•考虑分析表达式id=id时，在工作到I2处已经把第一个id归约到L了,看到下一个输入=要作决策，第一个项目设置Action[2,=]为S6,即把赋值的其它部分找到.但=也是属于Follow(R)的.第二个项目要用R–>L归约.出现shift-reduce冲突.SLR分析程序没有记住足够的左文以决定当见到一个能归约到L的串而在输入中碰上=时会发生什么.虽然在栈顶的符号序列可以归约到R,但我们不能要这个选择，因为不可能有规范句型以

5、R=…开头(有以*R=...开头的规范句型).SLR（1）的局限follow集包含了在任何句型中跟在R后的符号但没有严格地指出在一个特定的推导里哪些符号跟在R后.所以需要扩充状态以包含更多的信息：follow集的哪些部分才是进到该状态最恰当的归约依据.处在状态2时，试图构建句子有两条路：1.SL=R或2.SRL.如下一符号是=,那就不能用第二个选择，必须用第一个,即移进.只有下一个符号是#时才能归约.尽管=属于Follow(R)，那是因为一个R可以出现在别的上下文中，在现在这个特定的情况，它不合适,因为在用SRL推导句子时,=不

6、能跟在R后..讨论例6.6后有以下结果：不是LR(0)文法∵I2S→L．=RR→L.中存在移进/归约冲突SLR能否解决I2中的冲突∴FOLLOW（R）={#,=}与{=}交不为空不是SLR（1）文法想早知信息.若用R→L归约则形成R=…而R=不是活前缀LR（1）方法若A.BI则B.（B是一产生式）I把FIRST（）中的符号作为用B归约的搜索符，向前搜索符LR（1）项目(配置）的一般形式[A.，a]意味着处在栈顶是的相应状态，期望相应在栈顶的状态，然后只有当跟在后的token是终结符a时进行归约。a称作该

7、项目(配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A–>•,a.意味着处在栈中是的相应状态，但只有当下一个输入符是a时才能进行归约.a要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作A–>u•,a/b/c构造LR(1)项目集规范族和G0函数closure(I)按如下方式构造(1)I的任何项目属closure(I)；(2)若[A→β1．Bβ2，a]∈closure(I)，B→δ是一产生式，那么对于FIRST(β2a)中的每个终结符b，如果[B→．δ

8、,b]不在closure(I)中，则把它加进去；(3)重复（1）（2），直至closure(I)不再增大。GO函数：若I是一个项目集，X是一个文法符号GO(I,X)=closure(J)其中J