东北大学秦皇岛分校编译原理课件第六章.ppt

《东北大学秦皇岛分校编译原理课件第六章.ppt》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件第六章.ppt（30页珍藏版）》请在三一办公上搜索。

1、第6章 自底向上优先分析法,自底向上分析法的基本思想及主要方法,自底向上分析法也称移进-归约法。自底向上分析法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上归约，试图归约到文法的识别符号。从语法树的角度来看：自底向上分析的过程是以输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。自底向上分析法的关键在于：如何在每一步归约当中，找到当前句型的句柄，并判断句柄是否唯一。主要的分析方法有：简单优先分析法、算符优先分析法、LR类分析法。,自底向上分析法中面临的问题及解决方法,采用自底向上分析法分析的每一步中，会遇到两个基本问题：（1）如何找出进

2、行直接归约的简单短语？（2）找出的简单短语应直接归约到哪一个非终结符号？解决方法：由于分析过程是从左往右扫描源程序，所以遇到的第一个简单短语正好是句柄，因此，第一个问题变为：如何找到句柄。对于如何找到句柄，找到句柄后应归约到哪一个非终结符号这两个问题，不同的自底向上分析法有不同的解决方法。简单短语：只经过一次推导得到的短语叫简单短语；句柄：句型的最左简单短语。,自底向上分析法的基本实现方法,自底向上分析的基本实现方法是：移进-归约法。引入“#”作为栈底标志符号。在整个分析过程中，共有4类动作：（1）移入：读入下一个输入符号并把它下推进栈。（2）归约：当栈顶的（部分）符号串形成一个句柄时，对此句

3、柄进行归约，把形成句柄的符号串替换为相应的非终结符号。（3）接受：当识别程序发现栈顶除了栈底标志符号#外仅有识别符号，而输入也以达到右端标志符号#时，便识别出输入符号串是一个句子，执行接受动作并结束本次识别。（4）报错：发现输入符号串不是句子而无法继续识别。,自底向上优先分析法的基本思想,常见的自底向上的分析算法：（1）优先分析法（2）LR类分析法 优先分析法分为：（1）简单优先分析法：采用规范归约，考虑所有文法符号（包括终结符号、非终结符号）之间的优先关系。（2）算符优先分析法：不是规范归约，只考虑算符（即终结符号）之间的优先关系。自底向上优先分析法的基本思想：利用文法符号中相邻符号之间的优

4、先关系找出句柄。,简单优先分析法及简单优先文法,简单优先分析法按照文法符号（终结符号和非终结符号）的优先关系确定句柄。如何确定任意两个文法符号之间的优先关系？如何构造优先关系表,补充内容,FIRST关系：U FIRST S存在规则 US（注：S可以是终结符号，也可以是非终结符号。）FIRST关系的传递闭包：FIRST+=FIRST FIRST2 FIRST3 LAST关系：U LAST S存在规则 US（注：S可以是终结符号，也可以是非终结符号。）LAST关系的传递闭包：LAST+=LAST LAST 2 LAST 3,例：求文法G的FIRST关系和LAST关系,GA：AAf|BBDdc|De

5、CeDBf,AAf AB BDdc BDe Ce DBf,A FIRST A A FIRST B B FIRST D B FIRST D C FIRST e D FIRST B,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B）,A LAST f A LAST B B LAST c B LAST e C LAST e D LAST f,LAST=（A，f），（A，B），（B，c），（B，e），（C，e），（D，f）,FIRST=（A，A），（A，B），（B，D），（C，e），（D，B）FIRST2=（A，A），（A，B），（A，D），（B，B），（D，D）FIRST3=（A

6、，A），（A，B），（A，D），（B，D），（D，B）FIRST4=FIRST2 FIRST+=FIRST FIRST2 FIRST3=(A，A)，(A，B)，(A，D)，(B，D)，(C，e)，(D，B)，(D，D),LAST=(A，f)，(A，B)，(B，c)，(B，e)，(C，e)，(D，f)LAST+=(A，f)，(A，B)，(A，c)，(A，e)，(B，c)，(B，e)，(C，e)，(D，f),优先关系的形式定义：（1）相等关系 X=Y：当且仅当G中存在规则 AXY（2）小于关系X Y）（3）大于关系XY：当且仅当G中存在规则 ABD，且 B LAST+X（即B=X）和 D FIRS

7、T*Y（即D=Y）。在此限定S为终结符号。简单优先文法满足条件：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部。由简单优先文法的定义可知，简单优先文法是无二义性的。,+,+,*,构造优先关系,构造相等关系“=”很简单，只需要顺次考察文法的各规则即可。如：例6.2（1）。构造大于和小于关系，可以使用如下两个公式：,其中，（FIRST*）为FIRST的自反传递闭包；（LAST+）T为LAST+的逆关系。,例：构造文法GZ的简单优先关系表,GS：SbAb，A（B|a，BAa）,首先构造相等（=）关系。根据文法规则：=（b，M）,（M，b）

8、,（，L），（A，a）,（a，）,构造小于（）关系：FIRST=（S，b）,（A，（）,（A，a）,（B，A）FIRST+=（S，b）,（A，（）,（A，a）,（B，A）,（B，（）,（B，a）=（=）（FIRST+）=（b，（）,（b，a）,（，A）,（，（）,（，a）,构造大于（）关系：LAST=（S，b）,（A，B）,（A，a）,（B，）LAST+=（S，b）,（A，B）,（A，a）,（A，）,（B，）（LAST+）T=（b，S）,（B，A）,（a，A）,（），B）,（），A）=（LAST+）T（=）（FIRST*）=（B，b）,（B，a）,（a，b）,（a，a）,（），b）,（），a）

9、,文法GZ的优先关系矩阵,课堂练习：利用公式求出例6.2的三个优先关系，并给出其优先关系矩阵。,简单优先分析法算法,根据给定的简单优先文法构造出相应的简单优先关系表，并将文法的产生式保存，设置符号栈S，再根据如下算符步骤进行分析：（1）将输入符号串a1a2an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。（2）栈顶当前符号ai尾句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1 ak，为止。（3）由句柄akai在文法的产生式中查找右部尾akai的产生式，若找到则用相应左部代替句柄，若找不到则出错。（4）重复上述三个步骤直到规约完输入符号串，栈中只剩文法

10、的开始符号或出错为止。,算符优先分析法,算符优先分析法常用于高级语言的表达式的语法分析。算符优先关系的形式定义：（1）相等关系 a=b：当且仅当G中存在 Aab 或 AaBb 的规则。（2）小于关系a b 或 B=Cb（3）大于关系a b：当且仅当G中存在规则 ABb，且B=a 或 B=aC 算符优先分析法的基本思想：根据算符（广义为终结符号）之间的优先关系来决定如何归约。,+,+,+,+,算符文法及其性质,算符文法的形式定义：设有一文法G，如果G中没有形如ABC的规则，其中B和C为非终结符，则称G为算符文法，也称OG文法。算符文法的性质：（1）在算符文法中任何句型都不包含两个相邻的非终结符。

11、（2）如果Ab（或bA）出现在算符文法的句型中，其中AVN，bVT，则中任何含b的短语必含有A。,算符优先文法及其性质,算符优先文法的形式定义：设有一不含产生式的算符文法G，如果对任意两个终结符对a,b之间至多只有=、三种关系中的一种成立，则称G是一个算符优先文法。也称为OPG文法。算符优先文法的性质：如果aNb或ab出现在句型r中，则a和b之间有且仅有一种优先关系即：（1）若a b 则 在r中必有含a而不含b的短语存在（3）若a=b 则 在r中含有a的短语必含有b，反之亦然。,算符优先关系表的构造,由定义直接构造（1）FIRSTVT集合：FIRSTVT（B）=b|B=b或B=Cb（2）LAS

12、TVT集合：LASTVT（B）=a|B=a或B=aC 由关系图法构造（1）FIRST关系：A FIRST B 当且仅当存在形如 AB 的产生式。（2）LAST关系：A LAST B 当且仅当存在形如 A B 的产生式。（3）FIRSTTERM关系：B FIRSTTERM b 当且仅当存在形如 Bb 或 BCb的产生式。（4）LASTTERM关系：B FIRSTTERM a 当且仅当存在形如 Ba 或 BaC的产生式。（5）FOLLOWEDB关系：X FOLLOWEDB Y 当且仅当存在形如 AXY 的产生式（X、Y中必须是一个为终结符，另一个为非终结符）。用公式法构造（1）=（LAST*）（L

13、ASTTERM）T（=）,+,+,+,+,编译方法中对公式的证明：注意：此处相等关系的符号为“”，与教材采用的符号不同。规则中连接左部与右部的符号也不同，为EBNF中的形式。,例：用公式构造文法GE的算符优先关系表,课堂练习：求该文法的优先关系“”,用程序构造算符优先关系的方法和步骤,教材,算符优先分析法与最左素短语,引入最左素短语的目的：解决在算符优先分析过程中如何寻找句柄的问题。最左素短语的形式定义：设有文法GS，其句型的素短语是一个短语，该短语至少包含一个终结符，并且除自身外不包含其他素短语，最左边的素短语称最左素短语。由句型的语法图我们可以直接找出所有的素短语和最左素短语。算符优先分析

14、法的关键问题是寻找最左素短语。算符优先分析法的局限性：算符优先分析法去掉了单个非终结符之间的归约，使得其在分析过程中很难完全避免把错误的句子得到正确的归约。,算符优先分析法算法,算符优先分析法的算法用到一个符号栈S和一个存放输入符号串的数组R，算法中的Q为一工作单元，用于存放待比较的终结符号：（1）将输入符串R1R2RK依次逐个存入符号栈S中，直至符号栈顶元素Sj与下一个待输入的符号Rk有关系Sj Rk为止；（2）最左素短语尾Sj已在符号栈S的栈顶，由此往前（左）在栈中找最左素短语的头符号Si，直至找到第一个 Si Q（Q=Sj）为止；（3）已找到最左素短语SiSj，将其归约到任意一个非终结符。重复上述过程，直至j=2且RK=#为止。,优先函数,优先关系表是以矩阵的形式在计算机内存储的，占用的空间相对较大。引入优先函数是为了减少存储优先关系的存储空间。现在计算机的存储资源已经非常可观，由于优先函数虽然能节省一定的存储空间，但由于其某些情况下不能准确地提供出错位置等信息，因此现在已不再使用优先函数的形式来存储优先关系。,