资源描述
自下而上语法分析方法自下而上语法分析方法第四章（第四章（2） 本节要求本节要求 主要内容主要内容：自下而上语法分析的概念，规自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。范归约，算符优先分析方法及其相关概念。 重点掌握：重点掌握：掌握自下而上分析的基本思想，掌握自下而上分析的基本思想，规范规约的概念及过程；算符优先文法、规范规约的概念及过程；算符优先文法、算符优先关系的判定，最左素短语、句柄算符优先关系的判定，最左素短语、句柄的定义与判定，构造算符优先关系表，能的定义与判定，构造算符优先关系表，能用算符优先分析法进行表达式分析用算符优先分析法进行表达式分析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是否是下述文法的句子？结论结论：自上而下语法分析自上而下语法分析采用最左推导，每一步推导使用哪个产生式要视当前非终结符匹配输入字符串中的哪个符号来确定。自下而上语法分析自下而上语法分析是最右推导的逆过程，由输入符号串反向推导推导到文法的开始符号。自下而上的语法分析自下而上的语法分析 实现思想：实现思想：“移进移进- -归约归约”方法方法设置一个栈，将输入符号逐个移进移进栈中，栈顶形成某某产生式的右部时，就用左部去代替，称为归约归约。重复这一过程，直到栈中只剩下文法的开始符号，就确认输入串是文法的句子，分析成功，否则出错。语法树：从树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。 核心核心 寻找寻找句柄句柄（这是关键）（这是关键）进行规约。用不同的方法寻找句柄，就可获得不同的分析方法。 最左推导最左推导(Left-most Derive) 每一步推导都替换当前句型的最左边的非终结符。 其逆过程称为最右归约最右归约 最右推导最右推导(Right-most Derive) 每一步推导都替换当前句型的最右边的非终结符。 其逆过程称为最左归约最左归约(规范归约规范归约)，得规范句型规范句型例：例：设有文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 使用最右推导：因为S aAcBe aAcde aAbcde abbcde，所以 abbcde是文法G的句子。)1(rm)2(rm)3(rm)4(rm步骤步骤动作动作(1)S aAcBe(2)A b (3)A Ab(4)B d最左归约过程是最右推导的逆过程， 对输入串abbcde的归约过程如下：该分析过程反复执行该分析过程反复执行“移进移进”和和“归约归约”两个动作，直到栈中只有开始符号为止。两个动作，直到栈中只有开始符号为止。ab AcS1移进aAa移进b4 a归约35c A a移进d7c A a归约48Bc A a移进e910归约1移进b2a归约23ab移进c6AadBeA语法分析树的生成演示语法分析树的生成演示a b b c d ea b b c d eAABSAbAbAAbAAbBdBdSaAcBeSaAcBe(1)S aAcBe(2)A b (3)A Ab(4)B d 这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进移进栈中) 。 一旦发现可归约串可归约串（某个产生式的右端）就立即归约归约。 归约归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次重复多次。 若最终能归约成文法的开始符号，则分析成功。 由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。 关键是如何判断可归约串可归约串？问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 不同的自下而上的分析方法对可归约串的定义是不同的，但分析过程的一个共同特点是：边移边移进边归约进边归约。规范归约：使用句柄句柄来定义算符优先分析：使用最左素短语最左素短语来定义LR分析方法：使用活前缀活前缀来定义规范归约的概念 有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语直接短语 位于一个一个句型最左边的直接短语称为句柄句柄.*+*注意: 每次归约的部分必须是句柄句柄 (最右推导)。 关键的问题是如何识别句柄如何识别句柄例：考虑如下文法：求句型 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）*从语法分析树来识别： 一棵子树子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语短语。 直接短语直接短语：只有父子两代结点形成的短语。 句柄句柄：最左子树的直接短语。EE + TTFi3i2i1T * FF从语法树可以看出：i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的短语直接短语有：i1, i2 , i3 句柄是： i1ET | E+TTF | T*FFi | (E)句型i1*i2+i3的语法树如图：对下述文法，求句型 E+T * F + i的短语、直接短语、句柄ET | E+TTF | T*FFi | (E)EE + TFiE + TT * F短语有：i, T * F, E+T * F, E + T * F + i直接短语有： i, T * F句柄是：T * F练 习给定右边的文法，用句柄对符号串abbcde进行归约 用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。符号串归约规则abbcde(1)S aAcBe(2)A b (3)A Ab(4)B d(2)Ab(3)A AbaAbcdeaAcde(4)B d(1)S aAcBeaAcBeSbAABSacdeb规范归约的定义： 假定是文法G的一个句子，如果序列： n, n-1, , 0 (=S)满足如下条件，则序列n, n-1, , 0是一个规范归约规范归约:(1) n = 是给定的句子(2) 0 =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)所以不是算符优先文法。 3.算符优先文法算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 = , 中的一种成立,则G为一算符优先文法符优先文法。练 习 对右边的文法G，计算终结符+，*，和 )之间的优先关系：EE + T 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 TT*F|F F (E)|i 求算符优先关系表终结符+#终结符+#对于结束符#和其它终结符a之间若有关系,则必有: # # ，计算方法是拓展成E#E#*注意： a,b之间未必有优先关系,在优先表中，空白部分是一种错误关系 相同的终结符之间的优先关系不一定是 如果有a = b,不一定有b = a(不具对称性) 如果有a b,不一定有b a(不具对称性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。 如果有a b, b c不一定有a c算符优先关系表的自动构造算法算符优先关系表的自动构造算法 1.FirstVT1.FirstVT集集定义定义：对每个非终结符P, FirstVT(PFirstVT(P) )=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符+由优先性低于的定义和FirstVT集合的定义可以得出：若存在某个产生式：Q-aP，对所有：bFirstVT(P) 都有：a .a或 P =.aQ,a为终结符,P，Q为非终结符+构造LastVT集算法算法 ： 自己练习练习练习 LastVT(S) = a,) LastVT(T) = a,), , 计算LastVT给定文法GS：S a | (T)T T,S | S 3.3.构造优先关系表的算法构造优先关系表的算法如果每个非终结符的FirstVT和LastVT集均已知,则可根据定义构造优先关系表。构造思路： (1) 若产生式是形如：Pab 或 PaQb的形式，则有a b (2)若产生式右部是.aR.的形式,则对于每个bFirstVT(R)都有a b (3)若产生式右部有.Rb的形式,则对于每个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同一产生式中同一产生式中的相邻符号的相邻符号2a出现在其它产出现在其它产生式中，通过生式中，通过计算得到计算得到练习练习 FirstVT(S) = a,( FirstVT(T) = a,(, , LastVT(S) = a,) LastVT(T) = a,), , 的FirstVT和LastVT集,构造优先关系表。给定文法GS：S a | (T)T T,S | S a,()#a,(# aj+1时为止.(2)(2)再从aj开始往左扫描堆栈,直至找到某个i,满足ai-1 ai为止(3)(3)Niai Ni+1ai+1 Njaj Nj+1形式的子串即为最左最左素短语素短语，应被归约。算符优先分析过程算符优先分析过程 开始开始： 分析栈中为：# #，输入缓冲区为：输入串输入串# 结束结束：输入缓冲区为# #，分析栈中为#S#S，分析成功否则失败表达式表达式 i+ii+i* *i i的算符优先过程EE+T|T TT*F|FF(E)|i例:给定文法GE：栈栈输入缓冲输入缓冲 说明说明# #i+ii+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 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=#;算法：P95栈顶符号sj与即将输入的符号a进行比较栈顶符号优先性低于或等于输入符号a，则移进a向前查找最左素短语的头， j记录可归约串的头进行归约S表示堆栈，top记录栈顶位置，j记录栈顶符号位置Sj优先性高于a,寻找可归约串,进行归约 算符优先分析不是严格的规范归约 不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。 算符优先分析比规范归约过程要快，跳过了所有的单非终结产生式。 可能将本来不是句子的输入串误认为是句子。 总结归约的策略: 在文法中寻找这样的产生式:它的右部形如: Niai Ni+1ai+1 Njaj Nj+1,其中每个终结符号与最左素短语对应位置上的终结符号完全相同终结符号完全相同,而每一个非终结符号非终结符号uk应与相应位置上的非终结符号Nk相对应,不必完全相同不必完全相同。算符优先分析法小结算符优先分析法小结 优点优点 简单、效率高简单、效率高 能够处理部分二义性文法能够处理部分二义性文法 缺点缺点 文法书写限制大文法书写限制大 占用内存空间大占用内存空间大 不规范、存在查不到的语法错误不规范、存在查不到的语法错误优先函数优先函数 一般不直接用优先关系表，构造优先函数 将每个终结符与两个自然数f()和g()对应，f()和g()的选择满足如下关系：1 2 , f(1) 2 , f(1)g(2)函数f为入栈优先函数，g为比较优先函数。给定一个文法，如果存在优先函数，则一定存在多个，即f和g的选择不是唯一的。从优先关系表构造优先函数的方法： (1) 对应于每个终结符a(包含#)，令其对应两个符号fa和ga，然后画一张以所有这些符号为结点的方向图，如果a = b，就从fa画箭弧到gb ，如果a *(练习 对下边的文法，有优先关系表如右：为其构造优先函数：S a | (T)T T,S | S a,()#a,(#=a,()#f64262g73722fagaf,g,f(g(f)g)f#g#算符优先分析中的错误处理算符优先分析中的错误处理 使用算符优先分析法时，可在两种情况下发现语法错误： 1. 若栈顶终结符号与下一个输入符号之间不存在任何优先关系 2. 若找到某一可归约串，但不存在任一产生式，其右部与其匹配。 设文法为： E #E# TF EE+T FPF | P ET 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)=+,*, ) , 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) 所以 # +, # *, # , # ( ， # 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(#=
展开阅读全文