编译原理语法分析——自下而上分析.pptx

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

1、第五章 语法分析自下而上分析自上而下分析法(Top-down)(Top-down)自下而上分析法(Bottom-up)(Bottom-up)第1页/共174页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法(Top-down)(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找 匹配 的推导推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序F优点：直观、简单和宜于手工实现。第2页/共174页语法分析的方法：自下而上分

2、析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归归约约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LRLR分析法：规范归约第3页/共174页G(E)：E i|E+E|E-E|E*E|E/E|(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE第4页/共174页采用“移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式

3、的候选式时，即把栈顶的这一部分替换成(归约归约为)该产生式的左部符号。第5页/共174页例：设文法G(S)：(1)S aAcBe (2)A b (3)A Ab (4)B d试对abbcdeabbcde进行“移进归约”分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e第6页/共174页第7页/共174页bdbaceSABA分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串第8页/共174页5.5.1 1.2.2 规范归约定义：令G G是一个文法，S S是文法的开始符号，

4、假定是文法G G的一个句型，如果有 且 则 称是句型相对于非终结符A A的短语。特别是，如果有A A,则称 是句型相对于规则A A 的直接短语。一个句型的最左直接短语称为该句型的句柄。第9页/共174页考虑文法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+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i1第10页/共174页在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终

5、结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i2第11页/共174页可用句柄来对句子进行归约句型 归约规则abbcde (2)A baAbcde (3)A AbaAcde (4)B daAcBe (1)S aAcBe S第12页/共174页定义：假定 是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即 0=S 3 对任何i，0 i n，i-1是从 i经把句柄替换成为相应产生式左部符号而得到的。第13页/共174页把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde

6、aAbcde aAbcde a abbcde bbcde 显然这是一个最右推导。规范归约规范归约是关于是一个最右推导最右推导的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为规范句型。第14页/共174页bdbaceSABAdbaceSABAdaceSABaceSABS第15页/共174页5.1.3 符号栈的使用和分析树的表示栈是语法分析的一种基本数据结构。#作为栈底符号考虑文法G(E)：E T|E+T T F|T*F F (E)|i输入串为i1*i2+i3，分析步骤为：第16页/共174页步骤 符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i

7、3#归，用Fi3#T*i2+i3#归，用TF4#T*i2+i3#进nG(E)：E T|E+T T F|T*F F (E)|i第17页/共174页步骤 符号栈输入串动作4#T*i2+i3#进5#T*i2+i3#进6#T*F+i3#归，用Fi7#T+i3#归，用TT*F8#E+i3#归，用ET9#E+i3#进nG(E)：E T|E+T T F|T*F F (E)|i第18页/共174页步骤 符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归，用Fi12#E+T#归，用TF13#E#归，用EE+T14#E#接受nG(E)：E T|E+T T F|T*F F (E)|i第19页/共17

8、4页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓 归约归约 ，是指根据文法的产生式规则，把产生式的右部替换成左部符号。回顾第20页/共174页归约采用“移进归约移进归约”思想进行自下而上分析。基本思想：用一个寄存符号的先进后出栈栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约归约为)该产生式的左部符号。第21页/共174页规范归约定义：令G G是一个文法，S S是文法的开始符号，假定是文法G G的一个句型，如果有 且

9、则 称是句型相对于非终结符A A的短语。特别是，如果有A A,则称 是句型相对于规则A A 的直接短语。一个句型的最左直接短语称为该句型的句柄。第22页/共174页定义：假定 是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即 0=S 3 对任何i，0 i n，i-1是从 i经把句柄替换成为相应产生式左部符号而得到的。第23页/共174页步骤 符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用Fi3#T*i2+i3#归，用TF4#T*i2+i3#进nG(E)：E T|E+T T F|T*

10、F F (E)|i第24页/共174页步骤 符号栈输入串动作4#T*i2+i3#进5#T*i2+i3#进6#T*F+i3#归，用Fi7#T+i3#归，用TT*F8#E+i3#归，用ET9#E+i3#进nG(E)：E T|E+T T F|T*F F (E)|i第25页/共174页步骤 符号栈输入串动作9#E+i3#进10#E+i3#进11#E+F#归，用Fi12#E+T#归，用TF13#E#归，用EE+T14#E#接受nG(E)：E T|E+T T F|T*F F (E)|i第26页/共174页5.2 5.2 算符优先分析算符优先分析四则运算的优先规则：先乘除后加减，同级从左到右考虑二义文法文法

11、G(E)：G(E)：E i|E+E|E-E|E*E|E/E|(E)它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。第27页/共174页例如：句子i+i-i*(i+i)i+i-i*(i+i)Ei()i*EiEE+EEE-ii+EEE第28页/共174页Ei()i*EiEE+EEE-ii+EEE返回第29页/共174页句子i+i-i*(i+i)的归约过程是：(1)i+i-i*(i+i)(2)E+i-i*(i+i)(3)E+E-i*(i+i)(4)E-i*(i+i)(5)E-E*(i

12、+i)(6)E-E*(E+i)(7)E-E*(E+E)(8)E-E*(E)(9)E-E*E(10)E-E(11)E第30页/共174页起决定作用的是相邻的两个算符之间的优先关系。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。第31页/共174页首先必须定义任何两个可能相继出现的终结符a a与b b的优先关系 三种关系a a b ab a的优先级低于b ba a b a b a的优先级等于b ba a b a b a的优先级高于b b注意：与数学上的=不同+a a b b并不意味着b b a a，如 (+和 +(第32页/共174页算符优先文法及优先

13、表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。第33页/共174页假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab当且仅当文法G中含有形如Pab或PaQb的产生式；n如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab，ab 则称G是一个算符优先文法。2.ab当且仅当G中含有形如PaR的产生式，而R b或R Qb；3.ab 当且仅当G中含有形如PR

14、b的产生式，而 R a或R aQ。第34页/共174页例:考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i由第(4)条规则，有()；由规则EET和TT*F，有 *；由(2)TT*F 和(3)FP F，可得*；由(1)EET和E E+T，可得+；由(3)FP F和F P F，可得。由(4)P(E)和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有(+、(*、(和(i。第35页/共174页 优先关系表第36页/共174页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。2.a

15、b当且仅当G中含有形如PaR的产生式，而R b或R Qb；3.ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。n确定满足关系 和的所有终结符对：1.ab 当且仅当文法G中含有形如Pab或PaQb的产生式；第37页/共174页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系 和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：ab当且仅当G中含有形如PaR的产生式，而R b或R Qb；第38页/共174页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的

16、每个候选式，可找出所有满足ab的终结符对。确定满足关系 和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：3.ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。第39页/共174页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系 和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：比较比较第40页/共174页q有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系 和的所有终结符对。假定有个产生式的一个候选

17、形为aP 那么，对任何b FIRSTVT(P)，有 a b。假定有个产生式的一个候选形为Pb 那么，对任何a LASTVT(P)，有 ab。第41页/共174页首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式Pa或PQa，则a FIRSTVT(P)；2.若a FIRSTVT(Q)，且有产生式PQ，则a FIRSTVT(P)。第42页/共174页数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当a FIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP

18、，a的符号对(P，a)全都放在STACK之中。第43页/共174页运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。第44页/共174页如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把(P，a)下推进STACK栈 END；第45页/共174页主程序：BEGIN FOR 每个非终结符P和终结符a DO FP

19、，a:=FALSE；FOR 每个形如Pa或PQa的产生式 DO INSERT(P，a)；WHILE STACK 非空 DOBEGIN 把STACK的顶项，记为(Q，a)，上托出去；FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END第46页/共174页这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a|FP，a=TRUE同理，可构造计算LASTVT的算法。第47页/共174页构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P a或P aQ，则a LAS

20、TVT(P)；2.若a LASTVT(Q)，且有产生式P Q，则a LASTVT(P)。第48页/共174页使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：第49页/共174页FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF i n-2且Xi和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2；IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia；IF Xi为非

21、终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END第50页/共174页例:考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i1.计算文法G的FIRSTVT和LASTVT;2.构造优先关系表;3.G是算符优先文法吗?第51页/共174页第52页/共174页G结论:G是算符优先文法q G的算符优先关系表第53页/共174页回顾定义任何两个可能相继出现的终结符a a与b b的优先关系 三种关系a a b ab a的优先级低于b ba a b a b a的优先级等于b ba a b a b a的优

22、先级高于b b注意：与数学上的=不同，a a b b并不意味着b b a a第54页/共174页假定G是一个不含-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab当且仅当文法G中含有形如Pab或PaQb的产生式；n如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：ab，ab，ab 则称G是一个算符优先文法。2.ab当且仅当G中含有形如PaR的产生式，而R b或R Qb；3.ab 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。第55页/共174页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定

23、满足关系 和的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：比较比较第56页/共174页q有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系 和的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何b FIRSTVT(P)，有 a b。假定有个产生式的一个候选形为Pb 那么，对任何a LASTVT(P)，有 ab。第57页/共174页首先讨论构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式Pa或PQa，则a FIRSTVT(P)；2.若a FIRSTVT(Q)，且

24、有产生式PQ，则a FIRSTVT(P)。第58页/共174页构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P a或P aQ，则a LASTVT(P)；2.若a LASTVT(Q)，且有产生式P Q，则a LASTVT(P)。第59页/共174页使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：第60页/共174页FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和Xi+1均为终结符 THEN 置XiXi+1 IF i n-2且Xi

25、和Xi+2都为终结符 但Xi+1为非终结符 THEN 置XiXi+2；IF Xi为终结符而Xi+1为非终结符 THENFOR FIRSTVT(Xi+1)中的每个a DO 置 Xia；IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END第61页/共174页算符优先分析算法可归约串，句型，短语，直接短语，句柄，规范归约。一个文法G G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。第62页/共174页考虑下面的文法G(E)：(1)EE+T|T

26、(2)TT*F|F (3)FP F|P (4)P(E)|iEEF+*TiFTFTP+ETP句型：T+F*P+i短语：直接短语：句柄：素短语：最左素短语：,T+F*P+iT,F,P,F*P,iT+F*PT,F,P,iTF*P,iF*P第63页/共174页算符优先文法句型(括在两个之间)的一般形式写成：#N1a1N2a2NnanNn+1#其中，每个ai都是终结符，Ni是可有可无的非终结符。定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 NjajNiaiNi+1，aj-1aj aj aj+1，ai-1ai aiai+1第64页/共174页算符优先分析算法使用一个符号栈S，用它

27、寄存终结符和非终结符，k代表符号栈S的使用深度。第65页/共174页k:=1;Sk:=#;REPEAT 把下一个输入符号读进a中；IF Sk VT THEN j:=k ELSE j:=k-1;WHILE Sja DOBEGIN REPEAT Q:=Sj;IF Sj-1 VT 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 THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR/*调用出错诊察程序*/UNTIL a=#自左至右，终结符对终结符，非终

28、结符对非终结符，而且对应的终结符相同。N X1 X2 Xk-j Sj+1 Sj+2 Sk第66页/共174页在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。第67页/共174页算符优先分析一般并不等价于规范归约。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第68页/共174页算符优先分析法特点：优点:简

29、单，快速缺点:可能错误接受非法句子，能力有限.算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL 60第69页/共174页优先函数把每个终结符 与两个自然数f(f()与g(g()相对应，使得若 1 1 2 2，则f(f(1 1)g(g(g(2 2)f f称为入栈优先函数，g g称为比较优先函数。优点:便于比较，节省空间；缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。第70页/共174页文法G(E)G(E)(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的优先函数如下表第71页/共174页有许多

30、优先关系表不存在优先函数，如：不存在对应的优先函数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如果优先函数存在，则不唯一(无穷多)第72页/共174页如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:1 1 对于每个终结符a a，令其对应两个符号f fa a和g ga a，画一以所有符号和为结点的方向图。如果a ab b，则从f fa a画一条弧至g gb b，如果a ab b，则画一条弧从g gb b至f fa a 。2 2 对每个结点都赋予一个数，此数等于

31、从该结点出发所能到达的结点(包括出发点自身)。赋给f fa a的数作为f(a)f(a)，赋给g ga a的数作为g(a)g(a)。3 3 检查所构造出来的函数f f和g g是否与原来的关系矛盾。若没有矛盾，则f f和g g就是要求的优先函数，若有矛盾，则不存在优先函数。第73页/共174页现在必须证明：若ab，则f(a)g(b)；若ab，则f(a)g(b)。第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。至于ab和ab的情形，只须证明其一。1 1 对于每个终结符a a，令其对应两个符号f fa a和g ga a

32、，画一以所有符号和为结点的方向图。如果a ab b，则从f fa a画一条弧至g gb b，如果a ab b，则画一条弧从g gb b至f fa a 。第74页/共174页如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a)g(b)。我们所需证明的是，在这种情况下，f(a)g(b)不应成立。我们将指出，如果f(a)g(b)，则根本不存在优先函数。假若f(a)g(b)，那么必有如下的回路：第75页/共174页 因此有ab,a1b,a1b1,ambm,abm对任何优先函数f和g来说，必定有f(a)g(b)f(a1)g(b1)f(am)g(bm)f(a)从而导致f(

33、a)f(a)，产生矛盾。因此，不存在优先函数f和g。fa1fafamgb1gbgbm第76页/共174页例:取前面文法G(E)G(E)(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的终结符+，*，i i第77页/共174页f+f*f fig+g*g gi第78页/共174页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适

34、合分析表达式。优先关系表的构造：FIRSTVTFIRSTVT,LASTVT,LASTVT优先函数算符优先分析法回顾第79页/共174页规范归约定义：令G G是一个文法，S S是文法的开始符号，假定是文法G G的一个句型，如果有 且 则 称是句型相对于非终结符A A的短语。特别是，如果有A A,则称 是句型相对于规则A A 的直接短语。一个句型的最左直接短语称为该句型的句柄。第80页/共174页定义：假定 是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即 0=S 3 对任何i，0 i n，i-1是从 i经把句柄替换成为相应产生式

35、左部符号而得到的。第81页/共174页5.3 LR分析法LR分析法：1965年 由Knuth提出分析表产生器文法分析表输入输出 产生分析表 LR分析器工作LR分析总 控程 序分析表第82页/共174页主要介绍1.总控程序(LR分析器)的处理思想2.LR分析表的构造方法及原理第83页/共174页分析器规范归约的关键问题是寻找句柄.“历史”：已移入符号栈的内容“展望”：根据产生式推测未来可能遇到的输入符号“现实”：当前的输入符号第84页/共174页LR分析方法：把历史及展望综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作 LR分析程 序状态符号分析栈 action goto LR分析

36、表a1a2ai an#输入串 输出第85页/共174页LR分析器的核心是一张分析表：ACTIONs，a：当状态s面临输入符号a时，应采取什么动作.GOTOs，X：状态s面对文法符号X时，下一状态是什么第86页/共174页每一项ACTIONs，a所规定的四种动作:1.移进 把(s，a)的下一状态s和输入符号a推进栈，下一输入符号变成现行输入符号.2.归约 指用某产生式A进行归约.假若 的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r,A)的下一状态s=GOTOsm-r,A和文法符号A推进栈.3.接受 宣布分析成功，停止分析器工作.4.报错第87页/共174页分

37、析开始时:状态 已归约串 输入串 (s0，#，a1a2 an#)以后每步的结果可以表示为:(s0 s1 sm，#X1 Xm，aiai+1 an#)第88页/共174页(s0 s1 sm，#X1 Xm，aiai+1 an#)分析器根据ACTION(sm,ai)确定下一步动作1.若ACTION(sm,ai)为移进，且s=GOTO(sm,ai),，则三元式格局变为:(s0 s1 sms，#X1 Xm ai，ai+1 an#)2.若ACTION(sm,ai)为按A归约，三元式变为:(s0 s1 sm-rs，#X1 Xm-rA，aiai+1 an#)此处,s=GOTO(sm-r,A),r为 的长度,=X

38、m-r+1 Xm3.若ACTION(sm,ai)为接受，则三元式不再变化，变化过程终止，宣布分析成功.4.若ACTION(sm,ai)为报错，则三元式变化过程终止，报告错误.(s0 s1 sm-r sm-r+1 sm，#X1 Xm-r Xm-r+1 Xm，aiai+1 an#)(s0 s1 sm-r，#X1 Xm-r，aiai+1 an#)(s0 s1 sm-rs，#X1 Xm-rA，aiai+1 an#)第89页/共174页LR分析器示例：文法G(E)：(1)EET(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi第90页/共174页其LR分析表为:第91页/共174页假定输入串为i

39、*i+i，LR分析器的工作过程:步骤状态符号输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#TiF*第92页/共174页假定输入串为i*i+i，LR分析器的工作过程:步骤状态符号输入串(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#+iTF*TFiE第93页/共174页步骤状态符号输入串(10)016#E+i#(11)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15)接受+

40、iTF*TFiEiTFE第94页/共174页定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为LR文法。定义：一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法.非LR结构LR文法不是二义的，二义文法肯定不会是LR的。S iCtS|iCtSeS 栈 输入 iCtS e#第95页/共174页项目集族和LR(0)分析表的构造假定 是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即 0=S 3 对任何i，0 i n，i-1是从 i经把句柄替换

41、成为相应产生式左部符号而得到的。第96页/共174页项目集族和LR(0)分析表的构造规范归约过程中栈内的符号串和扫描剩下的输入符号串构成了一个规范句型栈内的如果出现句柄，句柄一定在栈的顶部Xa 句柄 句柄 柄句a 柄句a 栈内永远不会出现句柄之后的符号！第97页/共174页项目集族和LR(0)分析表的构造字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1 i r)是的活前缀。(必为终结符串)对于一个文法G,可以构造一个DFA,它能识别G的所有活前缀

42、.第98页/共174页指导思想目标驱动踢足球“如果你不知道怎样踢球，就往球门方向踢”施拉普纳LR分析“如果你不知道怎样分析，就保证栈中总是活前缀”1.一个语言都有哪些一个语言都有哪些活前缀活前缀?2.那些字符串是那些字符串是活前缀活前缀?3.能不能构造一个能不能构造一个DFA来识来识别别活前缀活前缀?第99页/共174页文法G的每个产生式的右部添加一个圆点称为G的LR(0)项目如:AXYZ有四个项目：A.XYZ AX.YZ AXY.Z AXYZ.FA.称为归约项目F归约项目 S.称为接受项目FA.a (a VT)称为移进项目F A.B (B VN)称为待约项目.第100页/共174页文法G(S

43、)S E EaA|bB AcA|d BcB|d 该文法的项目有：1.S E2.S E3.EaA 4.EaA5.EaA6.AcA7.AcA8.AcA9.Ad 10.Ad11.EbB12.EbB13.EbB14.BcB15.BcB 16.BcB17.Bd18.Bd第101页/共174页构造识别文法所有活前缀的NFA方法 1.若状态i为XX1 Xi-1.Xi Xn，状态j为XX1 Xi-1Xi.Xi+1 Xn，则从状态i画一条标志为Xi的有向边到状态j；2.若状态i为X.A ，A为非终结符，则从状态i画一条 边到所有状态A.。把识别文法所有活前缀的NFA确定化。第102页/共174页67891045

44、3121112131415161817 a AEbBBcAcd识别活前缀的NFA第103页/共174页识别活前缀的DFA0:S E EaA EbB 4:AcA AcA Ad 2:EaA AcA Ad1:S E3:EbB BcB Bd5:BcB BcB Bd 11:Bd9:BcB7:EbB10:Ad6:EaA 8:AcAccbEadAccdddBAB第104页/共174页构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。第105页/共174页有效项目我们说项目A 1.2对活前缀1是有效的，其条件是存在规范推导q在任何时候，分析栈中的活前缀X1X2 Xm的有效项

45、目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2 Xm后到达的那个项目集(状态)。第106页/共174页结论:若项目A.B 对活前缀=是有效的且B 是一个产生式，则项目B .对=也是有效的。所以，B .对=也是有效的。设，那么第107页/共174页文法G(S)S E EaA|bB AcA|d BcB|d 考虑：项目：B c.BB .cB B .d 活前缀：bcS E bB bcBS E bB bcB bccBS E bB bcB bcd 项目A 1.2对活前缀1是有效的，其条件是存在规范推导第108页/共174页LR(0)项目集规范族的构造项目集规范族的

46、构造假定文法G是一个以S为开始符号的文法，我们构造一个G，它包含了整个G，但它引进了一个不出现在G中 的 非 终 结 符S，并加进一个新产生式S S，而这个S 是G 的开始符号。那么，我们称G 是G的拓广文法。这 样，便 会 有 一 个 仅 含 项 目S S.的 状 态，这 就 是 唯 一 的“接 受”态。第109页/共174页假定I是文法G 的任一项目集，定义和构造I的闭包CLOSURE(I)如下：1.I的任何项目都属于CLOSURE(I)；2.若A B 属于CLOSURE(I)，那么，对任何关于B的产生式B，项目B 也属于CLOSURE(I)；3.重复执行上述两步骤直至CLOSURE(I)

47、不再增大为止。P50：NFA确定化设I是的状态集的一个子集，定义I的-闭包-closure(I)为:i)若s I，则s-closure(I)；ii)若s I，则从s出发经过任意条 弧而能到达的任何状态s都属于-closure(I)-closure(I)=I s|从某个s I出发经过任意条 弧能到达s 2.若状态i为X.A ，A为非终结符，则从状态i画一条 边到所有状态A.。第110页/共174页为了识别活前缀，我们定义一个状态转换函数GO是一个状态转换函数。I是一个项目集，X是一个文法符号。函数值GO(I，X)定义为：GO(I，X)CLOSURE(J)其中 J任何形如A X 的项目|A X 属

48、于I。G直观上说，若I是对某个活前缀 有效的项目集，那么，GO(I，X)便是对 X 有效的项目集。nP50：设a是 中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。第111页/共174页文法G(S)S E EaA|bB AcA|d BcB|d I0=S E,EaA,EbB GO(I0,E)=closure(J)=closure(SE)=SE=I1 GO(I0,a)=closure(J)=closure(EaA)=EaA,AcA,Ad)=I2 GO(I0,b)=closure(J)=closure(E b.B)=E b.B,B.cB,B.d

49、=I3第112页/共174页构造文法G的拓广文法G 的LR(0)项目集规范族算法：PROCEDURE ITEMSETS(G)；BEGINC:=CLOSURE(SS)；REPEAT FOR C中每个项目集I和G 的每个符号X DO IF GO(I，X)非空且不属于C THEN 把GO(I，X)放入C族中;UNTIL C不再增大END转换函数GO把项目集连接成一个DFA转换图.第113页/共174页0:S E EaA EbB 4:AcA AcA Adc5:BcB BcB Bd c3:EbB BcB Bdb1:S EE2:EaA AcA Ada11:Bdd8:AcAAccd10:Addd9:BcBB

50、6:EaA A7:EbBB第114页/共174页回顾：规范归约定义：令G G是一个文法，S S是文法的开始符号，假定是文法G G的一个句型，如果有 且 则 称是句型相对于非终结符A A的短语。特别是，如果有A A,则称 是句型相对于规则A A 的直接短语。一个句型的最左直接短语称为该句型的句柄。第115页/共174页定义：假定 是文法G的一个句子，我们称序列 n，n-1，0 是的一个规范归约，如果此序列满足：1 n=2 0为文法的开始符号，即 0=S 3 对任何i，0 i n，i-1是从 i经把句柄替换成为相应产生式左部符号而得到的。第116页/共174页5.3 LR分析法LR分析法：1965