《编译原理课程教案》第4章：自下而上语法分析.ppt

自下而上语法分析方法,第四章（2）,本章要求,主要内容：自下而上语法分析的概念，规范归约，算符优先分析方法及其相关概念。 重点掌握：掌握自下而上分析的基本思想，基本概念，算符优先文法、算符优先关系的判定，最左素短语、句柄、活前缀的定义与判定，求FirstVT集,LastVT集,构造算符优先关系表,能用算符优先分析法进行表达式分析,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)S aAcBe (2)A b (3)A Ab (4)B d,最左归约过程是最右推导的逆过程， 对输入串abbcde的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b,A,c,S,b,d,B,e,A,这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即归约。 归约就是将栈顶的一串符号用文法产生式的左部代替，归约可能重复多次，然后继续移进。 若最终能归约成文法的开始符号，则分析成功。 由于总是将句型的最左边的可归约串替换成非终结符，该方法与最右推导对应。 关键是如何判断可归约串？,语法分析树的生成演示,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,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,规范归约的概念,有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型，x,y是任意的符号串 如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语 如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语 位于一个句型最左边的直接短语称为句柄.,注意: 每次归约的部分必须是句柄 (最右推导)。 关键的问题是如何识别句柄,例：考虑如下文法：,求句型 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,从语法分析树来识别： 一棵子树是由树的某个结点连同它的所有子孙组成的。 子树的所有端末结点自左至右排列成一个相对子树根的短语。 直接短语：只有父子两代结点形成的短语。 句柄：最左子树的直接短语。,从语法树可以看出： 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的语法树如图：,对下述文法，求句型 E+T * F + i的短语、直接短语、句柄,ET | E+T TF | T*F Fi | (E),短语有：i, T * F, E+T * F, E + T * F + i 直接短语有： i, T * F 句柄是：T * F,练 习,给定右边的文法，用句柄对符号串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,规范归约的定义：,假定是文法G的一个句子，如果序列： n, n-1, ,0 (=S)满足如下条件，则序列n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0in，i-1是从i经把句柄替换为相应文法产生式的左部符号而得到的。 规范归约是最右推导的逆过程，规范归约又称为最左归约。 最右推导又称规范推导，由规范推导所得到的句型称规范句型，规范推导的逆过程是规范归约。,(1)S aAcBe (2)A b (3)A Ab (4)B d,上述例子中句子abbcde的规范归约过程是： abbcde， aAbcde， aAcde， aAcBe，S,练 习,使用下述文法对句型i1*i2+i3进行规范规约:,ET | E+T TF | T*F Fi | (E),i1*i2+i3 , F*i2+i3 , T*i2+i3, T*F+i3 , T + i3 , E+i3 , E + F, E + T , E,使用修剪语法树的方法来进行归约：,规范归约分析中栈的使用,1、句型表示,符号栈内容 + 输入缓冲区内容 # 当前句型 #,2、分析器结构,能够到达终态，分析成功，不能到达终态，分析失败。,例2：有文法： E E+T|T T T*F|F F (E)|i 对输入串 id1+id2*id3 的规范归约过程：,动作 栈 输入缓冲区 1) 准备 # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 Fid #F +id2*id3# 4) 归约 TF #T +id2*id3# 5) 归约 ET #E +id2*id3# 6) 移进 #E+ id2*id3# 7) 移进 #E+id2 *id3# 8) 归约 Fid #E+F *id3# 9) 归约 TF #E+T *id3# 10) 移进 #E+T* id3# 11) 移进 #E+T*id3 # 12) 归约 Fid #E+T*F # 13) 归约 TT*F #E+T # 14) 归约 EE+T #E # 15) 接受,所得的结果是：用产生式序列表示语法分析树,id1 + id2 * id3,F,T,E,F,T,F,T,E,(1) ET | E+T (2)