《编译原理-第04章(3)》由会员分享，可在线阅读，更多相关《编译原理-第04章(3)（44页珍藏版）》请在金锄头文库上搜索。
1、4.3 自下而上分析法的一般原理,自下而上分析法的一般原理:,编译中存在着多种自下而上的分析法，但不管哪种自下而上的分析法都是按照移进一归约法的原理建立起来的一种语法分析方法。,4.3 自下而上分析法的一般原理,$,t1,t3,ti,t2,tn,ti-1,ti+1,$,S,基本思想:,符号栈,可规约串,$,$,A,4.3 自下而上分析法的一般原理,例1. 设有文法GS:,(1) S aAcBe (2) A b (3) A A b (4) B d,对输入串abbcde进行自下而上语法分析, 检查该符号串是否该文法的正确句子。,4.3 自下而上分析法的一般原理,首先设一个符号栈并将输入符号串的左界
2、符$移入栈，分析时将输入符号串按从左到右扫描顺序移入栈中，其整个分析过程如下表所示。,S aAcBe(2) A b(3) A A b(4) B d 输入串abbcde,$ abbcde$,$a bbcde$,$ab bcde$,$aA bcde$,$aAb cde$,$aA cde$,$aAc de$,$aAcd e$,$aAcB e$,$aAcBe $,$S $,实现自下而上分析法的关键问题是如何精确定义可归约串这个直观概念，以及怎样识别“可归约串”？,4.3 自下而上分析法的一般原理,4.3 自下而上分析法的一般原理,对“可归约串”的不同定义形成不同的自下而上的分析方法,在规范归约分析法中
3、，是用句柄来刻画可归约串,而在算符优先分析法中,是用最左素短语来刻画可归约串。,(1) S aAcBe (2) A b(3) A A b(4) B d 输入串abbcde,4.3 自下而上分析法的一般原理,识别可归约串的不同方法，也同样形成不同的自下而上的分析方法, 简单优先分析法和LR分析法都是规范归约分析法，即都是用句柄刻画可归约串。,4.3 自下而上分析法的一般原理,但它们识别句柄的方法不同，LR分析法是根据历史、现实、展望三者信息来确定栈顶符号串是否形成句柄，而简单优先分析法是根据文法符号之间的优先关系来确定栈顶符号串是否形成句柄。,4.3 自下而上分析法的一般原理,下面，我们将介绍两
4、种常用的自下而上的分析方法即算符优先分析法和LR分析法。在这两种分析法中，重点讨论怎样识别栈顶符号串是可归约串以及如何进行归约。,4.4 算符优先分析法,方法概述,1.算符优先分析法,所谓算符优先分析法就是仿照算术表达式的四则运算过程而设计的一种语法分析方法。,这种分析方法首先要规定运算符之间(确切地说终结符之间)的优先关系和结合性质，然后借助这种关系，比较相邻运算符的优先级来确定句型的可归约串并进行归约。,4.4.1 方法概述,例如：文法GE为：,EE+E | E*E | (E) | id,这个文法是一个二义性文法，因而对句子id+id*id有两种不同的规范归约，也就是在归约过程中句型的句柄
5、不唯一。,4.4.1 方法概述,句子id+id*id的两种不同的规范归约过程如下：,第一个规范归约过程,(1) id + id * id (2) E + id * id (3) E + E * id (4) E + E * E (5) E + E (6) E,第二个规范归约过程,id + id * id (2) E + id * id (3) E + E * id (4) E * id (5) E * E (6) E,4.4.1 方法概述,分析上述归约过程，句型 E+E*id 在第一个规范归约中id是它的句柄; 而在第二个规范归约中EE是它的句柄。此现象是由于没有定义运算符和*的优先关系而引起
6、的。在第一个规范归约中是假定 *优先于, 所以不能立即把EE归约为E ; 而在第二个规范归约中是假定优先于* ,因此必须先把EE归约为E。,4.4.1 方法概述,可见上述归约过程中起决定作用的是相邻两个终结符号之间的优先关系。于是算符优先分析法的关键在于用合适的方法去定义任何两个可能相邻出现的终结符号a和b之间的优先关系。,4.4.1 方法概述,2. 任何两个相邻终结符号a 和 b之间的优 先关系有三种：,a的优先级低于b,a的优先级等于b,a的优先级高于b,4.4.1 方法概述,通常表达式中运算符的优先关系有,注意,优先关系与出现的左右次序有关,这一点是不同于数学中的,和。,但没有,而是有,
7、例如,不一定有,4.4.1 方法概述,优先关系表,算符优先分析法借助优先关系表寻找句型的可归约串。,4.4.1 方法概述,算符优先文法的定义,4.4.2 算符优先文法的定义,1.算符文法的定义,设有文法G, 若G中没有形如UVW的规则，其中V和W为非终结符，则称G为算符文法，也称OG文法。,4.4.2 算符优先文法的定义,也就是说，在算符文法中，任何一个规则右部都不存在两个非终结符相邻的情况。,2.定义任意两个终结符号之间的优先 关系,4.4.2 算符优先文法的定义,Pab,或 PaQb,的规则。,4.4.2 算符优先文法的定义,当且仅当G中含有形如,(2),PaR,的规则,且,或,当且仅当G
8、中含有形如,(3),的规则,且,或,PRb,4.4.2 算符优先文法的定义,3.算符优先文法的定义,4.4.2 算符优先文法的定义,对前述算术表达式的文法:,由算符文法和算符优先文法的定义，我们不难证明该文法是一个算符文法，但不是算符优先文法。,EE+E | E*E | (E) | id,4.4.2 算符优先文法的定义,因为该文法的任一规则右部都不包含两个相邻的非终结符，所以该文法是算符文法。,但是, 由于EE+E和,又由于EE*E和,4.4.2 算符优先文法的定义,即运算符和*之间存在两种不同的优先关系，所以该表达式的文法仅是算符文法而不是算符优先文法。,4.4.2 算符优先文法的定义,若算
9、术表达式的文法为：,E E + T | T T T * F | F F (E) | id,显然,该算术表达式的文法是算符优先文法。,4.4.3 算符优先关系表的构造,算符优先关系表的构造,对算符优先文法,根据优先关系的定义,可按如下方法直接构造优先关系表。,4.4.3 算符优先关系表的构造,首先对文法每个非终结符定义两个集合：,4.4.3 算符优先关系表的构造,使用这两个集合，构造文法的优先关系表的算法如下：,输入：算符优先文法,输出：关于文法的优先关系表,4.4.3 算符优先关系表的构造,方法：,1.为每个非终结符计算FIRSTVT(A)和LASTVT(A),2 .执行程序,for ( 每个
10、产生式 Ax1x2xn ),for ( i=1; i = n-1 ; i+ ),if ( i = n-2 且 xi和xi+2 都VT , 而xi+1VN ),if ( xiVT , xi+1VN ),if ( xiVN , xi+1VT ),4.4.3 算符优先关系表的构造,3. 对 FIRSTVT(S)中的所有b，置$ b;,（S为文法开始符号）,4.4.3 算符优先关系表的构造,例 设有表达式的文法GE：,E E + T | T T T * F | F F (E) | id,构造该文法的算符优先关系表。,4.4.3 算符优先关系表的构造,首先计算每个非终结符的FIRSTVT和LASTVT：
11、,4.4.3 算符优先关系表的构造,EE + T | TTT * F | FF(E) | id, *, +, (, id *, +, ), id , *, (, id *, ), id , (, id ), id ,4.4.3 算符优先关系表的构造,执行算法，逐条扫描文法规则，因有E(E)的规则，则有,4.4.3 算符优先关系表的构造,+ T,寻找终结符在左边，非终结符在右边的符号对有,* F,( E, *, (, id , (, id , *, +, (, id ,4.4.3 算符优先关系表的构造,4.4.3 算符优先关系表的构造,寻找非终结符在左边，终结在右边的符号对有,E +,T *,E ), *, ), id , *, +, ), id ,4.4.3 算符优先关系表的构造,从而构造出文法GE的算符优系表如下：,EE + T | TTT * F | FF(E) | id,本节完,
