编译原理05自底向上的语法分析方法

1、1第第6 6章章 自底向上优先分析法自底向上优先分析法2主要内容主要内容3课题：课题：自底向上分析方法、算符优先文法目的要求：目的要求： 1.理解自底向上的语法分析方法的基本思想； 2.掌握算符文法、算符优先文法的定义和性质教学重点：教学重点： 1.优先分析法的基本思想和术语； 2.算符文法、算符优先文法的定义和性质教学难点教学难点 ： 算符优先关系的定义教学课时：教学课时：2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下） 第第 十二十二 讲讲4自底向上分析方法，也称移进归约分析法自底向上分析方法，也称移进归约分析法实现思想（是推导的逆过程）：实现思想（是推导的逆过程）

2、：对输入符号串自左向右进行扫描，并将输入符对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。到栈中只剩下文法的开始符号时，则分析成功。自底向上分析方法的基本思想自底向上分析方法的基本思想5例例1：文法：文法:saacbea ba abb d输入串输

3、入串abbcde#分析分析最右推导：最右推导： saacbe aacde aabcde abbcde规约分析过程如下：规约分析过程如下：6步骤步骤符号栈符号栈输入符号串输入符号串 动作动作1#abbcde#移进移进2#abbcde#移进移进3#abbcde#归约归约 ab 4#aabcde#移进移进5#aabcde#归约归约 aab 6#aacde#移进移进7#aacde#移进移进8#aacde#归约归约 bb 9#aacbe#移进移进10#aacbe#规约规约 saacbe11#s#接受接受7上述的每一步规约可以构造一颗语法树：上述的每一步规约可以构造一颗语法树：abbdaabbsabbac

4、ebda8问题的提出：问题的提出：在构造语法树的过程中，何时规约？在构造语法树的过程中，何时规约？ 当句柄出现在栈顶符号串中就可以规约。当句柄出现在栈顶符号串中就可以规约。如何知道在栈顶符号串中已经形成句柄？如何知道在栈顶符号串中已经形成句柄？ 通过自底向上的分析算法来解释（优先关系）通过自底向上的分析算法来解释（优先关系） 9优先分析法又可分简单优先分析法和算符优优先分析法又可分简单优先分析法和算符优先分析法。先分析法。简单优先分析法（规范归约）对文法按简单优先分析法（规范归约）对文法按一定原则求出所有文法符号间的优先关系；一定原则求出所有文法符号间的优先关系；算法优先分析法（不规范归约）规

5、定算法优先分析法（不规范归约）规定算算符符之间的优先关系）之间的优先关系） 6.1 6.1 自底向上优先分析法概述自底向上优先分析法概述106.3 6.3 算符优先分析法算符优先分析法 算符优先优先分析法算符优先优先分析法只规定算符（终结符）之间的优先关系。在只规定算符（终结符）之间的优先关系。在归约过程中只要找到句柄就归约，不必考虑归约过程中只要找到句柄就归约，不必考虑归约到哪个非终结符，因此不是规范归约。归约到哪个非终结符，因此不是规范归约。特点：速度快，特别适合于表达式的分析特点：速度快，特别适合于表达式的分析 通过算符之间的优先关系来确定句柄通过算符之间的优先关系来确定句柄11先看一个

6、例题：先看一个例题：例例. 已知文法已知文法ge： ee+e e e*e e i输入串输入串i+i*i ，归约过程如下，归约过程如下12步骤步骤符号栈符号栈输入符号串输入符号串优先关系优先关系 1） # i+i*i# #i 移进移进 2） #i +i*i# #+ 规约规约 3） #e +i*i# #+ 移进移进 4） #e+ i*i# +i 移进移进 5） #e+i *i# +* 规约规约 6） #e+e *i# +* 移进移进 7） #e+e* i# *i 移进移进 8） #e+e*i # *# 规约规约 9） #e+e*e # +# 规约规约10） #e+e # # 规约规约11） #e

7、# 接受接受动作动作13分析可知：若只从移进分析可知：若只从移进归约的角度来考虑，归约的角度来考虑，在第在第6步时栈顶已出现了句柄步时栈顶已出现了句柄e+e，可以进行，可以进行归约了，但是明显是错误的，因为这样就不归约了，但是明显是错误的，因为这样就不符合算术运算规律符合算术运算规律 。所以对于表达式，我们可以人为地规定其算所以对于表达式，我们可以人为地规定其算符的优先顺序，即给出优先级别和同一级别符的优先顺序，即给出优先级别和同一级别的结合性。的结合性。14算符文法定义：算符文法定义： 设有一文法设有一文法g，如果，如果g中没有形如中没有形如abc的产生式，其中的产生式，其中b和和c为非终结

8、符，则称为非终结符，则称g为为算符文法算符文法(或称或称og文法文法)。 即任何一个产生式中都不包含两个非终结即任何一个产生式中都不包含两个非终结符相邻的情况，就是算符文法。符相邻的情况，就是算符文法。 15性质性质1：在算符文法中任何句型都不包含两个：在算符文法中任何句型都不包含两个相邻的非终结符。相邻的非终结符。性质性质2：如果：如果ab或（或（ba）出现在算符文法的句）出现在算符文法的句型型 中，其中中，其中a vn， b vt，则，则 中任何含中任何含b的短语必含有的短语必含有a。（含（含b的短语必含的短语必含a，含，含a的短语不一定含的短语不一定含b） 16算符优先关系的定义：算符优

9、先关系的定义： 设设g是一个算符文法，是一个算符文法，a和和b是任意两个终结是任意两个终结符，符，a，b，c是非终结符，算符优先关系是非终结符，算符优先关系如下：如下： (1)a=b当且仅当当且仅当g中含有形如中含有形如aab或或aabb的产生式的产生式; (2) a b当且仅当当且仅当g中含有形如中含有形如abb的产生式，且的产生式，且ba或或bac 。17算符优先文法的定义：算符优先文法的定义： 设有一不含设有一不含 产生式的算符文法产生式的算符文法g，如果对，如果对任意两个终结符任意两个终结符a，b之间至多只有之间至多只有= ，三三种关系的一种成立，则称种关系的一种成立，则称g是一个算符

10、优先文是一个算符优先文法法(也称也称opg文法文法)。 即即a b，a b，a b只有一种成立，但允许只有一种成立，但允许a b，b a同时存在。同时存在。18例：已知表达式文法例：已知表达式文法ge： ee+e | e*e | (e) | i 证明证明ge不是不是opg文法。文法。证明如下：证明如下：因为：因为：ee+e ， ee*e 则有则有 + *所以不是算符优先文法。所以不是算符优先文法。19 自底向上分析方法，也称移进归约分析法，是推自底向上分析方法，也称移进归约分析法，是推导的逆过程。导的逆过程。 算法优先分析法（不规范归约）规定算法优先分析法（不规范归约）规定算符算符之间之间的优

11、先关系）的优先关系） 文法符号之间的优先关系有三种：大于、小于和文法符号之间的优先关系有三种：大于、小于和等于。等于。 算符优先文法算符优先文法(也称也称opg文法文法)，它是一个算符文，它是一个算符文法，不含法，不含 产生式，且对任意两个终结符产生式，且对任意两个终结符a，b之间至之间至多只有多只有= ，三种关系的一种成立。三种关系的一种成立。教学总结20教材教材p122练习练习: 2(1)，3(1)作 业21课题：课题：算符优先关系表和算符优先分析法目的要求：目的要求： 1.掌握算符优先关系表的构造方法； 3.掌握算符优先分析法及其局限性教学重点：教学重点： 1.符优先关系表的构造 2.算

12、符优先分析法的实现；教学难点教学难点 ： 算符优先关系表的构造教学课时：教学课时：2教学方法：教学方法：多媒体教学教学内容和步骤教学内容和步骤 ：（如下） 第第 十三十三 讲讲22三、三、 算符优先关系表算符优先关系表 用表格形式来表示各终结符号的优先关系，这用表格形式来表示各终结符号的优先关系，这种表称为优先关系表。种表称为优先关系表。 构造优先关系表的方法：构造优先关系表的方法：按照定义来构造按照定义来构造 按关系图来构造按关系图来构造 首先引入两个概念：首先引入两个概念：firstvt集合集合lastvt集合集合first(b)=b|bb 或或 bcblastvt(b)=a|ba 或或

13、bac +231) = 关系关系直接看产生式的右部，若出现了直接看产生式的右部，若出现了a ab或或a abb，则，则a=b2) 关系关系求出每个非终结符求出每个非终结符b的的firstvt(b)若若aab，则，则 bfirstvt(b)，a 关系关系求出每个非终结符求出每个非终结符b的的lastvt(b)若若abb，则，则 alastvt(b)，ab三种算符优先关系的计算：三种算符优先关系的计算：24例：已知文法如下，计算优先关系例：已知文法如下，计算优先关系 e#e# ee+t et tt*f tf fpf fp p（e ） pi25解解: (1)先先求求firstvt和和lastvt集集

14、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) 求求 关系关系e #e# 则则 # first(e) 所以所以 # +, # *, # , # ( ， # i 27e e+t 则则 + first(t) 所以所以 + *, + , + (

15、 , + itt*f 则则 * first(f) 所以所以 * , * ( , * ifpf 则则 first(f) 所以所以 , ( , ip（e ) 则（则（first(e) 所以所以 ( +, ( *, ( , ( ( , ( 关系关系e #e# 则则 lastvt(e) # 所以所以 + #, * # ，# , ) #, i #ee+t 则则lastvt(e) + 所以所以 + +, * +, + , ) +, i +tt*f 则则lastvt(t) * 所以所以 *, *, i *, ) *fpf 则则lastvt(p) 所以所以 i , ) p(e) 则则lastvt(e) ) 所

16、以所以 + ) , *) , ) , i ) , ) )29算符优先关系表算符优先关系表 +*i()#+*i(#= 30算符优先分析算法：算符优先分析算法：归约过程中，只考虑终结符之间的优先关系归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的规约过程与规范归约是不同的.为解决在算符优先分析过程中如何寻找句柄，为解决在算符优先分析过程中如何寻找句柄，引进最左素短语的概念引进最左素短语的概念31算符文法的任一句型有如下形式：

17、算符文法的任一句型有如下形式：#n1a1n2a2.nnannn+1#,若若niai.njajnj+1为句柄，为句柄，则有则有ai-1 ai+1对于算符优先文法，若句型对于算符优先文法，若句型r中含有中含有anb(或或ab) 若若ab，则在则在r中必有含中必有含a而不含而不含b的短语存在的短语存在若若a=b，则在则在r中含有中含有a的短语必含有的短语必含有b，反之反之亦然亦然32最左素短语最左素短语： 定义：设有文法定义：设有文法gs，其中句型的，其中句型的素短语素短语是一个短语，它至少包含一个终结符，并是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语，最左边的素除自身外不包含其它素

18、短语，最左边的素短语称短语称最左素短语最左素短语。 例：文法例：文法ge: ee+t|t tt*f|f fpf|p p（e）|i句型句型#t+t*f+i#的语法树如下：的语法树如下：33eet+e+tftt*fpi根据语法树可知：根据语法树可知：句型句型#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 算符优先关系表是指用表格形式来表示各终结算符优先关系表是指用表格形式来表示各终结符号的优先关系