编译原理课件Chapt5-2.ppt

《编译原理课件Chapt5-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理第五章语法分析——自下而上分析LR分析法1965年由Knuth提出什么是LR(k)分析:L：从左到右扫描R：最右推导的逆过程（最左归约）k：是指为了作出分析决定而向前看的输入符号的个数是一种规范归约过程适用范围广，适用于多数无二义性的上下文无关文法分析效率高，报错及时可以自动生成手工实现工作量大LR分析法的优缺点优点缺点自下而上分析的中心思想是“移进－归约”，关键问题就是“寻找规范句型的句柄”。当一貌似句柄的符号串呈现于分析栈顶时，如何确定用哪一个产生式来归约？文法G[S]：(1)S→aPcQe(2)P→b(3)P→Pb(4)Q→dabbcde步骤符号栈输入符号串动作1）#a

2、bbcde#移进2）#abbcde#移进P3）#abbcde#归约(P→b)4）#aPbcde#移进P5）#aPbcde#归约(P→Pb)6）#aPcde#移进7）#aPcde#移进Q8）#aPcde#归约(Q→d)9）#aPcQe#移进11）#S#接受S10）#aPcQe#归约SaPcQeaPcdeaPbcdeabbcdeLR分析法LR分析法的基本思想：根据“历史资料”、“现实输入符号”以及对未来的“展望”等三个方面来确定栈顶的符号是否构成了相对于某一产生式的句柄。5.3.1LR分析器规范归约的关键问题是寻找句柄.“历史”：已移入符号栈的内容“展望”：根据产生式推测未来可能遇

3、到的输入符号“现实”：当前的输入符号LR分析方法：把"历史"及"展望"综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作LR分析程序状态符号分析栈actiongotoLR分析表a1a2aian#输入串输出LR分析器的核心是一张分析表：ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.GOTO[s，X]：状态s面对文法符号X时，下一状态是什么LR分析表a1a2…alS1ACTION[S1,a1]ACTION[S1,a2]…ACTION[S1,al]S2ACTION[S2,a1]ACTION[S2,a2]…ACTION[S2,al]……………SnACTION

4、[Sn,a1]ACTION[Sn,a2]…ACTION[Sn,al]X1X2…XlS1GOTO[S1,X1]GOTO[S1,X2]…GOTO[S1,Xl]S2GOTO[S2,X1]GOTO[S2,X2]…GOTO[S2,Xl]……………SnGOTO[Sn,X1]GOTO[Sn,X2]…GOTO[Sn,Xl]ACTION表（分析动作表）GOTO表（状态转换表）每一项ACTION[s，a]所规定的四种动作:1.移进把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号.2.归约指用某产生式A进行归约.假若的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈

5、顶状态，然后把(sm-r,A)的下一状态s’=GOTO[sm-r,A]和文法符号A推进栈.3.接受宣布分析成功，停止分析器工作.4.报错分析开始时:状态已归约串输入串(s0，#，a1a2an#)以后每步的结果可以表示为:(s0s1sm，#X1Xm，aiai+1an#)(s0s1sm，#X1Xm，aiai+1an#)分析器根据ACTION(sm,ai)确定下一步动作1.若ACTION(sm,ai)为移进，且s=GOTO(sm,ai),，则三元式格局变为:(s0s1sms，#X1Xmai，ai+1an#))2.若ACTION(sm,ai)为按A归约，三元式变为:(s

6、0s1sm-rs，#X1Xm-rA，aiai+1an#))此处,s=GOTO(sm-r,A),r为的长度,=Xm-r+1Xm3.若ACTION(sm,ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功.4.若ACTION(sm,ai)为"报错"，则三元式变化过程终止，报告错误.(s0s1sm-rsm-r+1sm，#X1Xm-rXm-r+1Xm，aiai+1an#)(s0s1sm-r，#X1Xm-r，aiai+1an#))(s0s1sm-rs，#X1Xm-rA，aiai+1an#))LR分析表实例设已给文法G[L]:1.LE,L2.LE3

7、.Ea4.Eb，产生的语言为：单个a,b或用逗号隔开的多个a,b符号串文法的LR分析表如下(s表示移进操作,r表示归约)ab，$0ss1acc2sr23r3r34r4r45ss6r1ab，$LE0341212534534626ACTION表GOTO表分析表的合并可看出,GOTO表中所有关于终结符的状态转换都与ACTION表中的移进操作对应，因此可将相应的列合并，得到下面的分析表（关于VN符的状态转换仍然保留）：状态ACTIONGOTOab，