《PPT课件第6章 自底向上语法分析》由会员分享，可在线阅读，更多相关《PPT课件第6章 自底向上语法分析（41页珍藏版）》请在金锄头文库上搜索。
1、6.1 自底向上语法分析,一、自底向上方法概述 自底向上方法：从给定终极符串进行归约，并归约成文法的初始符。,移进-归约方法的四个动作: 移进:输入流头符读到分析栈中 归约:分析栈句柄归约非终极符 接受:分析成功 报错:处理错误,例子：对输入串abbcde进行分析，检查该串是否是GS的句子。 GS： SaAcBe Ab AAb Bd 对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcde SaAcBeaAcdeaAbcdeabbcde,所以移进-归约方法的分析过程如下：,例：考虑文法 G(E): ET|E+T TF|T*F Fi|(E) 并假定已给定终极符串(i+i)
2、*i。下面是对该串的移入归约过程:,( ,(i+i)*i) 1 =移=( , i+i)*i) 2 =移=(i , +i)*i) 3 =归=(F , +i)*i) 4,=归=(T , +i)*i) 5 =归=(E , +i)*i) 6 =移=(E+ , i)*i) 7 =移=(E+i , )*i) 8 =归=(E+F , )*i) 9 =归=(E+T , )*i) 10 =归=(E , )*i) 11 =移=(E) , *i) 12 =归=(F , *i) 13,=归=(T , *i) 14 =移=(T* , i) 15 =移=(T*i , ) 16 =归=(T*F , ) 17 =归=(T ,
3、 ) 18 =归=(E , ) 19,6.2 简单优先方法,优先关系可用矩阵来表示，称这种矩阵为优先关系矩阵。,具体定义如下图：,Msi,sj,STEP2：对每个符号对Si，Sj填写优先关系矩阵。,构造优先关系矩阵步骤：,STEP1：对每个非终极符号W求下面两种集合,例子：假设有文法 GZ: ZbMb Ma|( L LM a ),所以对GZ: ZbMb Ma|( L LM a ) 有：FRIST(M)= (,a LAST(M)= ),L,a 有下表：,定义3.13 满足下面两个条件的文法称为简单优先文法。 1.任意两个符号至多成立一种关系 2.任意两个产生式具有不同右部,例子：GZ: EE+T
4、|T TT*F|F F(E)|i,下面文法均不为简单优先文法,G1:Ba Da (有两个相同的右部),定理3.10 设S1S2Sn是简单优先文法的规范句型,其子串SiSi+1Sj满足条件:,+,试用简单优先方法分析符号串 b( a a )b 是否为该文法的句子。,例：设有GZ: ZbMb Ma|( L LM a ),分析句子b( a a )b的过程：,移进项目的处理,移进项目的处理,算符优先文法的定义 算符优先关系表的构造 算符优先分析算法 算符优先分析法的局限性,6.3 算符优先方法,分析程序模型,总控程序,算符优先关系表,产生式,输入串#,#,输出,6.3.1 直观算符优先分析法,自下而上
5、分析算法 模型-移进归约 算符优先分析不是规范归约,如何确定算符优先关系？,人为确定： （1）i的优先级最高 （1） 优先级次于i，右结合 （2）*和/优先级次之，左结合 （3）+和-优先级最低，左结合 （4）括号(,)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 （5）#的优先性低于与其相邻的算符,文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i,算符优先关系表,6.3.2 算符优先文法的定义,定义：如果不含空产生式的上下文无关文法 G 中没有形如 ABC的产生式，其中B，CVN 则称G 为算符文法（OG）。 例6.1 GE：EE+E|E-|E*E|E
6、/E|EE|(E)|i 例6.2 GE: EET|T TT*F|F FPFP P(E)|i 性质1：在算符文法中任何句型都不包含两个相邻的非终结符. 性质2：如 Ab 或 bA 出现在算符文法的 句型 中，其中 AVN，bVT， 则 中任何 含 b 的短语必含有A。,算符优先关系,在OG中 定义 （算符优先关系） a = b G中有形如：Aab 或A aBb.的产生式。 a b G中有形如: A Bb的产生 式,而 B a 或 B aC 规定 若 S a或 S Ca 则 # #,在 OG文法 G 中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 注意：允许b
7、c, cb; 不允许 bc, b“（”。 结论 : 算符优先文法是无二义的。,6.3.3 算符优先关系表的构造,首先定义如下两个集合： FIRSTVT(B)=bB b 或 B Cb LASTVT(B)=aB a 或 B aC 按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系： 1) =关系 直接看产生式的右部，若出现了A ab或 A aBb,则a=b 2)关系 求出每个非终结符B的LASTVT(B) 若ABb,则aLASTVT(B),则ab,计算算符优先关系,例6.3 文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6)
8、P(E)(7) Pi,FIRSTVT(E)=#FIRSTVT(E)=+,*,(,iFIRSTVT(T)=*,(,iFIRSTVT(F)=,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,*,),iLASTVT(T)=*,),iLASTVT(F)=,),iLASTVT(P)=),i,(0)E#E# (1) EE+T (2) ET (3) TT*F (4) TF(5) FPF|P (6) P(E) (7) Pi,3)关系找形如：ABb的产生式E#: 则 LASTVT(E)#E+: 则 LASTVT(E)+ T*: 则 LASTVT(T)* P: 则 LASTVT(P
9、) E): 则 LASTVT(E),2）关系找形如AaB的产生式#E：则 #FIRSTVT(E)+T: 则 +FIRSTVT(T) *F: 则 *FIRSTVT(F)F: 则 FIRSTVT(F)(E: 则 (FIRSTVT(E),1)=关系由产生式(0)和(6),得#=#， ( = ),表达式文法GE的算符优先关表,6.3.4 算符优先分析算法,算符优先文法句型的性质 算符文法的任何一个句型应为如下形式： N1a1N2a2 . Nnan Nn+1 其中N k(1kn+1)为非终结符或空，ak(1kn)为终结符 算符优先文法句型的最左素短语NiaiNi+1ai+1 . Njaj Nj+1满足：
10、 ai-1 ai ai =ai+1 = =aj-1 =aj aj aj+1 即：ai-1 aj+1,算符优先分析的可归约 串是句型的最左素短语 定义 cfg（上下文无关文法） G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语 文法GS短语的定义 S A且A 则称是句型相对于非终结符A的短语,例：有文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,1. 画出句型T+T*F+i的语法树并写出改句型的所有短语。 2. 写出句型T+T*F+i的简单短语和句柄。 3.写出句
11、型T+T*F+i的素短语和最左素短语。,文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,句型T+T*F+i其短语有：T+T*F+iT+T*FTT*Fi,E,E,T,+,+,E,T,*,F,T,T,i,最左素短语为：T*F,F,素短语为：T*F， i,简单短语为：T ， T*F， i,句柄为：T,句型T+T*F+i的语法树,E,E,T,+,+,E,T,*,F,T,T,i,句型T+T*F+i进行算符优先分析时语法树的框架,F,N,N,N,+,+,N,N,*,N,N,i,省略了ET, ET, ET的规约,F,句型T+T+F的素短语为：T+T 最左素短语是T+T,E,+,+,T,E,句型T+T+i的素短语为：T+T, I 最左素短语为T+T (注：T+T不是简单短语，但是素短语）,E,T,T,例：有文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi,F,E,+,+,T,E,E,T,T,i,分析程序模型,总控程序,算符优先关系表,产生式,输入串#,#,输出,算符优先分析法,简单，直观，有利于表达式分析，易于手工实现 比规范归约快 可能导致把错误的句子得到正确的归约,
