语法分析自下而上分析.pptx

《语法分析自下而上分析.pptx》由会员分享，可在线阅读，更多相关《语法分析自下而上分析.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.1 自下而上分析基本问题自下而上分析：从输入开始，逐步进行“归约”，直至归约到文法的开始符号。第1页/共51页5.1.1 归约自下而上分析法是一种“移进-归约”法。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。第2页/共51页5.1.1 归约例：设文法GS：(1)S aAcBe (2)A b (3)A Ab (4)B d试对abbcde进行“移进-归约”分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S 第3

2、页/共51页5.1.1 归约例：设文法GS：(1)S aAcBe (2)A b (3)A Ab (4)B d试对abbcde进行“移进-归约”分析。第4页/共51页5.1.1 归约分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串bdbaceSABA第5页/共51页5.1.2 规范归约简述定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有 且 则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A,则称则称 是句型是句型相相对于规则对于规则A A 的的直接短语直接短语。一个句型的最。

3、一个句型的最左直接短语称为该句型的左直接短语称为该句型的句柄句柄。第6页/共51页5.1.2 规范归约简述例：文法GE：EE+T|T TT*F|F F(E)|F|id 考虑文法GE上的句子id1+id2*id3。其最右推导和分析树如图5.1(a)、(b)所示。分析树中的叶子与短语、直接短语和句柄有下述关系。短语：以非终结符为根的子树中所有从左到右排列的叶子；直接短语：只有父子关系的树中所有从左到右排列的叶子(树高为2)；句柄：最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的)。第7页/共51页图5.1 id1+id2*id3的最右推导、分析树与短语(a)最右推导；(b)分析树；(c)短语

4、 根据定义，从文法开始符号经过0步推导得到E1，从E1经过若干步推导得到id1+id2*id3，所以id1+id2*id3是句型id1+id2*id3相对于E1的短语(其中和均为，是句子的全体)。考虑推导E1=E2+id2*id3=T2+id2*id3=F1+id2*id3=id1+id2*id3，id1是相对于非终结符E2、T2和F1的短语(其中为，为+id2*id3)，特别是相对于F1的直接短语，也是句柄。id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语，因为找不到任何一个非终结符，它的子树中的所有叶子构成id1+id2。第8页/共51页EFFTTTi1+*EFi3i

5、25.1.2 规范归约简述例：考虑文法GE：ET|E+T TF|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+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i1第9页/共51页5.1.2 规范归约简述可用句柄来对句子进行归约例：设文法GS：(1)S aAcBe (2)A b (3)A Ab (4)B d句

6、型 归约规则abbcde (2)A baAbcde (3)A AbaAcde (4)B daAcBe (1)S aAcBe S第10页/共51页5.1.2 规范归约简述定义：假定是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即0=S 3 对任何i，0 i n，i-1是从i经把句柄替换成为相应产生式左部符号而得到的。第11页/共51页5.1.2 规范归约简述把上例倒过来写，则得到：S aAcBe aAcde aAbcde abbcde 显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约 规范推导由规范推导推出的句

7、型称为规范句型。规范归约的中心问题：确定句型的句柄。第12页/共51页5.1.2 规范归约简述最右推导，推导的每一步结果都是一个右句型。该推导即分析树“剪句柄”的全过程。图3.18 剪句柄的过程(a)句子；(b)剪去b之后；(c)剪去Abc之后；(d)剪去d之后；(e)开始符号 第13页/共51页5.1.3 符号栈的使用与语法树的表示从分析树上直观地看，“剪句柄”的方法十分简单。但是若在语法分析器中实现剪句柄，则有两个问题必须解决：确定右句型中将要归约的子串(确定句柄)；确定如何选择正确的产生式进行归约。具体实现采用移进归约方法，用一个栈“记住”将要归约句柄的前缀，并用一个分析表来确定何时栈顶

8、已形成句柄，以及形成句柄后选择哪个产生式进行归约。第14页/共51页5.1.3 符号栈的使用与语法树的表示在移进归约分析模式中，符号栈的使用有以下四种操作形式。移进(shift):把当前输入中的下一个终结符移进栈；归约(reduce):句柄在栈顶已形成，用适当产生式左部代替句柄；接受(accept):宣告分析成功；报错(error):发现语法错误，调用错误恢复例程。第15页/共51页考察文法GS：SaABe Ab AAbc Bd 的输入序列abbcde，移进归约方法分析的符号栈变化过程如下所示。步骤栈内容当前输入动作(0)(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)#a#ab

9、#aA#aAb#aAbc#aA#aAd#aAB#aABe#Sabbcde#bbcde#bcde#bcde#cde#de#de#e#e#shiftshiftreduced by Abshiftshiftreduced by AAbcshiftreduced by Bdshiftreduced by SaABeaccept第16页/共51页5.2 算符优先分析考虑二义文法文法G(E)：G(E)：E i|E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。起决定作用的是相邻的两个算符之间的优先关系。如果规定算符的优

10、先次序，并按这种规定进行归约，则归约过程是唯一的。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。第17页/共51页5.2 算符优先分析定义任何两个可能相继出现的终结符a与b的优先关系：三种关系a b a的优先级低于ba b a的优先级等于ba b a的优先级高于b注意：与数学上的、=不同，a b并不意味着b a第18页/共51页5.2.1 算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表

11、由终结符和非终结符组成的任意序列，包括空字。第19页/共51页假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab 当且仅当文法G中含有形如Pab或PaQb的产生式；如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：a b，a b，a b 则称G是一个算符优先文法。2.ab 当且仅当G中含有形如PaR的产生式，而R b或R Qb；3.ab 当且仅当G中含有形如PRb的产生式，而R a或R aQ。第20页/共51页5.2.1 算符优先文法及优先表构造例:考虑下面的文法GE：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i

12、由第(4)条规则，有()；由规则EET和TT*F，有 *；由(2)和(3)，可得*；由(1)EET和E E+T，可得+；由(3)FPF和F PF，可得 。由(4)P(E)和 EE+TT+TT*F+TF*F+T PF*F+TiF*F+T 有(+、(*、(和(i。第21页/共51页5.2.1 算符优先文法及优先表构造优先关系表（#为终结符）第22页/共51页从算符优先文法G构造优先关系表的算法：通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：5.2.1 算符优先文法及优

13、先表构造第23页/共51页5.2.1 算符优先文法及优先表构造有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系和的所有终结符对。如：假定有个产生式的一个候选形为 aP 那么，对任何bFIRSTVT(P)，有 a b。假定有个产生式的一个候选形为 Pb 那么，对任何aLASTVT(P)，有 a b。第24页/共51页FIRSTVT(P)的算法构造集合FIRSTVT(P)的算法：按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式Pa或PQa，则aFIRSTVT(P)；2.若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。第25页/共51页FI

14、RSTVT(P)的算法数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当aFIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。第26页/共51页FIRSTVT(P)的算法如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：过程PROCEDURE I

15、NSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把(P，a)下推进STACK栈 END；第27页/共51页FIRSTVT(P)的算法主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE；FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)；WHILE STACK 非空 DO BEGIN 把STACK的顶项，记为(Q，a)，上托出去；FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END第28页/共51页FIRSTVT(P)的算法这个算法的工作结果得到一个二维数组F，从它可得任

16、何非终结符P的FIRSTVT。FIRSTVT(P)a|FP，a=TRUE同理，可构造计算LASTVT的算法。第29页/共51页5.2.1 算符优先文法及优先表构造使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF in-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2；IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a

17、 DO 置 Xia；IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END第30页/共51页5.2.1 算符优先文法及优先表构造例:考虑下面的文法GE：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i 1.计算文法G的FIRSTVT和LASTVT;2.构造优先关系表;3.G是算符优先文法吗?第31页/共51页第32页/共51页G的算符优先关系表：结论:G是算符优先文法第33页/共51页5.2.2 算符优先分析算法为了解决在算符优先分析过程中如何寻找到可归约串的问题，引进最左素短语的概念。一个文法G的句

18、型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。第34页/共51页考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i句型：T+F*P+i短语：T+F*P+i,T,F，P,F*P,i,T+F*P直接短语：T,F,P,i句柄：T素短语：F*P,i最左素短语：F*P5.2.2 算符优先分析算法EEF+*TiFTFTP+ETP第35页/共51页5.2.2 算符优先分析算法算符优先文法句型(括在两个之间)的一般形式写成：#N1a1N2a2NnanNn+1#其中，每个a

19、i都是终结符，Ni是可有可无的非终结符。定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1，aj-1 aj aj aj+1，ai-1 ai ai ai+1第36页/共51页5.2.2 算符优先分析算法算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL 60算符优先分析法特点：优点:简单，快速缺点:可能错误接受非法句子，能力有限.算符优先分析算法：使用一个符号栈S，用它寄存终结符和非终结符，k代表符号栈S的使用深度。第37页/共51页5.2.2 算符优先分析算法1 k:=1;Sk:=#;2 REPEAT3 把下一个输入符号读进

20、a中；4 IF SkVT THEN j:=k ELSE j:=k-1;5 WHILE Sja DO6 BEGIN7 REPEAT8 Q:=Sj;9 IF Sj-1VT THEN j:=j-1 ELSE j:=j-210 UNTIL SjQ;11 把Sj+1Sk归约为某个N；12 k:=j+1;13 Sk:=N14 END OF WHILE;15 IF Sja OR Sja THEN16 BEGIN k:=k+1;Sk:=a END17 ELSE ERROR/*调用出错诊察程序*/18 UNTIL a=#第38页/共51页5.2.2 算符优先分析算法在算法的工作过程中，若出现j减1后的值小于等于

21、0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。算法的第11行中的N是指那样一个产生式的左部符号，此产生式的右部和S j+1Sk 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。第39页/共51页5.2.2 算符优先分析算法算符优先分析一般并不等价于规范归约EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiP第40页/共51页5.2.3 优先函数把每个终结符与两个自然数f()与g()相对应，使得若1 2，则f(1)g(2)f称为入栈优先

22、函数，g称为比较优先函数。优点:便于比较，节省空间；缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。第41页/共51页5.2.3 优先函数文法GE (1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的优先函数如下表：第42页/共51页有许多优先关系表不存在优先函数，如：不存在对应的优先函数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)如果优先函数存在，则不唯一(无穷多)5.2.3 优先函数abab第43页

23、/共51页如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:1 对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号fa和ga为结点的方向图。如果ab，则从fa画一条弧至gb，如果ab，则画一条弧从gb至fa。2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3 检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。5.2.3 优先函数第44页/共51页例:求文法G(E)(1)EE+T|T (2)TT*F|F (3)FP F|P

24、(4)P(E)|i的终结符+，*，i所对应的优先函数。5.2.3 优先函数第45页/共51页5.2.3 优先函数f+f*f fig+g*g gi+*i+*i第46页/共51页练习1 已知文法GS为：Sa|(T)TT,S|S(1)计算GS的FIRSTVT和LASTVT。(2)构造GS的算符优先关系表并说明GS是否为算符优先文法。(3)给出输入串(a,(a,a)#的算符优先分析过程。第47页/共51页文法：Sa|(T)TT,S|S 展开为：SaSS(T)TT,S TS(1)FIRSTVT-LASTVT表 非终结符非终结符 FIRSTVT集集 LASTVT集集 S a (a )T a (,a ),第

25、48页/共51页(2)算符优先关系表如下:表中无多重入口所以是算符优先（OPG）文法。a (),#a(),#第49页/共51页(3)对输入串（a,(a,a)）#的算符优先分析过程为：栈栈 当前当前字符字符 剩余输入串剩余输入串动作动作#(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,(a,a)#a,(a,a)#,(a,a)#(a,a)#(a,a)#a,a)#,a)#a)#a)#)#)#)#)#Move inMove inReduce:SaMove inMove inMove inReduce:SaMove inMove inReduce:SaReduce:TT,SMove inReduce:S(T)Reduce:TT,SMove inReduce:S(T)第50页/共51页感谢您的观看！第51页/共51页