《编译原理课件chap05(陈火旺).ppt》由会员分享，可在线阅读，更多相关《编译原理课件chap05(陈火旺).ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章语法分析语法分析自下而上分析自下而上分析所谓自下而上分析法就是从输入串开始，逐步进行所谓自下而上分析法就是从输入串开始，逐步进行“归约归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上向上“归约归约”，直到根结。，直到根结。5.1 自下而上分析基本问题自下而上分析基本问题 我们先讨论自下而上分析的一些基本思想和我们先讨论自下而上分析的一些基本思想和 基本概念：基本概念：自底向上分析方法自底向上分析方法，也称，也称移进移进-归约分析法归约分析法实现思想实现思想（是推导的逆过程是推导的逆过程）：）：对输入符号串
2、自左向右进行扫描，并将输入符逐个移入一个对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的可可归约串归约串时，就用该产生式的左部非终结符代替相应右部的文法符号时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。符号时，则分析成功。第五章语法分析-自下而上分析移进规约分析（Shift-reduceparsing)2 2#S.R.P#符号符号栈输入串入
3、串要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是规约。第五章语法分析-自下而上分析3 3 3 3 分析过程：把输入符号串从左向右一一地移进符号分析过程：把输入符号串从左向右一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的可归约串时，就根据规则进行规约，将句形成当前句型的可归约串时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的规则的左部符号），然后
4、再检查栈内符号串是否形成新的可归约串，若有就再进行规约，否则移进符号。分析一直可归约串，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的右界符为止。最后，若栈中仅含有左进行到读到输入串的右界符为止。最后，若栈中仅含有左界符号和识别符号，则表示分析成功，否则失败。界符号和识别符号，则表示分析成功，否则失败。#S.R.PS.R.P#符号符号符号符号栈栈输输入串入串入串入串第五章语法分析-自下而上分析例1：文法SaAcBeAbAAbBd输入串abbcde#分析第五章语法分析-自下而上分析归约分析过程（移进归约）：步骤符号栈输入符号串动作1#abbcde#移进2#abbcde#移进3#abb
5、cde#归约（Ab4#aAbcde#移进5#aAbcde#归约（AAb)?6#aAcde#移进7#aAcde#移进8#aAcde#归约（Bb）9#aAcBe#移进10#aAcBe#规约SaAcBe11#S#接受SaAcBeAbAAbBd第五章语法分析-自下而上分析上述的每一步规约可以构造一颗语法树：AbBdAAbbSAbbaceBdA问题的提出：在构造语法树的过程中，何时规约？当可归约串出现在栈顶符号串中就可以规约。如何知道在栈顶符号串中已经形成可归约串？需要精确定义可规约串这个直观概念。这是自下而上分析的关键。第五章语法分析-自下而上分析自下而上分析的关键问题：如何确定可归约串？通过自底向上
6、分析算法中的优先关系来计算简单优先分析法（规范规约）：寻找句柄算符优先分析法：寻找最左素短语第五章语法分析-自下而上分析一、自底向上优先分析法概述优先分析法又可分简单优先分析法和算符优先分析法。简单优先分析法：按一定原则求出文法中所有符号（终结符和非终结符）的优先关系，按这种关系求出句柄。（规范归约从左向右的规约）；算符优先分析法：只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。按这种关系求出最左素短语。（不规范归约）简单优先分析法：准确规范，但分析效率低，实际使用价值不大；算符优先分析法：不规范，但分析速度快，适于实际使用。第五章语法分析-自下而上分析句柄的定义：令G是一文
7、法，S是文法的开始符号，是文法G的一个句型。（为确定可归约串）如果有SA且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
8、推导推导解：解：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
9、为句柄。为句柄。解：解：EE+TE+T+TE+T*F+TE+T*F+F E+T*F+I?T*F+i是否是句柄是否是句柄第五章语法分析-自下而上分析EET+TFTFFi3i2i1从从语法树中可以看出，语法树中可以看出，所以树叶的组合就是其所以树叶的组合就是其相对应的父亲的短语。相对应的父亲的短语。第五章语法分析-自下而上分析 关于关于规范归约规范归约精确的说，假定精确的说，假定 是文法是文法G G的一个句子，的一个句子，我们称序列我们称序列 n n n-1n-1 n-2n-2,。,0 0 是是 的一个规范规约，如果此序列满足：的一个规范规约，如果此序列满足：（1 1）n n=;(2(2）0 0
10、为文法的开始符为文法的开始符,即即 0 0=S;=S;（3 3）对于任何的对于任何的i i，0i=n,0i.y表示X的优先性大于Yx.y表示X的优先性小于Y对任意两个文法符号X、Y按其在句型中可能会出现的相邻关系来确定优先关系：第五章语法分析-自下而上分析确定优先关系的规则（1）X=.Y当且仅当G中存在产生式AXY（在语法树的同一层）（2）X.Y当且仅当G中存在产生式ABD，且BX和DY（X在Y的下一层或X比Y先归约规范归约/最左归约）+*第五章语法分析-自下而上分析例：有文法G(S):SbAbA(B|aBAa)解：文法符号优先关系推导如下：(1)求=.关系:由SbAb，A(B，BAa)b=.
11、A，A=.b，(=.B，A=.a，a=.)第五章语法分析-自下而上分析(2)求.关系：由SbAb且A（B可得 b.(A a可得 b.a由A(B且B(B可得(.(B aa可得(.aB Aa)可得(.关系:由SbAb，且A)可得).bAB可得B.bA a可得a.b由BAa)，且A)可得).aAa可得a.aAB可得B.aA(B(Aa)A(BBAa+文法G(S):SbAbA(B|aBAa)第五章语法分析-自下而上分析SbA(Ba)#S.b=.A=.=.(.=.a.=.).#.#寻找句柄第五章语法分析-自下而上分析简单优先文法的定义：（1）在文法符号集中，任意两个符号之间最多只有一种优先关系；（2）在文
12、法中任意两个产生式没有相同的右部。第五章语法分析-自下而上分析SbAb（BSbAbaSbAb（BAa）（BAa）SbAb（BAa）a语法树结构如下：第五章语法分析-自下而上分析从上图可以看出：(1)当b(、ba出现在某一句型中，则（和a在句柄中，b不在句柄中，则（和a必须先规约。因此b.(,b.a。(2)同样可以看出，当(，(a，(A出现在某一句型中，右边的(，a，A出现在句柄中，左边的(不在句柄中。因此，左边(.右边的(，左边(.a，左边(.b，左边a.a。第五章语法分析-自下而上分析因此，可以根据文法符号之间的优先关系确定句柄。在规范归约（最左归约）过程中，出现在栈顶的优先级相同的连续符号
13、串就是句柄。第五章语法分析-自下而上分析首先根据已知优先文法构造优先关系矩阵，设置符号栈S，算法步骤如下：分析器结构分析器结构分析器结构分析器结构:#分析程序分析程序分析程序分析程序 优先关系矩阵优先关系矩阵优先关系矩阵优先关系矩阵#符号符号符号符号栈栈输输入串入串入串入串简单优先分析法的操作步骤第五章语法分析-自下而上分析三、算符优先分析1)这是一种经典的自底向上分析法，简单直观，并被广泛使 用，开始主要是对表达式的分析，现在已不限于此。可以 用于一大类上下无关的文法.1.乘除的优先大于加减 2.同优先级的运算符左大于右 3.括号内的优先级大于括号外 于是：4+8-6/2*3 运算过程和结果
14、唯一。2)2)称为算符优先分析是因为这种方法是仿效算术式的四则运算 而建立起来的，作算术式的四则运算时，为了保证计算结果 和过程的唯一性，规定了一个统一的四则运算法则，规定运 算符之间的优先关系。第五章语法分析-自下而上分析简单优先分析法：求出文法中所有符号（终结符和非终结符）的优先关系，按这种关系求出句柄。（规范归约从左向右的规约）；算符优先分析法：只考虑算符（终结符）之间的优先关系，不考虑非终结符之间的优先关系。按这种关系求出最左素短语。（不规范归约）算符优先关系的定义第五章语法分析-自下而上分析 3)3)算符优先分析的特点算符优先分析的特点:仿效四则运算过程，仿效四则运算过程，预先预先规
15、定相邻终结符之间的优规定相邻终结符之间的优 先关系，然后利用这种优先关系来确定句型的可归约串先关系，然后利用这种优先关系来确定句型的可归约串 ，并进行规约。并进行规约。4)4)分析器结构分析器结构分析器结构分析器结构:#分析程序分析程序分析程序分析程序 优先关系矩阵优先关系矩阵优先关系矩阵优先关系矩阵#符号符号符号符号栈栈输输入串入串入串入串第五章语法分析-自下而上分析(2)算符优先文法的定义【算符文法定义】设有一文法G，如果G中没有形如ABC的产生式，其中B和C为非终结符，则称G为算符文法算符文法(或称OG文法)。第五章语法分析-自下而上分析要点任何一个产生式中都不包含两个非终结符相邻的情况
16、，就是是算符文法。或：两个非终结符之间一定通过1个或多个终结符相连。性质1：在算符文法中任何句型都不包含两个相邻的非终结符。性质2：如果Ab或（bA）出现在算符文法的句型中，其中AVN.bVT,，则中任何含b的短语必含有A。（含b的短语必含A，含A的短语不一定含b）第五章语法分析-自下而上分析【算符优先关系的定义】设G是一个算符文法，a和b是任意两个终结符，A，B，C是非终结符，算符优先关系如下(相邻关系)(1)a=.b当 且 仅 当 G中 含 有 形 如 Aab或AaBb的产生式;(2)a.b当且仅当G中含有形如ABb的产生式，且Ba或BaC。与简单优先关系区别：区分终结符与非终结符，非终结
17、符忽略与简单优先关系区别：区分终结符与非终结符，非终结符忽略不计不计第五章语法分析-自下而上分析【算符优先文法的定义】设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=.，.三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。即a=.b，a.b只有一种成立，但允许a.b，b.a同时存在。例：EE+E|E*E|(E)|i证明不是OPG文法。第五章语法分析-自下而上分析【算符优先文法的定义】设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=.，.三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。即a=.b，a.b只有一种成立，但允许
18、a.a同时存在。例：EE+E|E*E|(E)|i证明不是OPG文法。因为：EE+E，EE*E则有+.*所以不是算符优先文法。AaB，a+，BE，BCb，b*ABb，BE，b*，BaC，a+第五章语法分析-自下而上分析算符优先分析法的实现：算符优先分析法的实现：#分析程序分析程序分析程序分析程序 优先关系矩阵优先关系矩阵优先关系矩阵优先关系矩阵#符号符号符号符号栈栈输输入串入串入串入串当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终
19、结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归约约约约。表明找到了素短语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。第五章语法分析-自下而上分析(3)算符优先关系表用表格形式来表示各终结符号的优先关系，这种表称为优先表。构造优先关系表的方法：按照定义来构造按关系图来构造构造步骤：（根据算符优先关系的定义）定义两个集合：firstVT集合lastVT集
20、合。(首终结符集，尾终结符集)firstVT(B)=b|Bb或BCblastVT(B)=a|Ba或BaC+第五章语法分析-自下而上分析三种优先关系的计算：a)=.关系：AabAaBbb).关系：对于每个非终结符B的firstVT(B)有 形 如 AaB中，对 每 一 个 bfirstVT(B)。则a=.b则a.关系：每个非终结符B的lastVT(B)有形如ABb中，对每一个alastVT(B)则a.b例：为文法例：为文法 E#E#TF EE+T FPF|P ET P（E）TT*F Pi构造算符优先关系表构造算符优先关系表第五章语法分析-自下而上分析构造优先关系矩阵的算法构造优先关系矩阵的算法构
21、造优先关系矩阵的算法构造优先关系矩阵的算法FOR 每条规则每条规则Ux1x2xn DO FOR i:=1 TO n-1 DO BEGIN IF xi和和xi+1均为终结符均为终结符,THEN 置置 xi=.xi+1 IF in-2，且，且xi和和xi+2都为终结符号但都为终结符号但 xi+1为非终结符号为非终结符号 THEN 置置 xi=.xi+2 IF xi为终结符号为终结符号xi+1为非终结符号为非终结符号 THEN FOR FIRSTVT(xi+1)中的每个中的每个b DO 置置xi.xi+1 END .第五章语法分析-自下而上分析构造构造FIRSTVT(U)的算法的算法1)若有规则若有
22、规则U b或或U Vb(存在存在Ub或或UVb)则则bFIRSTVT(U)+2)若有规则若有规则U V且且bFIRSTVT(V),则则bFIRSTVT(U)说明说明:因为因为Vb或或VWb,所以有所以有UVb或或 UV Wb+第五章语法分析-自下而上分析设一个栈设一个栈S和一个二维布尔数组和一个二维布尔数组F FU,b=TRUE iff bFIRSTVT(U)PROCEDURE INSERT(U,b)IF NOT FU,b THEN BEGIN FU,b:=TRUE 把把(U,b)推进推进S栈栈 /*bFIRSTVT(U)*/END BEGIN main FOR 每个非终结符号每个非终结符号U
23、和终结符和终结符b DO FU,b:=FALSE /*赋初值赋初值*/FOR 每个形如每个形如Ub或或UVb 的规则的规则 DO INSERT(U,b)具体方法如下具体方法如下具体方法如下具体方法如下:第五章语法分析-自下而上分析WHILE S栈非空栈非空 DO BEIGN 把把S栈的顶项弹出栈的顶项弹出,记为记为(V,b)/*bFIRSTVT(V)*/FOR 每条形如每条形如UV的规则的规则 DO INSTER(U,b);/*bFIRSTVT(U)*/END OF WHILE END上述算法的工作结果是得到一个二维的布尔数组上述算法的工作结果是得到一个二维的布尔数组上述算法的工作结果是得到一
24、个二维的布尔数组上述算法的工作结果是得到一个二维的布尔数组F,F,从从从从F F 可以得到任何非终结符号可以得到任何非终结符号可以得到任何非终结符号可以得到任何非终结符号U U的的的的FIRSTVT FIRSTVT FIRSTVT(U)=b|FU,b=TRUE FIRSTVT(U)=b|FU,b=TRUE 第五章语法分析-自下而上分析构造构造LASTVT(U)的算法的算法1.若有规则若有规则Ua或或U=aV,则则aLASTVT(U)2.若有规则若有规则UV,且且aLASTVT(V)则则aLASTVT(U)设一个栈设一个栈ST,和一个布尔数组和一个布尔数组B PROCEDURE INSERT(U
25、,a)IF NOT BU,a THEN BEGIN BU,aTRUE;把把(U,a)推进推进ST栈栈;END;第五章语法分析-自下而上分析BEGIN FOR 每个非终结符号每个非终结符号U和终结符号和终结符号a DO BU,a:=FALSE;FOR 每个形如每个形如Ua或或UaV的规则的规则 DO INSERT(U,a);WHILE ST栈非空栈非空 DO BEGIN 把把ST栈的栈顶弹出栈的栈顶弹出,记为记为(V,a);FOR 每条形如每条形如UV的规则的规则 DO INSERT(U,a);END OF WHILE;END;第五章语法分析-自下而上分析解解:(1)求求firstVT和和las
26、tVT集集firstVT(E)=#firstVT(E)=+,*,(,i)firstVT(T)=*,(,i)firstVT(F)=,(,i)firstVT(P)=(,i)lastVT(E)=#lastVT(E)=+,*,),i lastVT(T)=*,),i 文法文法E#E#TFEE+T FPF|PET P（E）TT*F Pi第五章语法分析-自下而上分析解解:(1)求求firstVT和和lastVT集集firstVT(E)=#firstVT(E)=+,*,(,i)firstVT(T)=*,(,i)firstVT(F)=,(,i)firstVT(P)=(,i)lastVT(E)=#lastVT(E
27、)=+,*,),i lastVT(T)=*,),i firstVT(B)=b|Bb或BCbE=#E#E#EE+TETT*FETFPFETP(E)ilastVT(B)=a|Ba或BaC第五章语法分析-自下而上分析lastVT(F)=),i lastVT(P)=i,)(2)求求=.关系关系E#E#=.#P(E)(=.)(3)求求.关系关系E#E#则则#.firstVT(E)所以所以#.+,#.*,#.,#.(，#.i 第五章语法分析-自下而上分析E E+T 则则+.firstVT(T)所以所以 +.*,+.,+.(,+.iTT*F 则则*.firstVT(F)所以所以 *.,*.(,*.iFPF
28、则则.firstVT(F)所以所以 .,.(,.iP（E)则（则（.firstVT(E)所以所以 (.+,(.*,(.,(.(,(.关系关系E#E#则则 lastVT(E).#所以所以+.#,*.#，.#,).#,i.#EE+T 则则lastVT(E).+所以所以 +.+,*.+,.+,).+,i.+TT*F 则则lastVT(T).*所以所以 *.*,.*,i.*,).*FPF 则则lastVT(P).所以所以 i.,).P(E)则则lastVT(E).)所以所以 +.),*.),.),i.),).)第五章语法分析-自下而上分析算符优先关系表+*i()#+.*.i.(.#.=.第五章语法分析
29、-自下而上分析50505050算符优先分析法的实现：算符优先分析法的实现：#分析程序分析程序分析程序分析程序 优先关系矩阵优先关系矩阵优先关系矩阵优先关系矩阵#符号符号符号符号栈栈输输入串入串入串入串当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移当栈内终结符的优先级栈外的终结符的优先级时，移进；栈内终结符的优先级栈外的终结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归进；栈内终结符的优先级栈外的终结符的优先级时，归约约约约。表明找到了素短
30、语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。表明找到了素短语的尾，再往前找其头，并进行规约。第五章语法分析-自下而上分析实例比较算符优先归约（P90表5.1）规范归约（）前者（1）去掉单非终结符的归约，（2）并且在归约时不考虑非终结符的名字，因此得到的不是真正的语法树，而是语法树的框架。（P90图5.1）算符优先分析法的可归约串不是句柄而是最左素短语。第五章语法分析-自下而上分析五、最左素短语定义：设有文法GS，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素
31、短语。与句柄的区别：至少包含一个终结符。（从而去掉了单非终结符的归约）例：文法GE:EE+T|TTT*F|FFPF|PP（E）|i句型#T+T*F+i#的语法树如下：第五章语法分析-自下而上分析EET+E+TFTT*FPi根据语法树可知：句型#T+T*F+i#的短语有：T相对非终结符E的短语T*F相对非终结符T的短语T+T*F相对非终结符E的短语i相对非终结符P、F、T的短语T+T*F+i相对非终结符E的短语第五章语法分析-自下而上分析根据素短语的定义可知：i和T*F为素短语。其中：T+T*F(含其他T*F素短语)和T+T*F+i不是素短语。T*F为最左素短语。T为句柄最左直接短语第五章语法分
32、析-自下而上分析定理定理：一个：一个OPG句型的最左素短语是满足下列条件的句型的最左素短语是满足下列条件的 最左子串：最左子串：aj-1NjajNiaiNi+1ai+1其中其中 aj-1.ai+1算符文法的任一句型形式为#N1a1N2a2NnanNn+1#(NiVN或Ni=,aiVT)算符优先分析法的关键：如何确定当前句型的最左素短语？第五章语法分析-自下而上分析56565656 根据该定理根据该定理根据该定理根据该定理,要找句型的最左素短语就是要找满足要找句型的最左素短语就是要找满足要找句型的最左素短语就是要找满足要找句型的最左素短语就是要找满足 上述条件的最左子串上述条件的最左子串上述条件
33、的最左子串上述条件的最左子串.注意注意注意注意:出现在出现在出现在出现在a aj j左端和左端和左端和左端和a a i i右端的非终结符号一定右端的非终结符号一定右端的非终结符号一定右端的非终结符号一定属于这个素短语属于这个素短语属于这个素短语属于这个素短语,因为我们的运算是中缀形式给出因为我们的运算是中缀形式给出因为我们的运算是中缀形式给出因为我们的运算是中缀形式给出的的的的(OPG(OPG文法的特点文法的特点文法的特点文法的特点)NaNaNaNNaNaNaN NaWaNNaWaN例例:文法文法GE E:=E+T|T T:=T*F|F F:=(E)|i分析文法的句型分析文法的句型T+T*F+
34、i第五章语法分析-自下而上分析57575757可以看出可以看出可以看出可以看出:1.1.每次规约最左子串每次规约最左子串每次规约最左子串每次规约最左子串,确实是当前句型的最左素短语确实是当前句型的最左素短语确实是当前句型的最左素短语确实是当前句型的最左素短语(语法树）语法树）语法树）语法树）2.2.规约的不都是真句柄（仅规约的不都是真句柄（仅规约的不都是真句柄（仅规约的不都是真句柄（仅i i规约为规约为规约为规约为F F是句柄，但它是句柄，但它是句柄，但它是句柄，但它是最左短语是最左短语是最左短语是最左短语)3.3.没有完全按规则进行规约没有完全按规则进行规约没有完全按规则进行规约没有完全按规
35、则进行规约,因为素短语不一定是因为素短语不一定是因为素短语不一定是因为素短语不一定是简单短语简单短语简单短语简单短语步骤步骤步骤步骤句型句型句型句型关系关系关系关系最左子串最左子串最左子串最左子串 规约符号规约符号规约符号规约符号1 12 23 34 4#T+T*F+i#T+T*F+i#T+T+i#T+T+i#E+i#E+i#E+F#E+F#+#+#+#+#+#+#T*FT*FT+TT+Ti iE+FE+FT TE EE EF F.第五章语法分析-自下而上分析算符优先分析法的实现：算符优先分析法的实现：详见详见P93 算法算法基本部分是找句型的最左子串（最左素短语）基本部分是找句型的最左子串（
36、最左素短语）并进行规约。并进行规约。第五章语法分析-自下而上分析六、优先函数：算符优先关系表示法矩阵表示法(空间大)优先函数法1、优先函数的定义：当a=.b，令f(a)=g(b)当a.b，令f(a).b，令f(a)g(b)f(a)、g(b)为优先函数，函数值用整数表示第五章语法分析-自下而上分析2、优先函数的构造构造规则a)对终结符aVT(包括#号)令f(a)=g(a)=1(初始化)b)如果a.b，而f(a)g(b)，则令f(a)=g(b)+1c)如果a2n(n为终结符个数)，则该文法不存在算符优先函数。第五章语法分析-自下而上分析例1：有优先表如下，构造优先函数。+*+.b关系有：.f(+)
37、=g(+)+1+*f222g111+*f221g111*.*.*.*第五章语法分析-自下而上分析+*f222g133+*+.(3)对a.b关系有.*g(*)=f(+)+1+.g()=f(+)+1+*f222g133*.b关系+.+*.+*.*f(*)=g(*)+1+*f242g133+*f244g133.+.*f()=g(*)+1第五章语法分析-自下而上分析+*+.+*f244g133(3)对a.b关系+.*+.*.*.i.(.#.b关系+*i()#f2111111g1111111+.+.)+.#第五章语法分析-自下而上分析+*i()#f2211111g1111111*.+*.*.)*.#.+
38、.*.).#+*i()#f2221111g1111111第五章语法分析-自下而上分析+*i()#f2222111g1111111i.+i.*i.i.)i.#+*i()#f2222121g1111111).+).*).).).#第五章语法分析-自下而上分析(3)对a.b关系+.*+.+.i+.(+*i()#f2222121g1333311*.*.i*.(+*i()#f2222121g1333311第五章语法分析-自下而上分析.i.(+*i()#f2222121g1333311(.+(.*(.(.i(.(+*i()#f2222121g2333311第五章语法分析-自下而上分析#.+#.*#.#.i
39、#.b关系+*i()#f3444141g2333311对于a.b关系+*i()#f3556141g2455511第五章语法分析-自下而上分析对于a.b关系+*i()#f3557171g2466611对于a.b关系+*i()#f3557171g2466611第五章语法分析-自下而上分析+*i()#f3557171g2466611对于ab关系第五次重复过程+*i()#f3557171g2466611第五章语法分析-自下而上分析第五次结果同第四次，表示收敛了。因此优先函数为：+*i()#f3557171g2466611第五章语法分析-自下而上分析5.2.3 优先函数优先函数 在实际实现算符优先分析算
40、法时，一般不用优先表而在实际实现算符优先分析算法时，一般不用优先表而是用两个优先函数是用两个优先函数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）
41、对于每个终结符）对于每个终结符a(a(包括包括#）令其对应两个符号）令其对应两个符号fafa和和g ga a ,画一张以所有符号画一张以所有符号fafa和和gaga为结点的方向图，如果为结点的方向图，如果a=b,a=b,那么，就从那么，就从fafa画一箭弧至画一箭弧至g gb b;如果如果a=b a=b 则画一条从则画一条从gbgb到到fafa的箭弧。的箭弧。第五章语法分析-自下而上分析 上图中图上图中图a是输入串是输入串abbcde的语法树，一个句型的句柄是该句的语法树，一个句型的句柄是该句型语法树中最左子树的末端结的自左至右排列。则此子树为型语法树中最左子树的末端结的自左至右排列。则此子树
42、为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 我们有我们有(=),从产生式从产
43、生式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)的，的，至多只有一种优先关系。从而得到下面的优先表：至多只有一种优先关系。从而得到下面的优先表：第五章语法分析-自下而上分析(2)对于每个结点都赋予一个数，此数等于从该结点所能对于每个结点都赋予一个数，此数等于从该结点所
44、能到达结点（包括出发结点自身在内）的个数。赋给到达结点（包括出发结点自身在内）的个数。赋给fa的数作为的数作为f(a)，赋给，赋给gb的数作为的数作为g(b).(3)检查构造出来的函数检查构造出来的函数f 和和g，看它们同原来的关系表是看它们同原来的关系表是否有矛盾。如果没矛盾，则否有矛盾。如果没矛盾，则f 和和g就是所要的优先函数。就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。如果有矛盾，那么，就不存在优先函数。例题例题5。5 就是构造优先函数的例子，望同学们好好就是构造优先函数的例子，望同学们好好研究一下。研究一下。5。2。4 算符优先分析中的出错处理算符优先分析中的出错处理根据
45、课本说明不作考核要求根据课本说明不作考核要求第五章语法分析-自下而上分析例题与习题解答例题与习题解答例例5.1 设有文法设有文法G和输入串和输入串$G:SaABe$:abbcde A Abc|b B d 通过语法树能使我们直观的理解规范通过语法树能使我们直观的理解规范“归约归约”、“句柄句柄”等概念。等概念。第五章语法分析-自下而上分析优先关系表优先关系表 +*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 第五章语法分析-自下而上分析