《编译原理及其习题解答课件chap6-7》由会员分享，可在线阅读，更多相关《编译原理及其习题解答课件chap6-7（203页珍藏版）》请在金锄头文库上搜索。
1、编译原理 Compiler Principles,编译原理 Compiler Principles第六章 自底向上优先分析法,编译原理 Compiler Principles,第六章 自底向上优先分析法,自底向上的分析方法，也称移进-归约分析法。它的实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。确定的自底向上的分析方法分为两大类：
2、优先分析法和LR分析方法。本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。,编译原理 Compiler Principles,6.1 短语、直接短语、句柄,1、短语：令文法G，开始符号为S，xAy是G的句型（即S xAy），如果S xAy且A ，则称是句型 xy相对于非终结符A的短语。 2、直接短语（简单短语）如短语中有A= ，则称是句型相对于规则A 的直接短语。 3、句柄（Handle）一个句型的最左直接短语称为该句型的句柄。 （可规约串）,编译原理 Compiler Principles,例6.1,例：文法G数: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
3、| 8 | 9 = = = 1 所以， 1 是一个句型。下面结论是否正确？ 1. 1是句型 1相对于 的短语。 2. 1是句型 1相对于 的短语。 3. 是句型 1相对于 的短语。,编译原理 Compiler Principles,语法树与短语的关系,1. 每个句型（句子）都对应有一棵语法树； 2. 每棵语法树的叶子结点从左到右、从上到下构成一个句型（句子）； 3. 每棵子树的叶子结点从左到右、从上到下构成一个短语； 每棵子树的直接叶子结点从左到右、从上到下构成一个直接短语； 最左简单子树的直接叶子结点从左到右、从上到下构成一个句柄。,编译原理 Compiler Principles,例6.1
4、,1,编译原理 Compiler Principles,解题方法 例2,例：文法GE: E T | E+TT F | T*FF (E) | i 证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。,证明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i,编译原理 Compiler Principles,接上例,语法树：,E,E,+,T,T,T,*,F,F,F,i3,i1,i2,第1层 i1+i2*i3 相对于E 第2层 i1 相对于E ; i2*i3 相对于T 第3层 i1 ,i2 相对于T; i3 相对于F 第4层 i1 ,i
5、2 相对于F(F i直接短语) 第5层, i+i*i是G的一个句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型i1+i2*i3 的短语，且i1 , i2 , i3 为直接短语， i1为句柄,编译原理 Compiler Principles,分析说明,(2)作为“短语”的两个条件是不可缺少的，仅仅有A ，未必意味着就是句型的一个短语，因为还需要有S 这个条件。,例如：上例中有E i1+i2，但i1+i2并不是该句型的一个短语，因为不存在从E（开始符号）到E* i3的推导。,(1)短语、直接短语、句柄是针对某一句型（S ）而言的;,编译原理 Compiler Pri
6、nciples,解题方法, 先证明前提（如证明i+i*i是G的一个句型） 给出语法树（注意文法是否是二义性的）如题文法GE: E E+E|E*E|(E) | i 所以：证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。 根据每颗语法树得出短语、直接短语、句柄 例课本P143例6.3,编译原理 Compiler Principles,练习1题目,文法GT: T F | T*FF F P | P P (T) | i 证明T*P (T*F)是文法G的一个句型，并指出这个句型的所有短语、直接短语、句柄。,编译原理 Compiler Principles,练习解答,证明：T T*F
7、 T*FP T*F(T) T*F(T*F) T*P(T*F),语法树：,T,T,*,F,F,P,P,T,(,),T,*,F,第1层 T*P(T*F) 相对于T 第2层 P(T*F) 相对于F; 第3层 P 相对于F; (T*F) 相对于P 第4层 T*F 相对于T 第5层, T*P(T*F)是G的一个句型，其中T*F , P , (T*F), P(T*F), T*P(T*F) 都是该句型的短语，且T*F , P 为直接短语， P为句柄,编译原理 Compiler Principles,练习2题目,设有文法GS: S V1V1 V2 | V1iV2V2 V3 | V2+V3V3 )V1* | (
8、 (1)给出 (+(i( 的最右推导，并画出相应的语法树； (2)证明V2+V3i( 是文法的一个句型，并指出这个句型的短语、直接短语、句柄。,编译原理 Compiler Principles,练习解答（）,(1)解：S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+(i( V3+(i( (+(i(,语法树：,V1,V1,i,V2,(,S,V2,V2,+,V3,V3,V3,(,(,编译原理 Compiler Principles,练习解答（）,(2)证明： S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+V3i(是文法的一个句型短语：V2+
9、V3 , (, V2+V3i(直接短语： V2+V3 , (句柄： V2+V3,编译原理 Compiler Principles,算法应考虑的问题,算法是否能够终止？算法是否快速？算法是否能够处理所有的情况？在每一步中如何选择子串进行归约？,编译原理 Compiler Principles,文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #a
10、AcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,编译原理 Compiler Principles,自下而上分析法存在的问题,可归约串的问题；（ 该分析的每一步就是从当前串中找一个子串（称“可归约串”），将它归约到某个非终结符号）自下而上分析法的关键就是找哪个子串是“可归约串”，哪个不是“可归约串”。例如上例中的(3),因此必须精确定义“可归约串”，事实上存在着种种不同的方法刻画“可归约串”，对这个概念的不同定义，形成了不同的自下而上的分析法。在“规范归约”的分析中，用“句柄”来刻画“可归约串”。,编译原理 Compi
11、ler Principles,课本例6.4,例6.4 设文法GZ: Z - AB A - aAb A - ab B - bB B - c 对输入符号串aabbbc进行移进-归约分析。 分析过程在p146.,编译原理 Compiler Principles,非确定的自下而上的分析器,非确定的自下而上的分析器，是一般移进-归约方法的抽象模型，可识别任何上下文无关语言。给定一个上下文无关文法，可构造一个自下而上的分析器。非确定的自下而上的分析器与非确定的自上而下的分析器的不同之处：课本P147,编译原理 Compiler Principles,非确定的自下而上的分析器形式定义,非确定的自下而上的分析
12、器，是一个七元组。课本P147-148,编译原理 Compiler Principles,6.2 自底向上优先分析方法概述,优先分析方法可分为简单优先分析法和算符优先分析法。 1、简单优先分析法的基本思想对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，并按照这种关系来确定归约过程中的句柄。它的归约过程是一种规范归约。 2、算符优先分析法的基本思想只规定算符之间的优先关系（即只考虑终结符之间的优先关系），在规约过程中，只要找到句柄就规约，不考虑归约到哪个非终结符，不是规范归约。,编译原理 Compiler Principles,两种优先分析方法的比较,3、简单优先分析法
13、和算符优先分析法比较简单优先分析法准确、规范，但分析效率低，不实用；算符优先分析法不规范，但速度快，特别适用于表达式的分析。,编译原理 Compiler Principles,6.3 简单优先分析方法,按照文法符号之间的优先关系来确定句柄。 1、优先关系的表示（1）X=Y 表示X和Y的优先关系相等（2）XY 表示X的优先性比Y的优先性大,编译原理 Compiler Principles,6.3 简单优先分析方法,按照文法符号之间的优先关系来确定句柄。 2、优先关系的确定 （1）X=Y 文法G中存在产生式A.XY. （2）XY 文法G中存在产生式A.BD.，且B . X和D Y.,编译原理 Co
14、mpiler Principles,简单优先关系的确定 例子,文法GS： (1) S bAb (2) A (B|a (3) B Aa) 确定优先关系： （1）求=关系因为： S bAb 和A (B|a和 Aa)所以：b=A , A=b , ( = B , A=a , a = ) （2）求关系因为： S bAb ,且A ( B， A a所以：b ( , b a 因为： A (B ,且B (B， B a, B A所以: ( ( , ( a , ( 关系因为： S bAb ,且A )， A B， A a所以: ) b, B b, a b 因为： B Aa) ,且A )， A B， A a 所以: ) a, B a, a a,
