第五章-语法分析自下而上分析-优质课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第五章-语法分析自下而上分析-优质课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 语法分析 自下而上 分析 优质 课件
- 资源描述:
-
1、第五章 语法分析自下而上分析第五章第五章 语法分析语法分析-自下而上分析自下而上分析22022-8-5中南大学软件学院 陈志刚主要内容:主要内容:5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析概述 5.4 LR(0)分析 5.5 SLR(1)分析 5.6 LR(1)分析 5.7 LALR(1)分析 5.8 二义文法的应用第五章第五章 语法分析语法分析-自下而上分析自下而上分析32022-8-5中南大学软件学院 陈志刚5.1 5.1 自下而上分析基本问题自下而上分析基本问题自下而上分析法(Bottom-up)n基本思想:从输入串开始,逐步进行“归约”,直到文法的开始符号。即
2、从树末端开始,构造语法树。所谓归约,是指根据文法的产生式规则,把产生式的右部替换成左部符号。n算符优先分析法:按照算符的优先关系和结合性质进行语法分析。适合分析表达式。nLR分析法:规范归约第五章第五章 语法分析语法分析-自下而上分析自下而上分析42022-8-5中南大学软件学院 陈志刚例:G(E):Ei|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE第五章第五章 语法分析语法分析-自下而上分析自下而上分析52022-8-5中南大学软件学院 陈志刚一、归约n采用“移进归约”思想进行自下而上分析。n基本思想:设计一个堆栈,把符号串
3、从左至右压入栈中,判别栈顶符号是否为某一个产生式的右部,若是则把栈顶的这一部分替换成(归约为)该产生式的左部符号。n可归约串在算符优先分析法中即为最左素短语,在规范归约中是句柄。n最左归约是最右推导的逆过程,最左归约称为规范。第五章第五章 语法分析语法分析-自下而上分析自下而上分析62022-8-5中南大学软件学院 陈志刚n例:设文法G(S):(1)S aAcBe (2)A b (3)A Ab (4)B d试对abbcde进行“移进归约”分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e第五章第五章 语法分
4、析语法分析-自下而上分析自下而上分析72022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析82022-8-5中南大学软件学院 陈志刚二、分析树n语法分析过程可用一棵语法分析树表示出来。n自下而上分析过程:边输入单词符号,边归约。即,在自下而上分析的每一步,都可画出一棵子树,随着归约的完成,便最终形成一棵分析树。n如果文法无二义,分析树恰好等同于语法树。n核心问题:识别可归约串bdbaceSABA第五章第五章 语法分析语法分析-自下而上分析自下而上分析92022-8-5中南大学软件学院 陈志刚三、规范归约n定义:令G是一个文法,S是文法的开始符号,假定
5、是文法G的一个句型,如果有 且 则称是句型相对于非终结符A的短语短语。n特别地,如果有A,则称是句型相对于规则A 的直接短语直接短语。n一个句型的最左直接短语称为该句型的句柄句柄。AS*A第五章第五章 语法分析语法分析-自下而上分析自下而上分析102022-8-5中南大学软件学院 陈志刚例:考虑文法G(E):E T|E+T T F|T*F F (E)|i 和句型i1*i2+i3:E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短语:i1,i2,i3,i1*i2,i1*i2+i3n直接短语:i1,i2,i3n句柄:i1第五章第五章 语法分析
6、语法分析-自下而上分析自下而上分析112022-8-5中南大学软件学院 陈志刚n在一个句型对应的语法树中,以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语,如果子树只有两代,则该短语就是直接短语。EFFTTTi1+*EFi3i2第五章第五章 语法分析语法分析-自下而上分析自下而上分析122022-8-5中南大学软件学院 陈志刚n可用句柄来对句子进行归约句型 归约规则abbcde (2)A baAbcde (3)A AbaAcde (4)B daAcBe (1)S aAcBe S第五章第五章 语法分析语法分析-自下而上分析自下而上分析132022-8-5中
7、南大学软件学院 陈志刚n定义:假定是文法G的一个句子,我们称序列n,n-1,0 是的一个规范归规范归约约,如果此序列满足:1、n=2、0为文法的开始符号,即0=S 3、对任何i,0 i n,i-1是从i经把句柄替换成为相应产生式左部符号而得到的。第五章第五章 语法分析语法分析-自下而上分析自下而上分析142022-8-5中南大学软件学院 陈志刚把上例倒过来写,则得到:S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。最右推导常被称为规范推导。容易看到,规范归约是关于的一个最右推导 的逆过程。因些,规范归约也称最左归约。由规范推导推出的句型称为规范句型。第五章第五章
8、语法分析语法分析-自下而上分析自下而上分析152022-8-5中南大学软件学院 陈志刚bdbaceSABAdbaceSABAdaceSABaceSABS第五章第五章 语法分析语法分析-自下而上分析自下而上分析162022-8-5中南大学软件学院 陈志刚四、符号栈的使用n栈是语法分析的一种基本数据结构。#作为栈底符号。n初始状态:栈 输入串#n自左至右把输入符号一一进栈,一旦栈顶形成句柄,就把其归约,直至栈顶不再形成句柄为止。然后继续移进,重复上述过程,直至形成 栈S,输入串。n若达到上述状态,则表示分析成功,否则输入串不是句子。第五章第五章 语法分析语法分析-自下而上分析自下而上分析17202
9、2-8-5中南大学软件学院 陈志刚步骤 符号栈输入串 动作0#i1*i2+i3#预备1#i1 *i2+i3#进2#F *i2+i3#归,用Fi3#T *i2+i3#归,用TF4#T*i2+i3#进例:考虑文法G(E):E T|E+T T F|T*F F (E)|i输入串为i1*i2+i3,分析步骤为:第五章第五章 语法分析语法分析-自下而上分析自下而上分析182022-8-5中南大学软件学院 陈志刚步骤 符号栈输入串动作4#T*i2+i3#进5#T*i2 +i3#进6#T*F +i3#归,用Fi7#T +i3#归,用TT*F8#E +i3#归,用ET9#E+i3#进例:考虑文法G(E):E T
10、|E+T T F|T*F F (E)|i输入串为i1*i2+i3,分析步骤为:第五章第五章 语法分析语法分析-自下而上分析自下而上分析192022-8-5中南大学软件学院 陈志刚步骤 符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归,用Fi12#E+T#归,用TF13#E#归,用EE+T14#E#接受例:考虑文法G(E):E T|E+T T F|T*F F (E)|i输入串为i1*i2+i3,分析步骤为:第五章第五章 语法分析语法分析-自下而上分析自下而上分析202022-8-5中南大学软件学院 陈志刚5.2 5.2 算符优先分析算符优先分析n四则运算的优先规则:先乘除后加减
11、,同级从左到右n考虑二义文法文法G(E):G(E):E i|E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。n归约即计算表达式的值。归约顺序不同,则计算的顺序也不同,结果也不一样。n如果规定算符的优先次序,并按这种规定进行归约,则归约过程是唯一的。第五章第五章 语法分析语法分析-自下而上分析自下而上分析212022-8-5中南大学软件学院 陈志刚n算符优先分析过程是自下而上的归约过程,但未必是严格的最左归约。也就是说,算符优先分析法不是一种规范归约法。n所谓算符优先分析法就是定义算符之间的某种优先关系,借助于这种关系寻找“可归约串”进行归约的一种方法。第五章第五章 语法分析
12、语法分析-自下而上分析自下而上分析222022-8-5中南大学软件学院 陈志刚n首先必须定义任何两个可能相继出现的终结符a与b的优先关系 三种关系a b a的优先级高于bn注意:与数学上的,=不同a a一、直观算符优先分析法第五章第五章 语法分析语法分析-自下而上分析自下而上分析232022-8-5中南大学软件学院 陈志刚q直观算符优先分析法使用两个工作栈。OPTR-寄存操作符及,初值为,(输入串末尾也加)OPND-寄存操作数及结果,初值为空,最后为运算结果。第五章第五章 语法分析语法分析-自下而上分析自下而上分析242022-8-5中南大学软件学院 陈志刚n设设Q代表代表OPTR栈顶的当前符
13、号,栈顶的当前符号,a代表新的输入符号,代表新的输入符号,则直观算符优先算法为:则直观算符优先算法为:1Read next symbol to a;2If a=i then push a into OPND,GOTO 1;3If Q a then Call E(1)QE(2);GOTO 3;(注:E(1)QE(2)指pop E(1);pop E(2);t:=E(1),&,E(2)进行Q运算;push t;pop Q);4If Q a then If Q=(and a=)then pop Q;GOTO 1;If Q=a=then success;halt.5If Q b 当且仅当G中含有形如PR
14、b的产生式,而 R a或R aQ。p2.a b当且仅当G中含有形如PaR的产生式,而R b或R Qb;n如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一:a b 则称G是一个算符优先文法。第五章第五章 语法分析语法分析-自下而上分析自下而上分析272022-8-5中南大学软件学院 陈志刚FIRSTVTFIRSTVTn构造集合FIRSTVT(P)的算法。n按其定义,可用下面两条规则来构造集合FIRSTVT(P):1.若有产生式Pa或PRa,则a FIRSTVT(P);2.若a FIRSTVT(R),且有产生式PR,则a FIRSTVT(P)。第五章第五章 语法分析语法分析-自
15、下而上分析自下而上分析282022-8-5中南大学软件学院 陈志刚n构造集合LASTVT(P)的算法。n按其定义,可用下面两条规则来构造集合LASTVT(P):1.若有产生式P a或P aQ,则a LASTVT(P);2.若a LASTVT(Q),且有产生式P Q,则a LASTVT(P)。,|)(NTVQVaaQPaPaPLASTVT而或LASTVTLASTVT第五章第五章 语法分析语法分析-自下而上分析自下而上分析292022-8-5中南大学软件学院 陈志刚n检查G的每个候选式,若有paQb或pab的产生式,则置a bn若G中有形如aP的候选式,则对于所有的bFIRSTUT(P),有a b
16、 优先关系表的构造第五章第五章 语法分析语法分析-自下而上分析自下而上分析302022-8-5中南大学软件学院 陈志刚n数据结构:布尔数组FP,a,使得FP,a为真的条件是,当且仅当aFIRSTVT(P)。开始时,按上述的规则(1)对每个数组元素FP,a赋初值。栈STACK,把所有初值为真的数组元素FP,a的符号对(P,a)全都放在STACK之中。构造优先关系表的算法第五章第五章 语法分析语法分析-自下而上分析自下而上分析312022-8-5中南大学软件学院 陈志刚n运算:如果栈STACK不空,就将顶项逐出,记此项为(Q,a)。对于每个形如PQ 的产生式,若FP,a为假,则变其值为真且将(P,
17、a)推进STACK栈。上述过程必须一直重复,直至栈STACK拆空为止。第五章第五章 语法分析语法分析-自下而上分析自下而上分析322022-8-5中南大学软件学院 陈志刚n如果把这个算法稍为形式化一点,我们可得如下所示的一个程序(包括一个过程和主程序):PROCEDURE INSERT(P,a);IF NOT FP,a THENBEGIN FP,a:=TRUE;把(P,a)下推进STACK栈 END;第五章第五章 语法分析语法分析-自下而上分析自下而上分析332022-8-5中南大学软件学院 陈志刚主程序:BEGIN FOR 每个非终结符P和终结符a DO FP,a:=FALSE;FOR 每个
18、形如Pa或PQa的产生式 DO INSERT(P,a);WHILE STACK 非空 DOBEGIN 把STACK的顶项,记为(Q,a),上托出去;FOR 每条形如PQ的产生式 DOINSERT(P,a);END OF WHILE;END第五章第五章 语法分析语法分析-自下而上分析自下而上分析342022-8-5中南大学软件学院 陈志刚n这个算法的工作结果得到一个二维数组F,从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a|FP,a=TRUEn同理,可构造计算LASTVT的算法。第五章第五章 语法分析语法分析-自下而上分析自下而上分析352022-8-5中南大学软件学院 陈志刚三
19、、算符优先分析法的设计n可归约串,句型,短语,直接短语,句柄,规范归约。n一个文法G的句型的素短语素短语是指这样一个短语,它至少含有一个终结符,并且,除它自身之外不再含任何更小的素短语。n最左素短语最左素短语是指处于句型最左边的那个素短语。第五章第五章 语法分析语法分析-自下而上分析自下而上分析362022-8-5中南大学软件学院 陈志刚n例:考虑下面的文法G(E):(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|iEEF+*TiFTFTP+ETP句型:句型:T+F*P+i短语:短语:直接短语:直接短语:句柄:句柄:素短语:素短语:最左素短语:最左素短语:,T+F*
20、P+iT,F,P,F*P,iT+F*PT,F,P,iTF*P,iF*P第五章第五章 语法分析语法分析-自下而上分析自下而上分析372022-8-5中南大学软件学院 陈志刚n算符优先文法句型(括在两个之间)的一般形式写成:#N1a1N2a2NnanNn+1#其中,每个ai都是终结符,Ni是可有可无的非终结符。n定理:一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1,其中,aj-1 ai+1第五章第五章 语法分析语法分析-自下而上分析自下而上分析382022-8-5中南大学软件学院 陈志刚n根据这个定理,下面我们讨论算符优先分析算法。n为了和定理叙述的相适
21、应,我们使用一个符号栈S,用它寄存终结符和非终结符,下面的分析算法是直接根据这个定理构造出来的,k代表符号栈S的使用深度。第五章第五章 语法分析语法分析-自下而上分析自下而上分析392022-8-5中南大学软件学院 陈志刚k:=1;Sk:=#;REPEAT 把下一个输入符号读进a中;IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DOBEGIN REPEAT Q:=Sj;IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL SjQ;把Sj+1Sk归约为某个N;k:=j+1;Sk:=N END OF WHILE;IF Sja OR Sja
22、 THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR/*调用出错诊察程序*/UNTIL a=#自左至右,终结符对终结符,非自左至右,终结符对终结符,非终结符对非终结符,而且对应的终结符对非终结符,而且对应的终结符相同。终结符相同。N X1 X2 Xk-j Sj+1 Sj+2 Sk第五章第五章 语法分析语法分析-自下而上分析自下而上分析402022-8-5中南大学软件学院 陈志刚n在算法的工作过程中,若出现j减1后的值小于等于0时,则意味着输入串有错。在正确的情况下,算法工作完毕时,符号栈S应呈现:#N#。n由于非终结符对归约没有影响,因此,非终结符根本可以不进符号栈S
23、。第五章第五章 语法分析语法分析-自下而上分析自下而上分析412022-8-5中南大学软件学院 陈志刚n算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn考虑下面的文法G(E):(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的句子i+i*i+i第五章第五章 语法分析语法分析-自下而上分析自下而上分析422022-8-5中南大学软件学院 陈志刚n算符优先分析法特点:优点:简单,快速缺点:可能错误接受非法句子,能力有限.n算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL 60第五章
24、第五章 语法分析语法分析-自下而上分析自下而上分析432022-8-5中南大学软件学院 陈志刚四、优先函数n把每个终结符与两个自然数f()与g()相对应,使得若1 2,则f(1)g(2)f称为入栈优先函数,g称为比较优先函数。n优点:便于比较,节省空间;n缺点:原来不存在优先关系的两个终结符,由于自然数相对应,变成可以比较的。要进行一些特殊的判断。第五章第五章 语法分析语法分析-自下而上分析自下而上分析442022-8-5中南大学软件学院 陈志刚n例:文法G(E)(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的优先函数如下表+*()i#F2440660G 135
25、5050第五章第五章 语法分析语法分析-自下而上分析自下而上分析452022-8-5中南大学软件学院 陈志刚n有许多优先关系表不存在优先函数,如:abab 不存在对应的优先函数f和g 假定存在f和g,则有 f(a)=g(a),f(a)g(b),f(b)=g(a),f(b)=g(b)导致如下矛盾:f(a)g(b)=f(b)=g(a)=f(a)G如果优先函数存在,则不唯一(无穷多)第五章第五章 语法分析语法分析-自下而上分析自下而上分析462022-8-5中南大学软件学院 陈志刚n如果优先函数存在,则可以通过以下三个步骤从优先表构造优先函数:1 对于每个终结符a,令其对应两个符号fa和ga,画一以
展开阅读全文