第四章自下而上语法分析

资源描述

《第四章自下而上语法分析》由会员分享，可在线阅读，更多相关《第四章自下而上语法分析（74页珍藏版）》请在金锄头文库上搜索。

1、自下而上语法分析方法自下而上语法分析方法第四章（第四章（2）本章要求本章要求v主要内容主要内容：自下而上语法分析的概念，规自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。范归约，算符优先分析方法及其相关概念。v重点掌握重点掌握：掌握自下而上分析的基本思想，掌握自下而上分析的基本思想，基本概念，算符优先文法、算符优先关系基本概念，算符优先文法、算符优先关系的判定，最左素短语、句柄、活前缀的定的判定，最左素短语、句柄、活前缀的定义与判定，求义与判定，求First VT集集,Last VT集集,构造构造算符优先关系表算符优先关系表,能用算符优先分析法进能用算符优先分析法进行表达式分

2、析行表达式分析若若若若Z Z S S 则则则则 S S L(GZ) L(GZ) 否则否则否则否则 S S L(GZ) L(GZ) + +GZGZ存在主要问题存在主要问题: 左递归问题左递归问题回溯问题回溯问题主要方法主要方法: 递归子程序法递归子程序法 LL分析法分析法自顶向下分析算法的基本思想为：自顶向下分析算法的基本思想为：若若若若Z Z S S 则则则则 S S L(GZ) L(GZ) 否则否则否则否则 S S L(GZ) L(GZ) + +GZGZ自底向上分析算法的基本思想为：自底向上分析算法的基本思想为：存在主要问题存在主要问题: 句柄的识别问题句柄的识别问题主要方法主要方法:

3、算符优先分析法算符优先分析法 LR分析法分析法G = (E, i, +, *, (, ) , P , E) P： E E + E E E * E E ( E ) E i 使用最左推导：E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i例：判定输入串(i+i)*i是否是下述文法的句子？结论结论：自上而下语法分析自上而下语法分析采用最左推导，每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。自下而上语法分析自下而上语法分析是最左推导的逆过程，由输入符号串反向推导到文法的开始符号。自下而上的语法分析自下而上的语法分析v实现思

4、想：实现思想：“移进移进- -归约归约”方法方法设置一个栈，将输入符号逐个移移进进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归归约约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。v核心核心寻找句柄(这是关键) 进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。v最左推导(Left-most Derive)每次推导都替换当前句型的最左边的非终结符。与最右归约对应v最右推导最右推导(Right-most Derive)每次推导都替换当前句型的最右边的非终结符。与最

5、左归约(规范归约)对应，得规范句型例：例：设有文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 使用最右推导：因为S aAcBe aAcde aAbcde abbcde，所以 abbcde是文法G的句子。步骤步骤动作动作(1)S aAcBe(2)A b (3)A Ab(4)B d最左归约过程是最右推导的逆过程，对输入串abbcde的归约过程如下：该分析过程反复执行该分析过程反复执行“移进移进”和和“归约归约”两个动作，两个动作，直到栈中只有开始符号为止直到栈中只有开始符号为止。ab AcS1移进aAa移进b4 a归约35c A a移进d7c A a归约48

6、Bc A a移进e910归约1移进b2a归约23ab移进c6AadBeAv这种分析过程具有如下特点：从输入串的开始依次读入单词(移进移进栈中) 。一旦发现可归约串可归约串(某个产生式的右端)就立即归约归约。归约归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功。由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。v关键是如何判断可归约串？语法分析树的生成演示语法分析树的生成演示a b b c d ea b b c d eAABSAbAbAAbAAbBdBdSaAcBeSaAcBe(1)S aAcBe

7、(2)A b (3)A Ab(4)B d 这一方法简单明了这一方法简单明了,不断地进行移进归约不断地进行移进归约,关键是确定当前句型的关键是确定当前句型的句柄句柄. .说明说明:例子的分析过程是一步步地归约例子的分析过程是一步步地归约当前句型当前句型的句柄的句柄该句子该句子输入串为输入串为bbcde的的语法树的构造过程为语法树的构造过程为:Aba)AbAbb)AbAbcdBc)cdBeAbAbSd)例：例：GS: SAcBe Ab AAb Bd问题的提出：在构造语法树的过程中，何时归约？当可归约串出现在栈顶时就进行归约。如何知道在栈顶符号串中已经形成可归约串？如何进行归约？通过不同的

8、自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约边移进边归约。规范归约：使用句柄句柄来定义可归约串。算符优先：使用最左素短语最左素短语来定义可归约串规范归约的概念v有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型句型，x,y是任意的符号串v如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语短语v如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语直接短语v位于一个一个句型最左边的直接短语称为句柄句柄.*+*注意: 每次归约的部分必须是句柄句柄 (最右推导)。关键的问题是如何识别句柄如何识别句柄例：考

9、虑如下文法：求句型 i1 * i2 + i3 的短语、直接短语和句柄。ET | E+TTF | T*FFi | (E)因此：因此：短语有：i1, i2, i3, i1*i2, i1*i2+i3 直接短语有：i1, i2 , i3 句柄是： i1E = F * i2 + i3 E = i1 * F + i3 E = i1 * i2 + F E = T + i3 （T =T*F =i1 * i2）E = i1 * i2 + i3 Fii2 + i3 不是短语，因为E = i1 * E （E =i2 +i3）*从语法分析树来识别：v一棵子树子树是由树的某个结点连同它的所有子孙组成的。v子树的所有端

11、T * F + i直接短语有： i, T * F句柄是：T * F练习给定右边的文法，用句柄对符号串abbcde进行归约v用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。符号串归约规则abbcde(1)S aAcBe(2)A b (3)A Ab(4)B d(2)Ab(3)A AbaAbcdeaAcde(4)B d(1)S aAcBeaAcBeSbAABSacdeb规范归约的定义：v假定是文法G的一个句子，如果序列： n, n-1, ,0 (=S)满足如下条件，则序列n, n-1, , 0是一个规范归约规范归约:(1) n = 是给定的句子(2) 0 =

12、S 是文法的开始符号(3) 对任何i, 0b.或R=Qb. (注意ab相邻)a b,G中有P.Rb.的产生式,且R=.a或R=.aQ (注意ab相邻)算符优先文法的定义+例：EE+E | E*E | (E) | i 证明不是算符优先文法。因为：EE+E ，EE*E 则有 + *(由规则2)又因为：EE*E, EE+E 则有 + *(由规则3)所以不是算符优先文法。v3.算符优先文法算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 = , 中的一种成立,则G为一算符优先文法符优先文法。练习v对右边的文法G，计算终结符+，*，和 )之间的优先关系：EE + T

13、 TT * F FP FP(E) 因为： EE + T ，T=T*F，所以：+ E + T ，所以：+ + (规则规则3)因为： T T * F ，F = P F，所以：* T * F，所以：* * (规则规则3)因为： P(E) ， E = E + T ，所以：+ ) (规则规则3) 因为：FP F, P = (E)，所以：） (规则规则3) 因为： FP F， F =P F，所以： i, 得 + T*F, 得 + (E), 得 + E+TE = i, 得i +E = E+T,得+ + E = T*F, 得* + E = (E), 得 ) + +*i()#+*i()#例:P:EE+T|T T

14、T*F|F F (E)|i 求算符优先矩阵终结符+#终结符+#对于结束符#和其它终结符a之间若有关系,则必有: # # ，计算方法是拓展成E#E#*注意：v在优先表中，空白部分是一种错误关系v相同的终结符之间的优先关系不一定是v如果有a = b,不一定有b = a(不具传递性) v如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。va,b之间未必有优先关系( ) 算符优先关系表的自动构造算法算符优先关系表的自动构造算法 v1.FirstVT1.FirstVT集集定义定义：对每个非终结符P, FirstVT(PFirstVT(P) )

15、=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符+由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：Q-aP，对所有：bFirstVT(P) 都有：a .a或 P =.aQ,a为终结符,P，Q为非终结符+构造LastVT集算法：自己练习v3.3.构造优先关系表的算法构造优先关系表的算法如果每个非终结符的FirstVT和LastVT集均已知,则可根据定义构造优先关系表。构造思路：v(1) 若产生式是形如：Pab 或 PaQb的形式，则有a bv(2)若产生式右部是.aR.的形式,则对于每个bFirstVT(R)都有a bv(3)若产生式右部有.Rb的形式,则对于

16、每个aLastVT(R)集,都有a bfor 每个每个形如形如PX1X2Xn的的产生式产生式 dofor i =1 to n-1 dobegin if Xi和和Xi+1都是终结符都是终结符 then Xi = Xi+1 if i= n-2, Xi和和Xi+2是终结符是终结符, 但但Xi+1为非终结符为非终结符 then Xi = Xi+2 if Xi为为终结符终结符, Xi+1为非终结符为非终结符 then for FirstVT中的每个元素中的每个元素a do Xi Xi+1 ;end;优先关系表构造算法同一产生式中同一产生式中的相邻符号的相邻符号1同一产生式中同一产生式中的相邻符号的相邻符

17、号2a出现在其它产出现在其它产生式中，通过生式中，通过计算得到计算得到练习练习vFirstVT(S) = a,(vFirstVT(T) = a,(, , vLastVT(S) = a,)vLastVT(T) = a,), , 的FirstVT和LastVT集,构造优先关系表。给定文法GS：S a | (T)T T,S | S a,()#a,(#A，A=+ 则称为句型A的一个短语v素短语至少含有一个终结符，并且不再含有更小的素短语v最左素短语处于句型最左面的素短语5252例：给定右边文法的一个句型： T * F + i 求其短语、素短语、最左素短语？ET | E+TTF | T*FFi | (E

18、)EE + TFiTT * F短语有：i, T * F, T * F + i素短语有： i, T * F最左素短语是：T * Fv练习:给定文法GE: 求句型T+T*F+iT+T*F+i的短语、素短语、最左素短语。根据语法树可知：句型#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(不含终结符)也不是素短语T*F为最左素短语最左素

19、短语。EE+T|TTT*F|FF(E)|iEET+E+TFTT*Fiv设算符文法G的句型的一般形式为 #N1a1 N2a2 Nnan # (NiVVN N,ai VVT T）它的最左素短语最左素短语是满足下列条件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：其中： ai-1 ai , ai ai+1 . aj-1 aj ， aj aj+1说明了最左素短语与周围符号之间的关系定定理理一般形式：一般形式：符号栈的内容符号栈的内容剩余输入串剩余输入串初态：初态：#输入串输入串#终态：终态：#S#符号栈内容符号栈内容 + 输入缓冲区内容输入缓冲区内容 # 当前句型当前句型 # #

20、N1a1 N2a2 NnanNn+1# # (ai为终结符,Ni为可有可无的非终结符)句型句型的一般形式：分析时句型表示：3.算符优先分析分析模型v过程过程：(1)(1)从左向右扫描输入符号并移入堆栈,并查优先矩阵,直至找到满足aj aj+1时为止.(2)(2)再从aj开始往左扫描堆栈,直至找到某个i,满足ai-1 ai为止(3)(3)Niai Ni+1ai+1 Njaj Nj+1形式的子串即为最左素短语，应被归约。算符优先分析过程算符优先分析过程开始开始：分析栈中为：# #，输入缓冲区为：输入串输入串# 结束结束：输入缓冲区为# #，分析栈中为#S#S，分析成功否则失败表达式表达式 i

21、+i*ii+i*i的算符优先过程EE+T|T TT*F|FF(E)|i例:给定文法GE：栈栈输入缓冲输入缓冲说明说明# #i+i*i#i+i*i#初始状态#i+i*i#+i*i# #i, i入栈#F+i*i#+i*i# #+, 用Fi归约#F+i*i#i*i# #+, +入栈#F+i*i#*i# +i, i入栈#F+F*i#*i# +*, 用Fi归约#F+F*i#i# +*, *入栈#F+F*i# # *i, i入栈#F+F*F# # *#,用Fi归约#F+T# # +#, 用TF*F归约#E# # #, 用EF+T归约+* i ( ) #+ * i ( # a DO BEGINREPEAT

22、 q:=sj; IF sj-1 Vt THEN j:=j-1 else j:=j-2;UNTIL sj q;把把sj+1.sk归约为归约为某个某个N，将，将N入栈；入栈；top:=j+1; END IF sj a OR sj = a THENBEGIN top:=top+1; stop:=a; END; ELSE error;UNTIL a=#;算法：P93栈顶符号sj与即将输入的符号a进行比较栈顶符号优先性低于或等于输入符号a，则移进a向前查找最左素短语的头， j记录可归约串的头进行归约S表示堆栈，top记录栈顶位置，j记录栈顶符号位置Sj优先性高于a,寻找可归约串,进行归约v算符优先分析一

23、般并不等价于规范归约v并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。v算符优先分析比规范归约过程要快，跳过了所有的单非终结产生式。v可能将本来不是句子的输入串误认为是句子。v总结归约的策略: 在文法中寻找这样的产生式:它的右部形如: Niai Ni+1ai+1 Njaj Nj+1,其中每个终结符号与最左素短语对应位置上的终结符号完全相同终结符号完全相同,而每一个非终非终结符号结符号uk应与相应位置上的非终结符号Nk相对应,不必完全相同不必完全相同。算符优先分析法小结算符优先分析法小结v优点优点简单、效率高简单、效率高能够处

24、理部分二义性文法能够处理部分二义性文法v缺点缺点文法书写限制大文法书写限制大占用内存空间大占用内存空间大不规范、存在查不到的语法错误不规范、存在查不到的语法错误优先函数优先函数v一般不直接用优先关系表，构造优先函数将每个终结符与两个自然数f()和g()对应，f()和g()的选择满足如下关系：1 2 , f(1) 2 , f(1)g(2)函数f为入栈优先函数，g为比较优先函数。给定一个文法，如果存在优先函数，则一定存在多个，即f和g的选择不是唯一的。从优先关系表构造优先函数的方法：v(1) 对应于每个终结符a(包含#)，令其对应两个符号fa和ga，然后画一张以所有这些符号为结点的方向图，如果a

25、 = b，就从fa画箭弧到gb ，如果a *(练习v对下边的文法，有优先关系表如右：为其构造优先函数：S a | (T)T T,S | S a,()#a,(#=a,()#f64262g73722算符优先分析中的错误处理算符优先分析中的错误处理v使用算符优先分析法时，可在两种情况下发现语法错误：1. 若栈顶终结符号与下一个输入符号之间不存在任何优先关系2. 若找到某一可归约串，但不存在任一产生式，其右部与其匹配。设文法为： E #E# TF EE+T FPF | P ET P(E) TT*F Pi求算符优先关系表。练习练习解: (1)求firstVT和lastVT集firstVT(E)=#fi

26、rstVT(E)=+,*, ( , i )firstVT(T)=*, ( , i )firstVT(F)=, ( , i )firstVT(P)= ( , i )lastVT(E)=#lastVT(E)=+,*, ) , i lastVT(T)=*, ) , i lastVT(F)= ) , i lastVT(P)= i , ) firstVT(B)=b|Bb 或 BCbE = #E#E #EE+TETT*FETFPFETP(E)ilastVT(B)=a|Ba 或 BaC(2) 求 = 关系E #E# # = #P(E) ( = )(3) 求关系E #E# 则 # firstVT(E) 所以

27、# +, # *, # , # ( ， # i E E+T 则 + firstVT(T) 所以 + *, + , + ( , + iTT*F 则 * firstVT(F) 所以 * , * ( , * iFPF 则 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(#=

展开阅读全文

第四章自下而上语法分析

最新文档