资源描述：
《LR分析器(LR Parser).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§3.7LR分析器(LRParser)*本节提出一种有效的﹑自下而上的语法分析技术,LR(k)分析技术,它能适用于一大类上下文无关文法的分析.*其中:L表示从左到右扫描输入符号串,R表示构造最右推导的逆过程,k表示在作分析决定时要向前看k个输入符号.在实际的编译器中,我们只考虑k=0或k=1的情形.当(k)省略时,表示k=1.一.LR分析方法的优缺点优点:能够构造LR分析器来识别所有能用上下文无关文法写的程序设计语言的结构.LR分析方法是已知的最一般的无回溯移进―归约方法.它能够和其它移进―归约方法一样有效地实现.LR分析方法能分析的文法类是预测分析法能分析的文法类的真超集(
2、propersuperset).*LR分析方法向前看k个符号只需看右句型中某个产生式右边的k个符号,而预测分析方法向前看k个符号要看某个产生式右边的文法符号能推出的前k个符号.因此,LR分析法比LL分析法简单,适用的文法类更广.LR分析器能及时察觉语法错误,在自左向右扫描输入时,尽可能快地发现错误.缺点:对典型的程序设计语言文法,手工构造LR分析器工作量太大.*目前已有许多自动生成LR分析器的生成器,例如:Yacc.一.LR分析算法1.结构:(见书P248)栈中:s0X1s1X2s2…Xmsm其中:si:状态(state),Xi:文法符号(grammarsymbol)分析表:
3、动作函数action和转移函数goto2.动作:根据当前栈顶状态sm和当前输入符号ai,action[sm,ai]有四种可能动作:(1)移进(shift)s,s是一个状态(2)按文法产生式A→β归约(reduce)(3)接受(accept)(4)出错3.活前缀(viableprefix)文法G的活前缀是它的右句型(rightsententialform)的前缀,它不超过该句型中最左句柄(handle)的右端.例:文法E→E+T
4、T,T→T*F
5、F,F→(E)
6、id,存在最右推导:ETT*FT*idF*id(E)*id(,(E,(E)都是右句型(E)*id的活前缀.4.格局(c
7、onfiguration):栈中内容:s0X1s1X2s2…Xmsm,剩余输入串:aiai+1…an$组成当前格局:(s0X1s1X2s2…Xmsm,aiai+1…an$)这个格局代表右句型:X1X2…Xmaiai+1…an5.分析器动作:设当前格局是(s0X1s1X2s2…Xmsm,aiai+1…an$)(1)如果action[sm,ai]=移进s,分析器进入格局:(s0X1s1X2s2…Xmsmais,ai+1ai+2…an$)(2)如果action[sm,ai]=归约A→β,分析器进入格局:(s0X1s1X2s2…Xm-rsm-rAs,aiai+1…an$)其中:s=g
8、oto[sm-r,A],r是β的长度.这里分析器首先从栈中弹出2r个符号,包括r个状态和r个文法符号,这些文法符号刚好匹配产生式的右部β,即β=Xm-r+1Xm-r+2…Xm.(3)如果action[sm,ai]=接受,分析完成.(4)如果action[sm,ai]=出错,分析器发现错误,调用错误恢复例程.6.例子:文法(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(1)F→id分析表(parsingtable)(见书P252)给出串id*id+id的移进―归约过程.(见书P253)*注意:在实际的LR分析器中,栈中不保存文法符号,栈顶的状态代表栈中
9、的内容.一.构造SLR分析表1.项目(item):是右部的某个地方加点的G的产生式.例如:产生式A→XYZ有项目:A→.XYZA→X.YZA→XY.ZA→XYZ.产生式A→ε只有一个项目A→.*解释项目中加点的意义.2.拓广文法(augmentedgrammar):在文法G中引入产生式:S’→S,得拓广文法G’,S’是G’的开始符号,S是G原来的开始符号.*引入这个新的产生式的目的是指出什么时候分析结束,宣布接受输入串.3.闭包函数设I是项目集,那么closure(I)是由下面两条规则从I构造的项目集(setofitems):(1)初始,I的每个项目都加入closure(I)
10、;(2)如果A→α.Bβ在closure(I)中,且B→γ是产生式,那么,如果B→.γ不在closure(I)中,则把它加入.反复运用这条规则,直到没有更多的项目可加入closure(I)为止.*A→α.Bβ的直观意义和B→.γ加入closure(I)的意义.例:文法:E’→EE→E+T
11、TT→T*F
12、FF→(E)
13、id设I={E’→.E},那么closure(I)为{E’→.E,E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.id}4.核心项目与非核心项目(kernelitemsa
