编译原理自下而上语法分析.ppt

编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 自下而上语法分析 v掌握自底相上分析的基本思想，基本概念 v掌握算符优先关系的判定，求FIRSTVT集,LASTVT集 ,构造算符优先关系表，能运用算符优先分析方法 进行表达式分析 v掌握最左素短语、句柄的定义与判定 v理解规范规约与算符优先归约的区别 vLR(0)和SLR文法的理解 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 自下而上的语法分析 v实现思想 从输入符号串开始，从左到右进行扫描，将输入 符号逐个移入一个栈中，边移入边分析，一旦栈顶符 号串形成某个产生式的右部时，就用该产生式的左部 非终结符代替，称为归约。重复这一过程，直到归约 到栈中只剩下文法的开始符号时，则分析成功， 称为 “移进-归约”方法。 从语法树的角度看：从语法树的树叶开始，逐步 向上归约构造分析树，直到形成根结。是推导的逆过 程。 v核心 寻找可归约串(这是关键)进行规约。用不同的方 法寻找可归约串，就可获得不同的分析方法。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v最左推导(Left-most Derive) 每次推导都替换当前句型的最左边的非终结符 。 与最右归约对应 v最右推导(Right-most Derive) 每次推导都替换当前句型的最右边的非终结符 。 与最左归约(规范归约)对应，得规范句 型 例：设有文法例：设有文法GSGS： (1) S (1) S aAcBeaAcBe (2) A (2) A b b (3) A (3) A AbAb (4) B (4) B d d 使用最右推导：使用最右推导： 因为因为S= S= aAcBeaAcBe= = aAcdeaAcde= = aAbcdeaAbcde= = abbcdeabbcde， 所以所以 abbcdeabbcde是文法是文法GG的句子。的句子。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 步骤 动作 (1)S aAcBe (2)A b (3)A Ab (4)B d 最左归约过程是最右推导的逆过程，最左归约过程是最右推导的逆过程， 对输入串对输入串abbcdeabbcde的的 归约过程如下：归约过程如下： 该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。 a b a A a b A a A a c A a d c A a B c A a e B c A aS 1 移 进 a 2 移 进 b 3 归 约 2 4 移 进 b 5 归 约 3 6 移 进 c 7 移 进 d 8 归 约 4 9 移 进 e 10 归 约 1 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 语法分析树的生成演示 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 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v这种分析过程具有如下特点： 从输入串的开始依次读入单词(移进栈中) 。 一旦发现可归约串(某个产生式的右端)就立即 归约。 归约就是将栈顶的一串符号用文法产生式的左 部代替，归约可能重复多次，然后继续移进。 若最终能归约成文法的开始符号，则分析成功 。 v关键是如何判断可归约串？ 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 问题的提出：问题的提出： 在构造语法树的过程中，何时归约？在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法通过不同的自底向上的分析算法来解释，不同的算法 对可归约串的定义是不同的，但分析过程都有一个共同的对可归约串的定义是不同的，但分析过程都有一个共同的 特点：边移进边归约。特点：边移进边归约。 规范归约：使用句柄来定义可归约串。规范归约：使用句柄来定义可归约串。 算符优先：使用最左素短语来定义可归约串算符优先：使用最左素短语来定义可归约串 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 规范归约概念 v有文法G，开始符号为S, 如果有S=xy,则xy是 文法G的句型，x,y是任意的符号串 v如果有S=xAy, 且有A=,则是句型xy相对于 非终结符A的短语 v如果有S=xAy, 且有A-,则是句型xy相对于A -的直接短语 v位于一个句型最左边的直接短语称为句柄。 * *+ * 注注: : 每次归约的部分必须是称之为每次归约的部分必须是称之为句柄句柄的字符串的字符串( (最右推导最右推导) )。 关键的问题是关键的问题是如何识别句柄如何识别句柄 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例子 下面的例子说明作为短语的两个条件缺一不可。 例考虑表达式文法： E T|E+T T F|T*F F i | (E) 对于句型i*i+i 推导 E E+T E+F E+i T+i T*F+T T*i+i F*i+i i*i+i 尽管有E +i+i 但是, i+i 并不是该句型的一个短语 ，因为不存在从E(文法开始符）到i*E的推导。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 句型的短语和句柄举例 文法：S (T)| TS|T,S|a v 短语： 句型(a),S) S =* (T,S) T =+ (a) 句型(T,S),S) S =* (T),S) T =+ T,S v句型(a,(T),(T,S)直接短语以及句柄： S =* (T,(T),(T,S) T = a S =* (a,S,(T,S) S =(T) S =* (a,(T),(T) T =T,S 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 短语与语法树的关系 v短语：语法树子树的叶子结点组成的符号 串。 v直接短语：语法树简单子树（只有父子两 代）的叶子结点组成的符号串。 v句柄：语法树最左边简单子树的叶子结点 组成的符号串。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 短语与语法树关系的例子 句型(a,(T),(T,S)的语法树： S ()T TS, T,S(T) a(T)T,S 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 用句柄对句子abbcde进行归约 v用句柄对句子进行归约的过程与用移进-归约过程是一 致的，使用归约的产生式及其顺序是一致的。 句型 归约规则 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 aAcBeaAcBe S 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 规范归约的定义 v假定是文法G的一个句子，如果序列： n, n-1, , 0 (=S)满足如下条件，则序列 n, n-1, , 0是一个规范归约: (1) n = 是给定的句子 (2) 0 =S 是文法的开始符号 (3) 对任何i, 0E+T|TE-E+T|T (2)(2)T-T*F|FT-T*F|F (3)(3)F-(E)|iF-(E)|i 对输入串对输入串 i1+i2*i3 i1+i2*i3 的规范归约过程：的规范归约过程： 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 动作 栈 输入缓冲区 1) 准备 # i1+i2*i3# 2) 移进 #i1 +i2*i3# 3) 归约 Fi #F +i2*i3# 4) 归约 TF #T +i2*i3# 5) 归约 ET #E +i2*i3# 6) 移进 #E+ i2*i3# 7) 移进 #E+i2 *i3# 8) 归约 Fi #E+F *i3# 9) 归约 TF #E+T *i3# 10) 移进 #E+T* i3# 11) 移进 #E+T*i3 # 12) 归约 Fi #E+T*F # 13) 归约 TT*F #E+T # 14) 归约 EE+T #E # 15) 接受 所得的结果是：用产生式序列表示语法分析树所得的结果是：用产生式序列表示语法分析树 (1) E-E+T | T (2) T-T*F | F (3) F-(E) | i i1 + i2 * i3 F T E F T F T E 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 算符优先分析 v算符优先分析法的思想源于表达式的分析，即利用相邻终 结符号之间的关系来寻找可归约串。 v将句型中的终结符号当作“算符”，借助于算符之间的优 先关系确定可归约串。 v显然，在一个符号串中，任意两个相邻终结符号a和b之间 ，只可能存在以下四种优先关系： (1) a, b优先性相同，记作a b。 (2) a优先性高于b， 记作a b。 (3) a优先性低于b ，记作a b。 (4) a与b不可能相邻，即此符号串不 是句型(出错)。 如果以上四种关系中的任意两种都不会同时成立，则 可以根据终结符号之间的归约关系进行语法分析。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v算符文法:一个上下无关文法G,如果没有P-,且没 有P-.QR.(P,Q,R属于非终结符),则G是一个算 符文法。 v算符优先关系的定义： a b,G中有P-.ab.或P-.aQb. (在同一产 生式中) a b,G中有P-.aR.的产生式,且R=b.或 R=Qb. a b,G中有P-.Rb.的产生式,且R=.a或 R=.aQ 算符优先文法（OPG）的定义 + + + 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例：EE+E | E*E | (E) | i 证明不是OPG文法。 因为：EE+E ， EE*E 则有 + * 又因为：EE*E, EE+E 则有 + * 所以不是算符优先文法。 v算符优先文法 算符文法G的任何终结符a,b之间要么没有 优先关系，若有优先关系,至多有 , , 中的一种成立,则G为一算符优先文法。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 算符优先关系表的构造 vFIRSTVT集 定义：对每个非终结符P, FIRSTVT(P)=a|P=a.或P=Qa.,a为终 结符,P，Q为非终结符 + 由优先性低于的定义和由优先性低于的定义和FIRSTVTFIRSTVT集合的定义可以得出：集合的定义可以得出： 若存在某个产生式：若存在某个产生式：aPaP，对，对所有：所有： bbFIRSTVTFIRSTVT (P)(P)，都有：，都有：a ba b。 按照下面两条规则来构造按照下面两条规则来构造FIRSTVTFIRSTVT集：集： 若有产生式若有产生式P-a.P-a.或或P-P-QaQa.,.,则则aFIRSTVT(PaFIRSTVT(P) ) 若有产生式若有产生式P-R.,P-R.,则则FIRSTVT(R)FIRSTVT(R)包含在包含在FIRSTVT(P)FIRSTVT(P)中中 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 vLASTVT集 定义：对每个非终结符P, LASTVT(P)=a|P = .a或P =.aQ, a为终结符,P，Q为非终结符 + 由优先性高于的定义和由优先性高于的定义和LASTVTLASTVT集合的定义可以得出：集合的定义可以得出： 若存在某个产生式：若存在某个产生式：PbPb，对，对所有：所有： aaLASTVTLASTVT (P)(P)，都有：，都有：a ba b。 按照下面两条规则来构造按照下面两条规则来构造LASTVTLASTVT集：集： 若有产生式若有产生式P-.aP-.a或或P- .P- .aQaQ, ,则则aLASTVT(PaLASTVT(P) ) 若有产生式若有产生式P-.R,P-.R,则则LASTVT(R)LASTVT(R)包含在包含在LASTVT(P)LASTVT(P)中中 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v构造优先关系表 如果每个非终结符的FIRSTVT和LASTVT 集均已知,则可构造优先关系表。 若产生式右部有.aP.的形式,则对 于每个bFIRSTVT(P)都有a b 若产生式右部有.Pb的形式,则对于每 个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b v构造优先关系表的算法如下： 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 For 每条形如PX1X2Xn的产生式 do for i =1 to n-1 do if Xi和Xi+1都是终结符 then Xi = Xi+1 if i Xi+1 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 算符优先分析算法 v通过比较终结符间的优先关系来实现 v根据优先分析的原理，语法分析程序的任务是：不 断移进输入符号，识别可归约串并进行归约。 v分析的方法：根据优先性“高于”来识别可归约串的 头，根据优先性“低于”来识别可归约串的尾。各种 优先关系已经存于优先关系表中。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v不能识别只由一个非终结符组成的句柄。不 能保证每次对句柄进行归约,在算符优先分 析过程中,每次归约的符号串,是当前句型的 最左素短语。 v素短语：至少含有一个终结符,且除自身外, 不再包含任何其它更小的素短语。 v最左素短语(leftmost prime phrase)：是 指位于句型最左边的那个素短语。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例：下述文法的一个句型： T * F + i 其短语、素短语、最左素短语分别是？ ET | E+T TF | T*F Fi | (E) E E + T F i T T * F 短语有：短语有：i, T * F, T * F + ii, T * F, T * F + i 素短语有：素短语有： i, T * Fi, T * F 最左素短语是：最左素短语是：T * FT * F 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 例:文法G E-E+T|T T-T*F|F F-(E)|i 句型T+T*F+i的语法树如图： E ET+ E+T F TT*F P 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为最左素短语。 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v一个算符文法G的某个句型的最左素短语可描述： 设句型的一般形式为(NiVN,ai VT #N1a1 N2a2 Nnan Nn+1# 它的最左素短语是满足下列条件的最左子串： Niai Ni+1ai+1 Njaj Nj+1 其中：ai-1ai, aiai+1 aj-1aj ， ajaj+1 该该定理说明了最左素短语与周围符号之间的关系定理说明了最左素短语与周围符号之间的关系 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v算符优先分析过程：(根据最左素短语的定义) 句型的一般形式: #N1a1N2a2.NnanNn+1#(ai为终结符,Ni为可有可 无的非终结符) 从左向右扫描各符号,依次查看算符优先 矩阵,直至找到满足ai ai+1的终结符为止,一 直移进，再从ai开始往左扫描,直至找到满足 关系 aj-1 aj的终结符为止,进行归约。 此时,形如:Nj aj Nj+1 aj+1.Ni ai Ni+1 的子串即为最左素短语，应被归约。 分析过程的结束：分析栈中为#S，输入 串为# 编译原理编译原理 长春工业大学计算机科学与工程学院长春工业大学计算机科学与工程学院 v例: E-E+T|T T-T*F|F F-(E)|i v把#入栈,读一符号i, 因为# + ,所以归约:F-i v因# * , 所以归约:F-i v因+ # ,