《编译原理自下而上语法分析》由会员分享，可在线阅读，更多相关《编译原理自下而上语法分析（36页珍藏版）》请在金锄头文库上搜索。
1、自下而上语法分析,掌握自底相上分析的基本思想，基本概念掌握算符优先关系的判定，求FIRSTVT集,LASTVT集,构造算符优先关系表，能运用算符优先分析方法进行表达式分析掌握最左素短语、句柄的定义与判定理解规范规约与算符优先归约的区别 LR(0)和SLR文法的理解,自下而上的语法分析,实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功， 称为“移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析
2、树，直到形成根结。是推导的逆过程。核心寻找可归约串(这是关键)进行规约。用不同的方法寻找可归约串，就可获得不同的分析方法。,最左推导(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(
3、2)A b (3)A Ab(4)B d,最左归约过程是最右推导的逆过程， 对输入串abbcde的归约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b a,A a,b A a,A a,c A a,dc A a,Bc A a,eBc A a,S,语法分析树的生成演示,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,这种分析过程具有如下特点：从输入串的开始依次读入单词(移进栈中) 。一旦发现可归约串(某个产生式的右端)就立即归约。归约就是将栈顶的一串符号用文法产生式的左
4、部代替，归约可能重复多次，然后继续移进。若最终能归约成文法的开始符号，则分析成功。关键是如何判断可归约串？,问题的提出： 在构造语法树的过程中，何时归约？ 当可归约串出现在栈顶时就进行归约。 如何知道在栈顶符号串中已经形成可归约串？ 如何进行归约？ 通过不同的自底向上的分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,规范归约概念,有文法G，开始符号为S, 如果有S=xy,则xy是文法G的句型，x,y是任意的符号串如果有S=xAy, 且有A=,则是句型xy相对于非终结符A的短语如果有S=xAy, 且有A-,则是句型xy相对于A-的直接短语位于一个
5、句型最左边的直接短语称为句柄。,注: 每次归约的部分必须是称之为句柄的字符串(最右推导)。关键的问题是如何识别句柄,例子,下面的例子说明作为短语的两个条件缺一不可。例考虑表达式文法： 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 短语：句型(a),S) S =* (T,S) T =+ (a) 句型(T,S),S) S =
6、* (T),S) T =+ T,S 句型(a,(T),(T,S)直接短语以及句柄：S =* (T,(T),(T,S) T = aS =* (a,S,(T,S) S =(T)S =* (a,(T),(T) T =T,S,短语与语法树的关系,短语：语法树子树的叶子结点组成的符号串。直接短语：语法树简单子树（只有父子两代）的叶子结点组成的符号串。句柄：语法树最左边简单子树的叶子结点组成的符号串。,短语与语法树关系的例子,句型(a,(T),(T,S)的语法树：,用句柄对句子abbcde进行归约,用句柄对句子进行归约的过程与用移进-归约过程是一致的，使用归约的产生式及其顺序是一致的。,(1)S aAcB
7、e(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, 0E+T|TT-T*F|FF-(E)|i对输入串 i1+i2*i3 的规范归约过程：,动作 栈 输入缓冲区1) 准备 # i1+i2*i3#2) 移进 #i1 +i2*i3#3) 归约 Fi #F +i2*i3#4) 归约
8、 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) 接受,所得的结果是：用产生式序列表示语法分析树,E-E+T | TT-T*F | FF-(E) | i,i1 + i2 * i3,F,T,E,F,T,F,T,E,算符优先分析,算符优先分析法的思想源于表达式的分析，即
9、利用相邻终结符号之间的关系来寻找可归约串。将句型中的终结符号当作“算符”，借助于算符之间的优先关系确定可归约串。显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：(1) a, b优先性相同，记作a b。(2) a优先性高于b， 记作a b。(3) a优先性低于b ，记作a b。(4) a与b不可能相邻，即此符号串不是句型(出错)。 如果以上四种关系中的任意两种都不会同时成立，则可以根据终结符号之间的归约关系进行语法分析。,算符文法:一个上下无关文法G,如果没有P-,且没有P-.QR.(P,Q,R属于非终结符),则G是一个算符文法。 算符优先关系的定义：a b,G
10、中有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 则有 + *所以不是算符优先文法。,算符优先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 , , 中的一种成立,则G为一算符优先文法。,算符优先关系表的构造,FIRSTVT集定义：对每个非终结符P, FIRSTVT
11、(P)=a|P=a.或P=Qa.,a为终结符,P，Q为非终结符,由优先性低于的定义和FIRSTVT集合的定义可以得出： 若存在某个产生式：aP，对所有： bFIRSTVT (P)，都有：a b。,按照下面两条规则来构造FIRSTVT集： 若有产生式P-a.或P-Qa.,则aFIRSTVT(P) 若有产生式P-R.,则FIRSTVT(R)包含在FIRSTVT(P)中,LASTVT集 定义：对每个非终结符P, LASTVT(P)=a|P = .a或P =.aQ, a为终结符,P，Q为非终结符,+,+,由优先性高于的定义和LASTVT集合的定义可以得出： 若存在某个产生式：Pb，对所有： aLAST
12、VT (P)，都有：a b。,按照下面两条规则来构造LASTVT集： 若有产生式P-.a或P- .aQ,则aLASTVT(P) 若有产生式P-.R,则LASTVT(R)包含在LASTVT(P)中,构造优先关系表如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集,都有a b 若产生是形如：Aab 或 AaBb形式，则有a b构造优先关系表的算法如下：,For 每条形如PX1X2Xn的产生式 dofor i =1 to n-1 do if Xi和Xi+1都是终结符 then Xi = Xi+1 if i= n-2 且 xi和Xi+2都是终结符, Xi+1为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for firstVT中的每个元素a doXi Xi+1 ,
