人工智能_编译new第五章自下而上语法分析.ppt
《人工智能_编译new第五章自下而上语法分析.ppt》由会员分享,可在线阅读,更多相关《人工智能_编译new第五章自下而上语法分析.ppt(100页珍藏版)》请在启牛文库网上搜索。
1、第五章 语法分析自下而上分析,本章内容自下而上分析基本问题直观算符优先分析法算符优先分析 LR分析法,自下而上分析法从输入串开始,逐步进行“归约”,直至归约到文法的开始符号;一、自下而上分析基本问题,1、归约利用栈,输入符号移进栈,当栈顶形成P的候选式时,就归约为它的左P符号,例5.1 文法G2:S-aAcBe A-bA-Ab B-d输入串:abbcde,自下而上法,即“移进-归约”法,最右推导:,a,a,b,a,A,a,A,b,a,A,a,A,c,a,A,c,d,a,A,c,B,a,A,c,B,e,S,1,2,3,4,5,6,7,8,9,10,栈,S,=aAcBe,=aAcde,=aAbcd
2、e,=a b b c d e,S-aAcBe,输入串:abbcde,A-Ab,B-d,A-b,S,a,A,c,B,e,A,b,d,b,分 析 树,最左归约:,=S,=aAcBe,=aAcde,=aAbcde,a b b c d e,S-aAcBe,输入串:abbcde,A-Ab,B-d,A-b,2 规范归约,短语:令G是一个文法,S是文法的开始符号,若是文法G的一个句型,如果有S A且 A,则称是句型相对于非终结符A的短语。,句柄:一个句型的最左直接短语称为该句型的句柄。,规范推导:即最右推导;规范句型:由规范推导所得的句型称为规范句型;规范归约:是关于句型的一个最右推导的逆过程,也称最左归约
3、。,例5.2 文法G E T|E+T T F|T*F F i|(E)的一个句型 i1*i2+i3,语 法 树,T,F,E,E,F,F,+,T,*,i1,i2,i3,T,i1,i2,i3,i1*i2,i1*i2+i3,i1,i2,i3,i1,短语:,直接短语:,句柄:,3 符号栈的使用,规范归约用来作语法分析需要解决的问题:如何在句型中找出句柄?在相同的右部有不止一个产生式时,选哪一个?,实现移进-归约分析的一个方便途径是用一个栈和一个输 入缓冲区,用#表示栈底和输入的结束,分析程序的动作移进:下一输入符号移进栈顶归约:把句柄按产生式的左部进行归约接收:分析程序报告成功出错:发现了一个语法错,调
4、用出错处理程序,注意:可归约的串在栈顶,不会在内部,二 直观算符优先分析法 1 定义:任二个相继出现的终结符a与b(可能中间有VN),可能有以下优先关系:a b a的优先性低于ba b a的优先性等于ba b a的优先性高于b,2 例5.3 文法G:E E+E|E*E|EE|(E)|i的终结符的优先关系见下表。,优 先 表,E E+E|E*E|EE|(E)|i,3 使用如上分析表,构造分析算法(直观算符优先分析法),分析算法步骤:下一个输入符号读至a中;若a为i,则aOPND,转第一步;若 a,则调用关于的处理程序(语义程序),处理子表达式:E(1)E(2);然后重新进入第3步;(其中,E(1
5、)、E(2)分别为OPND栈的次栈顶和栈顶),a,OPTR,OPND,#,E(1),E(2),E(3),=,若 a,则若=(,a=),则逐出OPTR栈顶的(,放弃a中的),转第 1步;若=a=#,分析成功结束;若 a,aOPTR栈,转第1步;与a不存在优先关系,则输入串错误,调出错处理,),OPTR,OPND,#,(,E(1),E(2),a,#,成功!,2 例5.4 由文法G:E E+E|E*E|EE|(E)|i的终结符的优先关系表及上述分析算法分析算术表达式 i1+i2*i3#的过程。,OPTR,OPND,分析过程,OPND栈为空,#-OPTR栈,i1-OPND#OPTR i2-OPND,#
6、,+,i1,i2,i3,*,t,e,输入串:,i1+i2*i3#,+OPTR i3-OPND,*#,*弹出OPTR栈;i2*i3=t-OPND,+#,+弹出OPTR栈;t+i1=e-OPND,#=#,分析成功;e 为整个表达式的结果,1 算符优先文法定义一 如果一个文法的任何产生式右部都不含两个相继(并列)的非终结符,即不含有如下形式的产生式右部:QR则我们称该文法为算符文法。,三 算符优先分析,定义二 假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b,我们说:a b,当且仅当文法G中含有形如P-ab 或P-aQb的产生式;(如:(E),则()a b,当且仅当G中含有形如P-aR的
7、产生式,而R b 或 R Qb;a b,当且仅当G中含有形如P-Rb的产生式,而R a 或 R aQ。,定义三 如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三种关系之一:a b,a b,a b则称G是一个算符优先文法。,2 从算符优先文法构造优先关系表,构造优先关系表,就是要找出所有VT对之间的三种关系,而对于 可以直接检查所有的G中P来得到。而,关系不易检查,故要定义二个集合。FIRSTVT(P)=a|P a或P Qa,aVT 而QVN LASTVT(P)=a|P a或P aQ,aVT 而QVN 如该二集合成功,检查P,就可确定满足,的(a,b)对。这是因为,假定有个产生式候选
8、式:aP,那么对任何 bFIRSTVT(P),有a b;Pb,那么对任何 aLASTVT(P),有a b;,构造该二个集合的算法,对每一 VN的FIRSTVT(P)、LASTVT(P)使用每个VN的FIRSTVT(P)、LASTVT(P),检查每一个产生式,找出所有(a,b)的关系,就完成了构造优先关系表。,因此,问题归结为:,3 构造集合FIRSTVT(P)的算法 P-a或P-Qa,则aFIRSTVT(P);若aFIRSTVT(Q),且有产生式P-Q,则aFIRSTVT(P),4 构造集合LASTSTVT(P)的算法 P-a 或 P-aQ,则aLASTVT(P);若aLASTVT(Q),且有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 编译 new 第五 自下而上 语法分析