第五章-语法分析自下而上分析-优质课件.ppt

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，画一以

26、所有符号和为结点的方向图。如果ab，则从fa画一条弧至gb。如果ab，则画一条弧从gb至fa。2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3 检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。第五章第五章 语法分析语法分析-自下而上分析自下而上分析472022-8-5中南大学软件学院 陈志刚n现在必须证明：若ab，则f(a)g(b)；若ab，则f(a)g(b)。n第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从

27、gb到fa的弧。所以，fa和gb所能到达的结是全同的。n至于ab和ab的情形，只须证明其一。第五章第五章 语法分析语法分析-自下而上分析自下而上分析482022-8-5中南大学软件学院 陈志刚n如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a)g(b)。我们所需证明的是，在这种情况下，f(a)g(b)不应成立。我们将指出，如果f(a)g(b)，则根本不存在优先函数。假若f(a)g(b)，那么必有如下的回路：第五章第五章 语法分析语法分析-自下而上分析自下而上分析492022-8-5中南大学软件学院 陈志刚 因此有ab,a1b,a1b1,ambm,abm对任何

28、优先函数f和g来说，必定有f(a)g(b)f(a1)g(b1)f(am)g(bm)f(a)从而导致f(a)f(a)，产生矛盾。因此，不存在优先函数f和g。fa1fafamgb1gbgbm第五章第五章 语法分析语法分析-自下而上分析自下而上分析502022-8-5中南大学软件学院 陈志刚5.3 LR分析概述1、分析分析器模型器模型总控程序outputInput#S1 XmS1X1S0#栈状态文法符号ACTION GOTOLR分析表产生式表第五章第五章 语法分析语法分析-自下而上分析自下而上分析512022-8-5中南大学软件学院 陈志刚逻辑上说，一个逻辑上说，一个LR分析器由分析器由3个部分组成

29、：个部分组成：(1)总控程序总控程序，也可以称为驱动程序。对所有的，也可以称为驱动程序。对所有的LR分析器分析器总控程序都是相同的。总控程序都是相同的。(2)分析表分析表或分析函数，不同的文法分析表将不同，同一或分析函数，不同的文法分析表将不同，同一个文法采用的个文法采用的LR分析器不同时，分析表也不同，分析表又分析器不同时，分析表也不同，分析表又可分为可分为动作表（动作表（ACTION）和和状态转换（状态转换（GOTO）表）表两个部两个部分，它们都可用二维数组表示。分，它们都可用二维数组表示。(3)分析栈分析栈，包括文法符号栈和相应的状态栈，它们均是，包括文法符号栈和相应的状态栈，它们均是先

30、进后出栈。先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。分析器的动作就是由栈顶状态和当前输入符号所决定。2、LR分析方法的逻辑结构分析方法的逻辑结构第五章第五章 语法分析语法分析-自下而上分析自下而上分析522022-8-5中南大学软件学院 陈志刚 总控程序根据不同的分析表来决定其总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。文法按某种规则构造出来的。LR方法方法是根是根据具体文法的分析表对输入串进行分析处据具体文法的分析表对输入串进行分析处理。理。LR分析过程分析过程的思想是在总控程序的控的思想

31、是在总控程序的控制下，从左到右扫描输入符号串，根据分制下，从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。分析表完成相应的分析工作。第五章第五章 语法分析语法分析-自下而上分析自下而上分析532022-8-5中南大学软件学院 陈志刚分析表的组成：分析表的组成：(1)分析动作表分析动作表Action 符号符号状态状态a1a2atS0actionS0,a1 actionS0,a2actionS0,atS1actionS1,a1 actionS1,a2actionS1,atSnactionSn,a1 actionSn,a

32、2actionSn,at第五章第五章 语法分析语法分析-自下而上分析自下而上分析542022-8-5中南大学软件学院 陈志刚 表中表中actionSi,aj为二维数组，指出当前为二维数组，指出当前栈顶为状态栈顶为状态Si，输入符号为，输入符号为aj是所执行的动是所执行的动作。其动作有四种可能，分别为作。其动作有四种可能，分别为移进移进(S)、归约归约(r)、接受、接受(acc)、出错、出错(error)。(2)状态转换表状态转换表goto第五章第五章 语法分析语法分析-自下而上分析自下而上分析552022-8-5中南大学软件学院 陈志刚 符号符号状态状态x1x2xtS0gotoS0,x1got

33、oS0,x2gotoS0,xtS1gotoS1,x1gotoS1,x2gotoS1,xtSngotoSn,x1 gotoSn,x2gotoSn,xt 表表中中gotoSi,xj指出栈顶状态为指出栈顶状态为Si，文法符，文法符号为号为xj时应转到的时应转到的下一状态下一状态。第五章第五章 语法分析语法分析-自下而上分析自下而上分析562022-8-5中南大学软件学院 陈志刚分析表种类的不同决定使用不同的分析表种类的不同决定使用不同的LRLR分析方法分析方法a)SLR分析表分析表(简单简单LR分析表分析表)b)LR分析表分析表(规范规范LR分析表分析表)构造简单构造简单,最易实现最易实现,大多数上

34、下文无关文法都大多数上下文无关文法都 可以构造出可以构造出SLRSLR分析表分析表,所以具有较高的实用所以具有较高的实用 价值。使用价值。使用SLRSLR分析表进行语法分析的分析器分析表进行语法分析的分析器 叫叫SLRSLR分析器分析器适用文法类最大适用文法类最大,大多数上下文无关文法都能大多数上下文无关文法都能 构造出构造出LRLR分析表分析表,但其分析表体积太大但其分析表体积太大.暂时实暂时实 用价值不大用价值不大.第五章第五章 语法分析语法分析-自下而上分析自下而上分析572022-8-5中南大学软件学院 陈志刚c)LALR分析表分析表(超前超前LR分析表分析表)这种表适用的文法类及其实

35、现上难易在上面这种表适用的文法类及其实现上难易在上面 两种之间两种之间,在实用上很吸引人在实用上很吸引人.使用使用LALRLALR分析表进行语法分析的分析器叫分析表进行语法分析的分析器叫LALRLALR分析器。分析器。例：例：YACCYACC第五章第五章 语法分析语法分析-自下而上分析自下而上分析582022-8-5中南大学软件学院 陈志刚58581.1.三种分析表对应三类文法三种分析表对应三类文法几点说明几点说明2.2.一个一个SLRSLR文法必定是文法必定是LALRLALR文法和文法和LRLR文法文法第五章第五章 语法分析语法分析-自下而上分析自下而上分析592022-8-5中南大学软件学

36、院 陈志刚3、LR分析过程：分析过程：(1)LR分析步骤：分析步骤：(a)将初始状态将初始状态S0和句子的左界符和句子的左界符#分别进分析栈。分别进分析栈。(b)根据栈顶状态和当前输入符号查动作表，进根据栈顶状态和当前输入符号查动作表，进 行如行如下的工作。下的工作。移进：移进：当前输入符号进符号栈，根据状态转换当前输入符号进符号栈，根据状态转换表新的状态进状态栈，继续扫描，从而下一输入符表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。号变成当前输入符号。归约归约：(1)按某个产生式进行归约，若产生式的按某个产生式进行归约，若产生式的右端长度为右端长度为n，则符号栈顶和状态顶，

37、则符号栈顶和状态顶n个元素同时相个元素同时相应退栈。应退栈。(2)归约后的文法符号进符号栈，归约后的文法符号进符号栈，(3)查查第五章第五章 语法分析语法分析-自下而上分析自下而上分析602022-8-5中南大学软件学院 陈志刚状态转换表，新的状态进状态栈。状态转换表，新的状态进状态栈。(c)接受：接受：分析成功，终止分析。分析成功，终止分析。(d)出错出错：报告出错信息。：报告出错信息。(2)具体分析过程：具体分析过程：举例说明具体分析过程：举例说明具体分析过程：设文法为设文法为GL（假定已存在（假定已存在LR分析表）分析表）(1)L E,L (2)L E (3)E a (4)E b第五章第

38、五章 语法分析语法分析-自下而上分析自下而上分析612022-8-5中南大学软件学院 陈志刚 LR分析算法分析算法n置置ip指向输入串指向输入串w的第一个符号的第一个符号令令S为栈顶状态为栈顶状态 a是是ip指向的符号指向的符号重复重复 beginif ACTIONS,a=Sj then begin PUSH j,a(进栈进栈)ip 前进前进(指向下一输入符号指向下一输入符号)endelse if ACTIONS,a=rj (第第j条产生式为条产生式为A)第五章第五章 语法分析语法分析-自下而上分析自下而上分析622022-8-5中南大学软件学院 陈志刚LR分析算法分析算法nthen begi

39、npop|项项令当前栈顶状态为令当前栈顶状态为Spush GOTOS,A和和A(进栈进栈)nendnelse if ACTIONs,a=accthen return(成功）成功）nelse errorend.重复重复第五章第五章 语法分析语法分析-自下而上分析自下而上分析632022-8-5中南大学软件学院 陈志刚 为了介绍为了介绍LR分析过程，在这里直接给出该文分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。法的分析表，之后再介绍如何生成该表。状态ACTIONGOTOab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1ri表示按第

40、i个产生式进行归约Si表示把当前输入符号移进栈，且转第i个状态，即第i个状态进状态栈。i表示转第i个状态，即第i个状态进状态栈。空白表示分析动作出错。第五章第五章 语法分析语法分析-自下而上分析自下而上分析642022-8-5中南大学软件学院 陈志刚 根据上述分析表，即可对输入串进行分析。根据上述分析表，即可对输入串进行分析。如输入串为如输入串为#a,b,a#具体分析过程如下：具体分析过程如下：状态栈状态栈符号栈符号栈产生式产生式输入符号输入符号说明说明S0#a,b,a#S0和和#进栈进栈S0S3#a,b,a#a和和S3进栈进栈S0S2#EEa,b,a#a和和S3退栈退栈E和和S2进栈进栈S0

41、S2S5#E,b,a#,和和S5进栈进栈S0S2S5S4#E,b,a#b和和S4进栈进栈S0S2S5S2#E,EEb,a#b和和S4退栈退栈E和和S2进栈进栈第五章第五章 语法分析语法分析-自下而上分析自下而上分析652022-8-5中南大学软件学院 陈志刚状态栈状态栈符号栈符号栈产生式产生式输入符号输入符号说明说明S0S2S5S2S5#E,E,a#,和和S5进栈进栈S0S2S5S2S5S3#E,E,a#a和和S3进栈进栈S0S2S5S2S5S2#E,E,EEa#a和和S3退栈退栈E和和S2进栈进栈S0S2S5S2S5S6#E,E,LLE#E和和S2退栈退栈L和和S6进栈进栈S0S2S5S6#

42、E,L LE,L#E,L和和S2S5S6退退L和和S6进栈进栈S0S1#L LE,L#E,L和和S2S5S6退退L和和S1进栈进栈acc第五章第五章 语法分析语法分析-自下而上分析自下而上分析662022-8-5中南大学软件学院 陈志刚n自底向上分析法的关键问题是在分析过程中如何确定句柄。LR方法中的句柄是通过求可归前缀而求得。第五章第五章 语法分析语法分析-自下而上分析自下而上分析672022-8-5中南大学软件学院 陈志刚例：文法例：文法GS为：为：S aAcBe A b A Ab B d为产生式加序号变为为产生式加序号变为：S aAcBe1 A b2 A Ab3 B d4对于输入串对于输

43、入串abbcde句子的最右推导（规范推导）句子的最右推导（规范推导）如下：如下：SaAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1活前缀与可归前缀第五章第五章 语法分析语法分析-自下而上分析自下而上分析682022-8-5中南大学软件学院 陈志刚对它的逆过程最左归约对它的逆过程最左归约(规范归约规范归约)为：为：ab2b3cd4e1 aAb3cd4e1 aAcd4e1 aAcBe1 S用哪个产生式继续归约仅取决于当前句型的前部。用哪个产生式继续归约仅取决于当前句型的前部。我们把每次采取归约动作前的符号串部分称为我们把每次采取归约动作前的符号串部分称为可可归前缀归前缀。LR

44、分析的关键就是识别何时到达分析的关键就是识别何时到达可归前缀可归前缀。为产生式加序号变为为产生式加序号变为：S aAcBe1 A b2 A Ab3 B d4第五章第五章 语法分析语法分析-自下而上分析自下而上分析692022-8-5中南大学软件学院 陈志刚在规范句型中形成可归前缀之前包括可归前缀的在规范句型中形成可归前缀之前包括可归前缀的所有前缀称为活前缀。活前缀为一个或若干规范所有前缀称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范已分析过的部分即在符号栈中的符号串均为规范句型的活

45、前缀，则表明输入串的已被分析过的部句型的活前缀，则表明输入串的已被分析过的部分是某规范句型的一个正确部分。分是某规范句型的一个正确部分。例如：有下面规范句型的前缀：例如：有下面规范句型的前缀：，a，ab，a，aA，aAb，a，aA，aAc，aAcd，a，aA，aAc，aAcB，aAcBe左部均为活前左部均为活前缀，其中，红缀，其中，红色部分为可归色部分为可归前缀前缀第五章第五章 语法分析语法分析-自下而上分析自下而上分析702022-8-5中南大学软件学院 陈志刚nG=(Vn,Vt,P,S),若有若有S A A ,A （是句柄是句柄 ）是是的前缀的前缀,则称是文法则称是文法G G的活前缀的活前

46、缀n是含句柄的活前缀，并且句柄是的后端，则称是可归前缀或可规范前缀。n在在LRLR分析过程中，实际上是把分析过程中，实际上是把的前缀（即文的前缀（即文法法G G的活前缀）列出放在符号栈中，一旦在栈中出的活前缀）列出放在符号栈中，一旦在栈中出现现（形成可归前缀），即句柄已经形成，则（形成可归前缀），即句柄已经形成，则用产生式用产生式A 进行归约。进行归约。活前缀的定义及在活前缀的定义及在LRLR分析中的应用分析中的应用第五章第五章 语法分析语法分析-自下而上分析自下而上分析712022-8-5中南大学软件学院 陈志刚n识别活前缀的有限自动机识别活前缀的有限自动机n对任何一个上下文无关文法，只要能

47、构造对任何一个上下文无关文法，只要能构造出它的识别可归前缀的有限自动机，就可出它的识别可归前缀的有限自动机，就可以构造其相应的分析表（状态转换表和动以构造其相应的分析表（状态转换表和动作表）。作表）。第五章第五章 语法分析语法分析-自下而上分析自下而上分析722022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析732022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析742022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析752022-8-5中南大学软件学院 陈志刚

48、第五章第五章 语法分析语法分析-自下而上分析自下而上分析762022-8-5中南大学软件学院 陈志刚识别为活前缀的，则移识别为活前缀的，则移进；识别为可归前缀的，进；识别为可归前缀的，则归约则归约第五章第五章 语法分析语法分析-自下而上分析自下而上分析772022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析782022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析792022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析802022-8-5中南大学软件学院 陈志刚AC

49、TION表表 GOTO表表文法文法GE：(1)E:=E+T (2)E:=T (3)T:=T*F (4)T:=F (5)F:=(E)(6)F:=i文法符号状态i+*()#ETF0(S0)S5S41231(S1)S6ACCEPT2(S2)R2S7R2R23(S3)R4R4R4R4 4(S4)S5S48235(S5)R6R6R6R66(S6)S5S4937(S7)S5S4108(S8)S6S119(S9)R1S7R1R110(S10)R3R3R3R311(S11)R5R5R5R5第五章第五章 语法分析语法分析-自下而上分析自下而上分析812022-8-5中南大学软件学院 陈志刚 i +*()#E T

50、 F 0 S5 S4 1 2 3 1 S6 ACCEPT 2 R2 S7 R2 R2 3 R4 R4 R4 R4 4 S5 S4 8 2 3 5 R6 R6 R6 R6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 R1 S7 R1 R1 10 R3 R3 R3 R3 11 R5 R5 R5 R5 第五章第五章 语法分析语法分析-自下而上分析自下而上分析822022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析832022-8-5中南大学软件学院 陈志刚第五章第五章 语法分析语法分析-自下而上分析自下而上分析842022-8-5中