【教学课件】第五章语法分析-自下而上分析.ppt

第五章第五章语法分析语法分析自下而上自下而上分析分析所谓自下而上分析法就是从输入串开始，逐步进行所谓自下而上分析法就是从输入串开始，逐步进行“归约归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上向上“归约归约”，直到根结。，直到根结。5.1 自下而上分析基本问题自下而上分析基本问题 我们先讨论自下而上分析的一些基本思想和我们先讨论自下而上分析的一些基本思想和 基本概念：基本概念：归约归约自下而上分析的关键问题是寻找自下而上分析的关键问题是寻找可归约串可归约串。对。对“可归约串可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。在算符优概念的不同定义，就形成了不同的自下而上的分析方法。在算符优先分析法中我们用先分析法中我们用“最左素短语最左素短语”来刻画来刻画“可归约串可归约串”，在，在“规范规范归约归约”中，则用中，则用“句柄句柄”来刻画来刻画“可归约串可归约串”5.1.2 规范归约简述规范归约简述 在这一部分应掌握在这一部分应掌握短语短语和和直接短语直接短语和和句柄句柄三个重要概念三个重要概念 令令G是一个文法，是一个文法，S是文法的开始符，假定是文法的开始符，假定是文法是文法G的一个句型，如果有：的一个句型，如果有：S*A 且且 A+则称则称 是句型是句型相对于非相对于非终结符终结符A的的短语短语。特别是，如果有。特别是，如果有 A 则称则称 是句型是句型相对于规则相对于规则A 的的直接短语直接短语，一个句型的最左直接短语成为该句型的，一个句型的最左直接短语成为该句型的句句柄柄。注意：短语的。注意：短语的两两个条件是：个条件是：S*A 且且 A+例例5.1考虑文法：考虑文法：E T|E+T T F|T*F F i|(E)（5.2）对于句型对于句型i*i+i 推导推导解：解：EE+TT+TT*F+TF*F+Ti*F+Ti*i+F i*i+i 尽管有尽管有E +i+i 但是但是,i+i 并不是该句型的一并不是该句型的一个短语，因为不存在从个短语，因为不存在从E(文法开始符）到文法开始符）到i*E的推的推导。但是，导。但是，i,i*i,和和i*i+i 自身都是句型自身都是句型i*i+i 的短的短语。而且为为直接短语。语。而且为为直接短语。例例5。2 上题文法（上题文法（5。2）的另一个句型）的另一个句型E+T*F+i 的短语有的短语有 E+T*F+i ,E+T*F,T*F,和和i.其其中中T*F和和i为直接短语，为直接短语，T*F为句柄。为句柄。解：解：EE+TE+T+TE+T*F+TE+T*F+F E+T*F+i 关于关于规范归约规范归约精确的说，假定精确的说，假定 是文法是文法G G的一个句子，的一个句子，我们称序列我们称序列 n n n-1n-1 n-2n-2,。,0 0 是是 的一个规范规约，如果此序列满足：的一个规范规约，如果此序列满足：（1 1）n n=;(2(2）0 0 为文法的开始符为文法的开始符,即即 0 0=S;=S;（3 3）对于任何的）对于任何的i i，0i=n,0i=n,i-1i-1 是从是从 i i 经把句柄替经把句柄替换为相应产生式的左部符号而得到的。换为相应产生式的左部符号而得到的。容易看到，规范归约是关于容易看到，规范归约是关于的一个最右推导的的一个最右推导的逆过程。因此规范归约也成最左归约。逆过程。因此规范归约也成最左归约。在形式语言中，最右推导常被称为规范推导。由规在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范举行。如果文法范推导所得的句型称为规范举行。如果文法G G是无二义是无二义的，那么规范推导的逆过程必是规范归约。的，那么规范推导的逆过程必是规范归约。5.1.3 5.1.3 符号栈的使用与语法树的表示符号栈的使用与语法树的表示 本节重点掌握符号栈的使用请阅读本节重点掌握符号栈的使用请阅读P87P87相应段落。相应段落。现在举个例子以加深对这一节的理解。现在举个例子以加深对这一节的理解。例例5.3：对于文法（：对于文法（5.2）输入串）输入串i1*i2+i3 的分析（规范归约）步骤的分析（规范归约）步骤可表示如下：可表示如下：步骤步骤 符号栈符号栈 输入串输入串 动作动作0#i1*i2+i3#预备预备1#i1 *i2+i3#读入读入i12#F *i2+i3#归约，归约，Fi 3#T *i2+i3#归约，归约，T F4#T*i2+i3#读入读入5#T*i2 +i3#读入读入6#T*F +i3#归约，归约，F i7#T +i3#归约，归约，T T*F8#E +i3#归约，归约，E T9#E+i3#读入读入10#E+i3#读入读入11#E+F#归约归约,F i12#E+T#归约归约,T F13#E#归约归约，E E+T14#E#接受接受5.2 算符优先分析算符优先分析 5.2.1 算符优先文法及优先表的构造算符优先文法及优先表的构造 一个文法，如果它的任何产生式的右部都不含量个相继一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：（并列）的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为则我们称该文法为算符文法算符文法。在后面的定义中，在后面的定义中，a、b代表任意终结符；代表任意终结符；P、Q、R代表任代表任意非终结符；意非终结符；代表有终结符和非终结符组成的任意序列，代表有终结符和非终结符组成的任意序列，包括空字。包括空字。假定假定G是一个不含是一个不含-产生式的算符文法。对于任何一对终产生式的算符文法。对于任何一对终结符结符a、b，我们说：，我们说：（1)a b 当且仅当文法当且仅当文法G中含有形如中含有形如P ab或或P aQb的产生式的产生式;(2)ab当且仅当当且仅当G中含有形如中含有形如P Rb的产生式，的产生式，R而而R+a或或R+aQ;如果一个文法如果一个文法G中的任何终结符对（中的任何终结符对（a,b）至多只满足下述三关）至多只满足下述三关系之一：系之一：a=b,ab 则称则称G是一个是一个算符优先文法算符优先文法。应掌握应掌握算符优先表算符优先表的构造方法。的构造方法。通过检查通过检查G的每个产生式的每个候选式，可以找出满足的每个产生式的每个候选式，可以找出满足a=b的终结符对。为了找出所有满足关系的终结符对。为了找出所有满足关系的终结符对，我们需的终结符对，我们需要对要对G的每个非终结符的每个非终结符P 构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P):FIRSTVT(P)=a|P+a或或P+Qa,a VT而而 Q VN LASTVT(P)=a|P+a或或P+aQ,a VT而而 Q VN 有了这两个集合后，就可以通过检查每个产生式的候选式确定有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系满足关系的所有终结符对。例如：假定有个产生式的一个的所有终结符对。例如：假定有个产生式的一个候选式为候选式为 aP 那末，对任何那末，对任何b FISTVT(P),我们有我们有ab.我们首先讨论构造集合我们首先讨论构造集合FIRSTVT(P)的算法。按定的算法。按定义，我们可用下面两条规则来构造集合义，我们可用下面两条规则来构造集合FIRSTVT(P):(1)若有产生式若有产生式Pa或或P Qa,则则a FIRSTVT(P)(2)若若a FIRSTVT(Q)，且有产生式且有产生式P Q(3)则则a FIRSTVT(P)(4)同样我们可以构造同样我们可以构造LASTVT(P)的算法。的算法。(5)在我们有了每个非终结符在我们有了每个非终结符P 的的FISTVT(P)和和LASTVT(P)之后我们就能够造文法之后我们就能够造文法G的优先表。其的优先表。其算法如下：算法如下：FOR 每一条产生式每一条产生式PX1X2Xn(6)FOR i:=1 TO n-1 DO(7)BEGIN(8)IF Xi 和和 Xi+1 均为终结符均为终结符THEN 置置 Xi=Xi+1 IF I=n-2且且Xi和和Xi+2都为终结符，而都为终结符，而Xi+1为非终为非终结符，则置结符，则置Xi=Xi+2 IF Xi为终结符而为终结符而Xi+1为非终结符为非终结符 THEN FOR FISTVT(Xi+1)中的每个中的每个a DO 置置 Xia END 至此我们完成了从文法至此我们完成了从文法G构造优先表的算法。构造优先表的算法。5.2.2 算符优先分析算法算符优先分析算法 为了刻画什么是为了刻画什么是“可归约串可归约串”我们将定义算符优先文法的句型的我们将定义算符优先文法的句型的“最左素短语最左素短语”这个概念。这个概念。所谓素短语是指这样的一个短语，它至少含有一个终结符，并且出所谓素短语是指这样的一个短语，它至少含有一个终结符，并且出它自身外，不再含有更小的素短语。它自身外，不再含有更小的素短语。所谓最左素短语，是指处于句型最左边的那个素短语。所谓最左素短语，是指处于句型最左边的那个素短语。我们把算符优先文法句型（括在两个我们把算符优先文法句型（括在两个#号之间）的一般形式写成：号之间）的一般形式写成：#N1a1N2a2Nnan Nn+1#（5.4）其中每个其中每个ai都是终结符，都是终结符，Ni是可有可无的非终结符。是可有可无的非终结符。一个算符优先文法一个算符优先文法G的任何句型（的任何句型（5.4）的最左素短语是满足如下条）的最左素短语是满足如下条件的最左子串：件的最左子串：NjajNia i+1,a j-1a i+1 根据这个最左素短语的定义我们可以构造算符优先根据这个最左素短语的定义我们可以构造算符优先分析算法。参考分析算法。参考P935.2.3 优先函数优先函数 在实际实现算符优先分析算法时，一般不用优先表而在实际实现算符优先分析算法时，一般不用优先表而是用两个优先函数是用两个优先函数f f 和和g g。我们把每个终结符号。我们把每个终结符号 与两与两个自然数个自然数f(f()和和g(g()相对应，使得相对应，使得 若若 1 1 2 2 则则 f(f(1)g(1)g(1)g(2)2)函数函数f f 称为入栈优先函数，称为入栈优先函数，g g称为比较优先函数。称为比较优先函数。构造优先函数的方法应在必须掌握之列。构造优先函数的方法应在必须掌握之列。如果优先函数存在，那么，从优先表构造优先函如果优先函数存在，那么，从优先表构造优先函数的一个简单方法是：数的一个简单方法是：（1 1）对于每个终结符）对于每个终结符a(a(包括包括#）令其对应两个符号）令其对应两个符号fafa和和g ga a ,画一张以所有符号画一张以所有符号fafa和和gaga为结点的方向图，如果为结点的方向图，如果a=b,a=b,那么，就从那么，就从fafa画一箭弧至画一箭弧至g gb;b;如果如果a=b a=b 则画一条从则画一条从gbgb到到fafa的箭弧。的箭弧。(2)对于每个结点都赋予一个数，此数等于从该结点所能对于每个结点都赋予一个数，此数等于从该结点所能到达结点（包括出发结点自身在内）的个数。赋给到达结点（包括出发结点自身在内）的个数。赋给fa的数作为的数作为f(a)，赋给，赋给gb的数作为的数作为g(b).(3)检查构造出来的函数检查构造出来的函数f 和和g，看它们同原来的关系表是，看它们同原来的关系表是否有矛盾。如果没矛盾，则否有矛盾。如果没矛盾，则f 和和g就是所要的优先函数。就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。如果有矛盾，那么，就不存在优先函数。例题例题5。5 就是构造优先函数的例子，望同学们好好就是构造优先函数的例子，望同学们好好研究一下。研究一下。5。2。4 算符优先分析中的出错处理算符优先分析中的出错处理5。3；5。4 根据课本说明不作考核要求根据课本说明不作考核要求例题与习题解答例题与习题解答例例5.1 设有文法设有文法G和输入串和输入串$G:SaABe$:abbcde A Abc|b B d 通过语法树能使我们直观的理解规范通过语法树能使我们直观的理解规范“归约归约”、“句柄句柄”等概念。等概念。上图中图上图中图a是输入串是输入串abbcde的语法树，一个句型的句柄是该句的语法树，一个句型的句柄是该句型语法树中最左子树的末端结的自左至右排列。则此子树为型语法树中最左子树的末端结的自左至右排列。则此子树为A b其末端其末端b为句型为句型abbcde的句柄。将其剪掉（归约）后如图的句柄。将其剪掉（归约）后如图b，其最，其最左子树左子树A Abc其末端结其末端结Abc为句型为句型aAbcBe的最左子树末端结故的最左子树末端结故为句柄。图为句柄。图c表明句型表明句型aAde的句柄为的句柄为d。将其归约句型。将其归约句型aABe的最的最左子树为其自身。即为其自身句柄。左子树为其自身。即为其自身句柄。例例5.2考虑下面文法：考虑下面文法：1。EE+T|T 2.T T*F|F 3.F P F|P 4.P(E)|i 构造优先关系表构造优先关系表 解：解：根据产生式根据产生式4 我们有我们有(=),从产生式从产生式1，2 的的+T和和T*我们有我们有+*,从产生式从产生式2，3的的*F和和P 我们有我们有*+,同理可得：同理可得：。由产生式由产生式P(E)和和E E+T T+T T*F+T F*F+T P F*F+T i F*F+T 我们可以得到我们可以得到(+,(*,(,(i.总之，我们可以按定义得到对于文法总之，我们可以按定义得到对于文法G的任何终结符对（的任何终结符对（a,b)的，的，至多只有一种优先关系。从而得到下面的优先表：至多只有一种优先关系。从而得到下面的优先表：优先关系表优先关系表 +*i ()#+*i ()#例例5.3 对下列文法对下列文法G:S#S#P S|i S D(R)D i R R;P|P 求出每个非终结符的求出每个非终结符的FIRSTVT集和集和LASTVT集，并构造算符优先关集，并构造算符优先关系矩阵。系矩阵。文法文法G每个非终结符的每个非终结符的FIRSTVT集合集合FIRSTVT(S)=#FIRSTVT(P)=i,(FIRSTVT(S)=(,i FIRSTVT(D)=i FIRSTVT(R)=;,(,I 文法文法G的每个非终结符的的每个非终结符的LASTVT集合集合LASTVT(S)=#LASTVT(P)=i,)LASTVT(S)=)LASTVT(D)=i LASTVT(R)=;,),i 优先关系矩阵优先关系矩阵 （）；i#(=;#a且且aa,ba,ca,da 且且ab,ac,ab且且bb,cb,db 且且bc,b d 第六章第六章 属性文法和语法制导属性文法和语法制导翻译（翻译（1 1）本章重点掌握前本章重点掌握前两节两节6.16.1属性文法，属性文法，6.26.2基于属性文法的基于属性文法的处理方法和处理方法和6.3 S6.3 S属性文法的自下而属性文法的自下而上计算。由于后面上计算。由于后面两节涉及打两节涉及打*号的号的LRLR分析法较多，所以分析法较多，所以不作要求。不作要求。