ch6自底向上算符优先语法分析(张素琴).ppt

自底向上算符优先语法 分析 第6章 1 主要内容：规范归约，自上而下的算符优 先分析方法及其相关概念。 重点掌握： 掌握自下而上分析的基本思想，规范规约的 概念及过程； 算符优先文法、算符优先关系的判定，最左 素短语、句柄的定义与判定; 构造算符优先关系表; 能用算符优先分析法进行表达式分析。 6.1自底向上优先分析概述 2 自下而上的语法分析 实现思想：“移进-归约”方法 输入：待分析的句子(终结符号串)。 输出：语法树。从树叶开始，逐步向上归约 构造分析树，直到形成根结点。 核心 寻找句柄进行规约。 设置一个栈，将输入符号逐个移进栈中，栈 顶形成某产生式的右部时(句柄)，就用左部去 代替，称为归约。 重复这一过程，直到栈中只剩下文法的开始 符号，就确认输入串是文法的句子，分析成 功，否则出错。 3 最左推导(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的句子。 4 步骤 动作 (1)S aAcBe (2)A b (3)A Ab (4)B d 最左归约过程是最右推导的逆过程， 对输入串abbcde 的归约过程如下： 该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。 a b A c S 1 移 进 a A a 移 进 b 4 a 归 约 3 5 c A a 移 进 d 7 c A a 归 约 4 8 B c A a 移 进 e 9 10 归 约 1 移 进 b 2 a 归 约 2 3 a b 移 进 c 6 A a dB e A 5 语法分析树的生成演示 a b b c d e A A B S Ab AAb Bd SaAcBe (1)S aAcBe (2)A b (3)A Ab (4)B d 6 规范归约分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串（某个产生式的右端）就立 即归约。 归约就是将栈顶的一串符号用文法产生式的左 部代替，归约可能重复多次。 若最终能归约成文法的开始符号，则分析成功 。 由于总是将句型的最左边的可归约串替换成非 终结符，该方法与最右推导对应。 关键是如何判断可归约串？ 7 问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 不同的自下而上的分析方法对可归约串的定义 是不同的，但分析过程的一个共同特点是：边移 进边归约。 规范归约：使用句柄来定义,如简单优先分析 算符优先分析：使用最左素短语来定义 LR分析方法：使用活前缀来定义 8 规范归约的概念 有文法G，开始符号为S, 如果有S=xy,则xy 是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对 于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对 于A-的直接短语 位于一个句型最左边的直接短语称为句柄. * *+ * 注意: 规范规约中每次归约的部分必须是句柄 (最右 推导)。 关键的问题是如何识别句柄 9 例： 求句型 i1*i2+i3 的短语、 直接短语和句柄。 ET | E+T TF | T*F Fi | (E) 因此： 短语有：i1, i2, i3, i1*i2, i1*i2+i3 直接短语有：i1, i2 , i3 句柄是： i1 E = F * i2 + i3 E = i1 * F + i3 E = i1 * i2 + F E = T + i3 （T =T*F =i1 * i2） E = i1 * i2 + i3 Fi i2 + i3 不是短语，因为E = i1 * E （E =i2 +i3） * + + + + + 10 从语法分析树来识别： 一棵子树是由树的某个结点连同 它的所有子孙组成的。 子树的所有端末结点自左至右排 列成一个相对子树根的短语。 直接短语：只有父子两代结点形 成的短语。 句柄：最左子树的直接短语。 E E + T T F i3 i2 i1 T * F F 从语法树可以看出： i1, i2, i3, i1*i2, i1*i2+i3是句型i1*i2+i3的短语 直接短语有：i1, i2 , i3 句柄是： i1 ET | E+T TF | T*F Fi | (E) 句型i1*i2+i3的语法树如图： 11 对下述文法，求句型 E+T * F + i 的短语、直接短语、句柄 ET | E+T TF | T*F Fi | (E) E E + T F i E + T T * F 短语有：i, T * F, E+T * F, E + T * F + i 直接短语有： i, T * F 句柄是：T * F 练 习 12 给定右边的文法，用句柄对 符号串abbcde进行归约 用句柄对句子进行归约的过程与用移进-归约过程是 一致的，使用归约的产生式及其顺序是一致的。 符号串(句型 ) 归约规则 abbcde (1)S aAcBe (2)A b (3)A Ab (4)B d (2)Ab (3)A Ab aAbcde aAcde (4)B d (1)S aAcBe aAcBe S b A AB S ac d e b 13 规范归约分析中栈的使用 1、句型表示 a1 a2 a3 # X1 X2 X3 # “移进-归约” 分析程序 输出 栈(存放句型前缀) 输入串 符号栈内容 + 输入缓冲区内容 # 当前句型 # 一般形式： 符号栈的内容剩余输入串 初态：#输入串# 终态：#S# 2、分析器结构 能够到达终态，分析成功， 不能到达终态，分析失败。 14 例2：有文法： (1)E E+T|T (2)T T*F|F (3)F (E)|i 对输入串 id1+id2*id3 的规范归约过程： 15 动作 栈 输入缓冲区 1) 准备 # i+i*i# 2) 移进 #i +i*i# 3) 归约 Fi #F +i*i# 4) 归约 TF #T +i*i# 5) 归约 ET #E +i*i# 6) 移进 #E+ i*i# 7) 移进 #E+i *i# 8) 归约 Fi #E+F *i# 9) 归约 TF #E+T *i# 10) 移进(可规约) #E+T* i# 11) 移进 #E+T*i # 12) 归约 Fi #E+T*F # 13)归约TT*F(TF) #E+T # 14) 归约 EE+T #E # 15) 接受 所得的结果是：用产生式序列表示语法分析树 i + i * i F T E F T F T E (1) ET | E+T (2) TF | T*F (3) Fi | (E) 16 练习 给出句型(a,(a,a)的 规范归约过程 给定文法GS： S a | (T) T T,S | S 1#(a,(a,a)#开始 2#(a,(a,a)#移进 3#(a,(a,a)#移进 4#(S,(a,a)#归约 5#(T,(a,a)#归约 6#(T,(a,a)#移进 7#(T,(a,a)#移进 8#(T,(a,a)#移进 9#(T,(S,a)#归约 10#(T,(T,a)#归约 11#(T,(T,a)#移进 12#(T,(T,a)#移进 13#(T,(T,S)#归约 14#(T,(T)#归约 15#(T,(T)#移进 16#(T,S)#归约 17#(T)#归约 18#(T)#移进 19#S#接受17 do do 将输入串最左边的符号移入栈内； while（栈顶没有出现可归约串 ）； do 归约可归约串； while（栈顶还有可归约串）； while（文法开始符号没有出现在栈顶或者没有发 现错误） 规约算法描述： 18 分析器的四种动作 1) 移进：将下一输入符号移入栈 2) 归约：当栈顶出现句柄，用产生式左侧的 非终结符替换栈顶的句柄 3) 接受：分析成功，是归约的一种特殊情况 4) 出错：栈顶的内容与输入符号相悖，进行 出错处理 ？决定移进和归约的依据是什么 19 移进归约分析中的问题 1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 p17上例第10)步可以移进*，也可以按产生式 EE+T进行归约。 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 例如上述第13)步，可以用TF进行归约，又可 以按TT*F进行归约。 本章所给两种处理以上冲突的方法 20 优先分析法有两种： 简单优先分析法(规范归约)文 法按一定规则规定文法符号(终结符 和非终结符)的优先关系 算符优先分析法(不规范归约) 规定算符(终结符)之间的优先关系 21 6.2简单优先分析 简单优先分析法的思想是利用终结符和非 终结符之间的优先关系确定唯一句柄，是 规范规约。 22 6.2.1简单优先关系 对于文法G中的任意两个符号X和Y按其在句型 中可能会出现的相邻关系来确定他们之间的优 先关系。X和Y可以是非终结符也可以是终结符 。 (1) X优先性等于Y ，记作X Y。当且仅当G中存在规 则AXY. (2) X优先性低于Y， 记作X Y。当且仅当G中存在规 则AXB , 且B+Y (3) X优先性高于Y ，记作X Y。当且仅当G中存在规 则ABD ，且B+X，D*Y 23 简单优先关系矩阵 SbA(Ba)# S b A ( B a ) # 例6.2 教科书p104.设有文法GS： SbAb A(B|a B Aa) 24 6.2.2简单优先文法定义 一个文法是简单优先文法必须满足如下两个 条件： (1)在文法符号集V中的任意两个符号最多只 有一种优先关系； (2)文法中任意两个产生式没有相同的右侧。 25 6.2.3简单优先分析算法 根据优先关系矩阵和文法构造算法如下： (1)将输入符号串a1a2an#存入符号栈T中，直到遇到 栈顶符号ai的优先级 下一个待输入符号的优先级 为止； (2)栈顶当前符号ai为句柄尾由此向左找句柄的头符号 ak，即找到ak-1 ak为止； (3)由句柄akai在文法的产生式中找右部为akai的产 生式，若找到用左部代替右部，否则不是句子； (4)重复上述步骤直到规约完输入符号串栈中只剩文法 输入符号。 26 分析b(aa)b 文法GS ： SbAb A(B|a B Aa) 栈T输入缓冲 说明 #b(aa)b# 初始状态 #b(aa)b# #b(aa)b# #b(aa)b# aa,(b,(b,(B是句柄 #bAb# #bAb# b#, bAb是句柄 #S# SbA(Ba) # S b= A = ( a= ) #+b.或 R=+Qb. (注意ab相邻或只隔一个非终结符)； a b, G中有P.Rb.的产生式,且R=+.a或 R=+.aQ (注意ab相邻或只隔一个非终结符)。 6.3.2算符优先文法的定义 30 例1：EE+E | E*E | (E) | i 就不是算符优先文法 。 因为：EE+E ，EE*E 则有 + *(由规则2) 又因为：EE*E, EE+E 则有 + *(由规则3) 所以不是算符优先文法，仅是算符文法。 3.算符优先文法 算符文法G的任何终结符a,b之间要么没有优先 关系，若有优先关系,至多有 = , 中的一 种成立,则G为一算符优先文法。 31 课堂练习：对右边的文法G， 计算终结符+，*，和 )之间的 优先关系： EE + T TT * F FP F P(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 35 算符优先关系表的自动构造算法 1.FirstVT集 定义：对每个非终结符P, FirstVT(P)=a|P=a.或P=Qa.,a为终结 符,P，Q为非终结符 + 由优先性 的定义和FirstVT集合的定义可以得出： 若存在某个产生式：Q-aP， 对所有：bFirstVT(P) 都有：a .a或 P =.aQ,a为终结符,P，Q为非终结符 + + 构造LastVT集算法如下。 43 构造LastVT集算法: 按照下面两条规则来构造LastVT集： 若有产生式P.a或P.aQ,则aLastVT(P) 若有产生式P.R,若aLastVT(R),则aLastVT(P) abc P Q 所有终结符 所有非终结符 数组值为真假， 为真的条件是c LastVT(Q) 通过构造一个二维数组F来实现, 数组F的每一行反映 任何一个非终结符P的LastVT集中的元素。步骤： (1)先用条规则进行初始化 44 (2)使用规则对数组F进行修改，修改方法是： (1) 用一个栈，将所有F数组中值为真的元素FP,a的符 号对(P,a)压入堆栈； (2) 对栈施行如下操作：若栈不空，将栈顶符号对出栈 ，记为(Q,a)，检查所有的产生式，若有形为：PQ 的产生式，且FP,a为假， 则置FP,a为真，将(P,a)压 入堆栈； (3) 重复这一过程，直到栈空 45 练习 LastVT(S) = a,) LastVT(T) = a,), , 计算LastVT 给定文法GS： S a | (T) T T,S | S a(), S11 T111 46 3.构造优先关系表的算法 如果每个非终结符的FirstVT和LastVT集 均已知,则可根据定义构造优先关系表。 构造思路： (1) 若产生式是形如：Pab 或 PaQb的形式，则有a b (2)若产生式右部是.aR.的形式,则对 于每个bFirstVT(R)都有a b (3)若产生式右部有.Rb的形式,则对于每 个aLastVT(R)集,都有a b 47 for 每个形如PX1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i Xi+1 ; end; 优先关系表构造算法伪代码 同一产生式中 的相邻符号1 同一产生式中 的相邻符号2 a出现在其它产 生式中，通过 计算得到 48 练习 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)再从aj开始往左扫描堆栈,直至找到某个i,满 足ai-1 ai为止 (3)Niai Ni+1ai+1 Njaj Nj+1形式的子串即为最左 素短语，