北大编译原理讲义课件.ppt

《北大编译原理讲义课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.7LR分析器序4.7.1LR分析器的逻辑结构及工作过程4.7.2SLR分析表的构造4.7.3LR（1）分析表的构造4.7.4LALR(1)分析表的构造4.8LR分析对二义文法的应用4.9分析器的生成器yacc1序LR(k)分析技术。这里的“L”是指从左至右扫描输入符号串，“R”是指构造一个最右推导的逆过程，“k”是指为了作出分析决定而向前看的输入符号的个数。LR分析方法是当前最广义的无回溯的“移进-归约”方法。根据栈中的符号串和向右顺序查看输入串的k(k0)个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。LR(k)分析技术knuth于1965年首先提出2来的。优

2、点：适用范围广；分析速度快；报错准确。构造分析器的工作量很大，不大可能手工构造；用软件工具yacc-YetAnotherCompilerCompiler,Bell,1974.LR(0)SLR(1)LR(1)LALR(1)34.7.1LR分析器的逻辑结构及工作过程一个输入、一个输出、一个栈、一个驱动程序和一张分析表id+id*id$SmXmSm-1Xm-1…S0LR驱动程序动作转移actiongoto输出4分析表：移进ai和s=goto[sm,ai]进栈action[sm,ai]=归约rj:AXm-r+1Xm-r+2…Xm接受s=goto[sm-r,A]出错G[E’]:(0)E’E(1)E

3、E+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fid5表4.11文法（4.22）的SLR分析表6LR分析器的工作过程格局：（栈中符号序列，剩余输入符号串）开始：（s0,a1a2……an$)中间：（s0x1s1x2s2…xmsm,aiai+1…an$)x1x2…xmaiai+1…an是一个右句型。1.若action[sm.ai]=si,则把ai,si=action[sm,ai]推进栈.格局：（s0x1s1x2s2…xmsmaisi,ai+1…an$)72.若action[sm.ai]=r(Axm-r+1xm-r+2…xm),则格局：（s0x1s1x2s2…xm-rsm-

4、rAs,aiai+1…an$)其中，s=goto[sm-r,A]3.若action[sm.$]=accep,则分析结束。4.若action[sm,ai]=error,则转出错处理程序。下面，显示id+id*id的LR分析过程：8栈输入动作0id+id*id$s50id5+id*id$r6Fid0F3+id*id$r4TF0T2+id*id$r2ET0E1+id*id$s60E1+6id*id$s50E1+6id5*id$r6Fid0E1+6F3*id$r4TF0E1+6T9*id$s70E1+6T9*7id$s50E1+6T9*7id5$r6Fid9栈输入动作0E1+6T9*7F1

5、0$r3TT*F0E1+6T9$r1EE+T0E1$accep0532169710idFTE+T*FididF分析表4.11是识别文法G[E]活前缀的有限自动机。104.7.2SLR分析表的构造根椐文法G，构造识别文法G的所有活前缀的DFAm，根椐DFAm构造分析表。分析表是DFAm的一种描述形式。一.项目识别活前缀的DFAm每个状态是一个项目集。SA,VT活前缀：的前缀是右句型的活前缀。*rmrm11活前缀和句柄的关系：1.活前缀不含有句柄的任何符号，；2.活前缀含有句柄的部分符号，1；3.活前缀已含有句柄的全部符号，。识别活前缀的自动机处于的格局：

6、0q0q1q0qq2112用圆点“”表示识别一个产生式右部符号到达的位子，若有规则AXYZ,则有下面四个项目：AXYZAa,aVT移进项目AXYZAB,BVNAXYZ待归约项目AXYZA,AA归约项目S´S,S´S接受项目以上项目称作LR(0)项目。13二.有效项目集和转移函数定义4.6(识别活前缀的有效项目)如果存在一个规范推导SαAwαβ1β2w项目A→β1·β2对识别活前缀γ=αβ1是有效的。有下面的结论：若项目A→α·Bβ对识别活前缀=δα是有效的且若B→ηP，则项目B→·η对识别活前缀=δα也是有效的。*r

7、mrm14推导如下：若项目A→α·Bβ对识别活前缀=δα是有效，则存在一个规范推导SδAwδαBβw设βwxw,则对任何B→ηP，有SδAwδαBβwδαBxwδαηxw则B→·η对识别活前缀=δα也是有效的。A→α·Bβ和B→·η在同一个项目集中。*rmrm*rm*rmrm*rmrm15识别文法G的某个活前缀γ的所有有效项目组成的集合称为γ的有效项目集。文法G的所有有效项目