第6章 自底向上优先分析法(lly)4.ppt

1、第6章 自底向上优先分析法,考查重点： 自底向上优先分析概述 简单优先分析（优先关系的理解） 算符优先分析 确定句型的短语、直接短语、句柄、素短语、最左素短语 算符优先关系矩阵的构造及输入串的过程分析,6.1 自底向上分析方法,1、自底向上分析方法，也称移进-归约分析法。,对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，（该句柄对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。 重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。,2、实现思想：,文法GS

2、：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,分析符号串abbcde是否GS的句子,对输入串abbcde#的移进-规约分析过程,自下而上语法分析相关问题,思想： 自下而上的语法分析过程是最右推导的逆过程（最左归约，即规范规约）；即从输入串开始，朝着文法开始符号进行归约，直至到达文法开始符号为止的过程。 核心：

3、 寻找句型中的“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法。 分类： 优先分析法（简单与算符） LR分析法,简单优先分析法 对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系(相邻有序符号间谁先归约)，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。 算符优先分析法 只规定算符（终结符）之间的优先关系。找到句柄就归约，并不考虑规约到哪个非终结符名，不是规范归约。,自下而上优先分析法,2、优先关系(相邻有序符号间谁先归约) X=Y 文法G中存在产生式A.XY. XY 文法G中存在产生式A.BD.，且B .X,D Y. （why）,6.2 简

4、单优先分析法,1、按照文法符号（包括终结符和非终结符）的优先关系确定句柄。,注意：优先关系的特点是相邻性与有序性 思考： 1）若有A.XYZ. 则X=Z？ 2）若XY ,则 YX ？,例：文法GS：(1) S bAb(2) A (B|a(3) B Aa),简单优先文法的定义,满足以下条件的文法是简单优先文法 （1）在文法符号集V中，任意两个符号之间(有序)最多只有一种优先关系成立。 （2）在文法中任意两个产生式没有相同的右部 （3）不含空产生式 思考： X=Y与XY可同时存在？ X=Y与YX可同时存在？,简单优先分析法,根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈S，

5、算法步骤如下： 将输入符号串a1a2a3.an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。 由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。 重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。 注意：何时移进，何时归约？归约中如何确定句柄？,如何确定优先关系？,例： 文法GS：(1) S bAb(2) A (B|a(3) B Aa),1. 求=关系： 由(1)：b=

6、A A=b 由(2)：(=B 由(3)：A=a a=),注意：行列与左右，空,4. #,3. 求关系： 由(1)：Bb ab)b 由(3)：Ba aa)a,2. 求关系： 由(1)(2)：b( ba 由(2)(3)：(A ( (a,简单优先关系矩阵,文法GS：(1) S bAb(2) A (B|a(3) B Aa),步骤,符号栈,输入符号串,动作,1） # b(aa)b# #b,移进,2） #b (aa)b# b(,移进,3） #b( aa)b# (a,移进,4） #b(a a)b# aa,归约Aa,5） #b(A a)b# A=a,移进,6） #b(Aa )b# a=),移进,7） #b(A

7、a) b# )b,归约BAa),8） #b(B b# Bb,归约A(B,9） #bA b# A=b,移进,10） #bAb # b#,归约SbAb,11） #S # 接受,对输入串b(aa)b#的简单优先分析过程,简单优先关系矩阵,注意：何时移进，何时归约？归约中如何确定句柄？,6.3 算符优先分析法,算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质(即：只考虑算符之间的优先关系来确定句柄。） 算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此不是一种规范归约法。 算符优先分析法是一种特别有利于表达式分

8、析，宜于手工实现的语法分析方法。 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性,二义文法，它的句子往往有不同的规范推导，按传统的习惯规定优先级从高到低为 : （0）i的优先级最高 （1） 优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性 （5）#优先性低于与其相邻的算符,例:文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,但是采用关于算符优先顺序和结合规则的规定， 并按这种规定

9、归约，那么归约过程就是唯一的。,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,步骤,符号栈,输入符号串,动作,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 # 接受,对输入串i+i*i的算符优先分析过程,算符优先关系表,注意：找“句柄”时非终结符处理！,算符文

10、法,定义 如果不含空产生式的上下文无关文法 G 中没有形如 UVW的产生式，其中V,WVN则称G 为算符文法（OG:Operater Grammar）。 性质1：在算符文法中任何句型都不包含两个相邻的非终结符.(数学归纳法/反证法) 性质2：如果 Vx 或 xV 出现在算符文法的句型 中，其中VVN,xVT, 则 中任何含 x 的短语必含有V.（反证法why）,OG中算符优先关系（与简单优先关系不同：“相邻”）,x = y （仅看当前产生式） G中有形如.Uxy或U xVy.的产生式。 x y （需要求W 的什么？） G中有形如.U Wy的产生式,而W x或W xV 规定 若 S x或 S V

11、x 则 # #,算符优先文法,定义: 在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 注意：允许bc,cb;不允许bc,bc,b=c 结论 : 算符优先文法是无二义的。 思考: 文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i 是算符文法吗? 是算符优先文法吗?,FIRSTVT(B)=b|B b 或 B Cb. 对于非终结符B，其往下推导所可能出现的首个算符（终结符） LASTVT(B)=a|B a 或 B . aC 对于非终结符B，其往下推导所可能出现的最后一个算符（终结符）,算符优先关系表的构造,由定义直接构造 由关系图法

12、构造算符优先关系表,首先引入两个概念(思考: FIRSTVT(B)与FIRSTVT(C)关系？),如何计算算符优先关系,1) =关系 直接看产生式的右部，若出现了A ab或A aBb,则a=b 2)关系 求出每个非终结符B的LASTVT(B) 若ABb,则aLASTVT(B),ab,例文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT

13、(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i,1)=关系由产生式(0)和(6),得#=#，（=）,3)关系找：ABb的产生式E# ,则 LASTVT(E)#E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) ,则 LASTVT(E),2）关系找：AaB产生式#E：则#FIRSTVT(E)+T: 则+FIRSTVT(T) *F: 则*FIRSTVT(F)F:则 FIRSTVT(F)(E: 则 (FIRSTVT(E),注意技巧！,算符优先分析句型的性质,算符文法的任一句型有如下形式（不

14、允许Ni相连）：#N1a1N2a2.NnanNn+1#, 若Niai.NjajNj+1为句柄，则有ai-1 ai+1,归约过程中，只考虑终结符之间的优先关系来确定“句柄”，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，P110. 为解决在算符优先分析过程中如何寻找“句柄” ，引进最左素短语的概念,最左素短语,定义 文法GS的句型的素短语是一个短语，它至少包含一个终结符，且除自身外 不再包含其他素短语。,素短语可以看作是包含有终结符的直接短语(错误的说法),处于句型最左边的素短语为最左素短语。,文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型#T+T*F+i#其短语有：,最左素短语为：T*F,思考：句型#T+T+i#的短语，直接短语，句柄，素短语，及最左素短语？,素短语：T*F， i,T+T*F+iT+T*FTT*Fi,算符优先分析法的局限性,一般语言的文法很难满足算符优先文