《ch6自底向上算符优先语法分析(张素琴)》由会员分享，可在线阅读，更多相关《ch6自底向上算符优先语法分析(张素琴)（72页珍藏版）》请在金锄头文库上搜索。
1、自底向上算符优先语法分析,第6章,1,主要内容：规范归约，自上而下的算符优先分析方法及其相关概念。 重点掌握： 掌握自下而上分析的基本思想，规范规约的概念及过程； 算符优先文法、算符优先关系的判定，最左素短语、句柄的定义与判定; 构造算符优先关系表; 能用算符优先分析法进行表达式分析。,6.1自底向上优先分析概述,2,自下而上的语法分析,实现思想：“移进-归约”方法 输入：待分析的句子(终结符号串)。 输出：语法树。从树叶开始，逐步向上归约构造分析树，直到形成根结点。 核心 寻找句柄进行规约。 设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时(句柄)，就用左部去代替，称为归约。 重
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
3、 Ab (4)B d,最左归约过程是最右推导的逆过程， 对输入串abbcde的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b,A,c,S,b,d,B,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,规范归约分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串（某个产生式的右端）就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次。 若最终能归约成文法的开始符号
4、，则分析成功。 由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。 关键是如何判断可归约串？,7,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 不同的自下而上的分析方法对可归约串的定义是不同的，但分析过程的一个共同特点是：边移进边归约。,8,规范归约的概念,有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语 位于一个句
5、型最左边的直接短语称为句柄.,注意: 规范规约中每次归约的部分必须是句柄 (最右推导)。 关键的问题是如何识别句柄,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,+,+,+,+,+,+,10,从语法分析树来识别：
6、 一棵子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语。 直接短语：只有父子两代结点形成的短语。 句柄：最左子树的直接短语。,从语法树可以看出： 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),短语有：i, T * F, E+T * F, E +
7、 T * F + i 直接短语有： i, T * F 句柄是：T * F,练 习,12,给定右边的文法，用句柄对符号串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,13,规范归约分析中栈的使用,1、句型表示,符号栈内容 + 输入缓冲区内容 # 当前句型 #,2、分析器结构,能够到达终态，分析成功，不能到达终态，分析失败。,14,例2：有文法： E E+T|T
8、T T*F|F 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 #
9、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,17,do do 将输入串最左边的符号移入栈内； while（栈顶没有出现可归约串 ）； do 归约可归约串； while（栈顶还有可归约串）； while（文法开始符号没有出现在栈顶或者没有发现错误）,规约算法描述：,18,分析器的四种动作,1) 移进：将下一输入符号移入栈 2) 归约：当栈顶出现句柄
10、，用产生式左侧的非终结符替换栈顶的句柄 3) 接受：分析成功，是归约的一种特殊情况 4) 出错：栈顶的内容与输入符号相悖，进行出错处理 ？决定移进和归约的依据是什么,19,移进归约分析中的问题,1) 移进-归约冲突 在分析到某一步时，既可以移进，又可以归约 p17上例第10)步可以移进*，也可以按产生式EE+T进行归约。 2) 归约-归约冲突 存在两个可选的句柄，可对栈顶符号进行归约 例如上述第13)步，可以用TF进行归约，又可以按TT*F进行归约。 本章所给两种处理以上冲突的方法,20,优先分析法有两种： 简单优先分析法(规范归约)文法按一定规则规定文法符号(终结符和非终结符)的优先关系 算
11、符优先分析法(不规范归约)规定算符(终结符)之间的优先关系,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,简单优先关系矩阵,例6.2 教科
12、书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的产生式，若找到用左部代替右部，否
13、则不是句子； (4)重复上述步骤直到规约完输入符号串栈中只剩文法输入符号。,26,分析b(aa)b,文法GS： SbAb A(B|a B Aa),27,6.3算符优先分析,算符优先分析法的思想源于表达式的分析，是利用相邻终结符号之间的关系来寻找可归约串。 将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定规约子串，分析过程是自下而上的归约过程，不是一种严格的规范归约。,28,6.3.1算符优先关系的定义,在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在三种优先关系： (1) a优先性等于b ，记作a b。 (2) a优先性高于b， 记作a b。 (3) a优先性低于b ，记
14、作a b。,另一种情况是，a与b不可能相邻，即此符号串不是句型 (出错)。 如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。,29,1.算符文法：文法G中没有P.QR.(P,Q,R属于非终结符)的产生式,(不存在具有相邻非终结符的产生式) 2.算符优先关系的定义：文法G是一个不含-产生式的算符文法，定义终结符a、b之间的优先关系 a b, G中有P.ab.或P.aQb. 产生式； a b, G中有P.aR.的产生式,且R=+b.或 R=+Qb. (注意ab相邻或只隔一个非终结符)； a b, G中有P.Rb.的产生式,且R=+.a或R=+.aQ (注意
15、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，所以
