《编译原理-05自底向上的语法分析方法课件》由会员分享，可在线阅读，更多相关《编译原理-05自底向上的语法分析方法课件（37页珍藏版）》请在金锄头文库上搜索。
1、1,第6章 自底向上优先分析法,2,主要内容,6.1 自底向上优先分析概述 6.3 算符优先分析法,3,课题：自底向上分析方法、算符优先文法 目的要求： 1.理解自底向上的语法分析方法的基本思想； 2.掌握算符文法、算符优先文法的定义和性质 教学重点： 1.优先分析法的基本思想和术语； 2.算符文法、算符优先文法的定义和性质 教学难点 ： 算符优先关系的定义 教学课时：2 教学方法：多媒体教学 教学内容和步骤 ：（如下）,第 十二 讲,4,自底向上分析方法，也称移进归约分析法 实现思想（是推导的逆过程）： 对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶
2、符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。,自底向上分析方法的基本思想,5,例1：文法:,SaAcBe A b A Ab B d,输入串abbcde#分析,最右推导： SaAcBe aAcde aAbcde abbcde,规约分析过程如下：,6,7,上述的每一步规约可以构造一颗语法树：,8,问题的提出： 在构造语法树的过程中，何时规约？ 当句柄出现在栈顶符号串中就可以规约。 如何知道在栈顶符号串中已经形成句柄？ 通过自底向上的分析算法来解释（优先关系）,9,优先分析法又可分简单优先分
3、析法和算符优先分析法。 简单优先分析法（规范归约）对文法按一定原则求出所有文法符号间的优先关系； 算法优先分析法（不规范归约）规定算符之间的优先关系）,6.1 自底向上优先分析法概述,10,6.3 算符优先分析法,算符优先优先分析法 只规定算符（终结符）之间的优先关系。在归约过程中只要找到句柄就归约，不必考虑归约到哪个非终结符，因此不是规范归约。 特点：速度快，特别适合于表达式的分析 通过算符之间的优先关系来确定句柄,11,先看一个例题： 例. 已知文法GE： EE+E E E*E E i 输入串i+i*i ，归约过程如下,12,13,分析可知：若只从移进归约的角度来考虑， 在第6步时栈顶已出
4、现了句柄E+E，可以进行 归约了，但是明显是错误的，因为这样就不 符合算术运算规律 。 所以对于表达式，我们可以人为地规定其算 符的优先顺序，即给出优先级别和同一级别 的结合性。,14,算符文法定义：,设有一文法G，如果G中没有形如ABC 的产生式，其中B和C为非终结符，则称G为 算符文法(或称OG文法)。,即任何一个产生式中都不包含两个非终结 符相邻的情况，就是算符文法。,15,性质1：在算符文法中任何句型都不包含两个相邻的非终结符。 性质2：如果Ab或（bA）出现在算符文法的句型中，其中AVN， b VT，则中任何含b的短语必含有A。 （含b的短语必含A，含A的短语不一定含b）,16,算符
5、优先关系的定义：,设G是一个算符文法，a和b是任意两个终结符，A，B，C是非终结符，算符优先关系如下： (1)a=b当且仅当G中含有形如Aab或AaBb的产生式; (2) a b当且仅当G中含有形如ABb的产生式，且Ba或BaC 。,17,算符优先文法的定义：,设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有= ，三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。,即a b，a b，a b只有一种成立，但允许 a b，b a同时存在。,18,例：已知表达式文法GE： EE+E | E*E | (E) | i 证明GE不是OPG文法。 证明如下： 因为：EE+E
6、 ， EE*E 则有 + * 所以不是算符优先文法。,19,自底向上分析方法，也称移进归约分析法，是推导的逆过程。 算法优先分析法（不规范归约）规定算符之间的优先关系） 文法符号之间的优先关系有三种：大于、小于和等于。 算符优先文法(也称OPG文法)，它是一个算符文法，不含产生式，且对任意两个终结符a，b之间至多只有= ，三种关系的一种成立。,教学总结,20,教材P122练习: 2(1)，3(1),作 业,21,课题：算符优先关系表和算符优先分析法 目的要求： 1.掌握算符优先关系表的构造方法； 3.掌握算符优先分析法及其局限性 教学重点： 1.符优先关系表的构造 2.算符优先分析法的实现；
7、教学难点 ： 算符优先关系表的构造 教学课时：2 教学方法：多媒体教学 教学内容和步骤 ：（如下）,第 十三 讲,22,三、 算符优先关系表,用表格形式来表示各终结符号的优先关系，这种表称为优先关系表。 构造优先关系表的方法：按照定义来构造 按关系图来构造,首先引入两个概念： firstVT集合lastVT集合 first(B)=b|Bb 或 BCb lastVT(B)=a|Ba 或 BaC,+,+,+,+,23,1) = 关系 直接看产生式的右部，若出现了A ab或A aBb，则a=b 2) 关系 求出每个非终结符B的LASTVT(B) 若ABb，则aLASTVT(B)，ab,三种算符优先关
8、系的计算：,24,例：已知文法如下，计算优先关系 E#E# EE+T ET TT*F TF FPF FP P（E ） Pi,25,解: (1)先求firstVT和lastVT集 first(E)=# first(E)=+,*, ( , i first(T)=*, ( , i first(F)=, ( , i first(P)= ( , i ,lastVT(E)=# lastVT(E)=+,*, ) , i lastVT(T)=*, ) , i lastVT(F)= ) , i lastVT(P)= i , ) ,26,(2) 求 = 关系 E#E# # = # P(E) ( = ) (3) 求
9、 关系 E #E# 则 # first(E) 所以 # +, # *, # , # ( ， # i,27,E E+T 则 + first(T) 所以 + *, + , + ( , + i TT*F 则 * first(F) 所以 * , * ( , * i FPF 则 first(F) 所以 , ( , i P（E ) 则（first(E) 所以 ( +, ( *, ( , ( ( , ( i,28,(4) 求 关系 E #E# 则 lastVT(E) # 所以 + #, * # ，# , ) #, i # EE+T 则lastVT(E) + 所以 + +, * +, + , ) +, i +
10、 TT*F 则lastVT(T) * 所以 *, *, i *, ) * FPF 则lastVT(P) 所以 i , ) P(E) 则lastVT(E) ) 所以 + ) , *) , ) , i ) , ) ),29,算符优先关系表,30,算符优先分析算法：,归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的. 为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念,31,算符文法的任一句型有如下形式：#N1a1N2a2.NnanNn+1#,若Niai.NjajNj+1为句柄，则有ai-1 a
11、i+1 对于算符优先文法，若句型r中含有aNb(或ab) 若ab，则在r中必有含a而不含b的短语存在 若a=b，则在r中含有a的短语必含有b，反之亦然,32,最左素短语：,定义：设有文法GS，其中句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素短语称最左素短语。,例：文法GE: EE+T|T TT*F|F FPF|P P（E）|i 句型#T+T*F+i#的语法树如下：,33,根据语法树可知： 句型#T+T*F+i#的短语有： T ； T*F ； T+T*F ； i； T+T*F+i .,34,根据素短语的定义可知： i和T*F为素短语。 其中：T+T*F (含其他T*F素短语)和 T+T*F+i 不是素短语。 T*F为最左素短语。,六、算符优先分析法的局限性,35,算符优先关系表是指用表格形式来表示各终结符号的优先关系的表。 为分析算符之间的优先关系，引入两个概念：firstVT集合和lastVT集合：对于非终结符B，有 firstVT (B)=b|Bb 或 BCb lastVT(B)=a|Ba 或 BaC 为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念。 算符优先分析法只适用于对表达式的分析，其特点是分析速度快。,教学总结,36,教材P122练习: 4,作 业,
