精品课程《编译原理》第6章自底向上语法分析ppt课件

1、6.1 6.1 自底向上语法分析自底向上语法分析一、自底向上方法概述 自底向上方法：从给定终极符串进展归约，并归约成文法的初始符。 移进-归约方法的四个动作: 移进:输入流头符读到分析栈中 归约:分析栈句柄归约非终极符 接受:分析胜利 报错:处置错误 例子：对输入串abbcde进展分析，检查该串能否是GS的句子。 GS： SaAcBe Ab AAb Bd对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcdeSaAcBeaAcdeaAbcdeabbcde所以移进-归约方法的分析过程如下：移进e#aAcB9归约(Bd)e#aAcd8移进de# #aAc7移进cde# #a

2、A6归约(AAb)cde# #aAb5移进bcde# #aA4归约(Ab)bcde# #ab3移进bbcde# #a2移进abbcde# #1Action 输入串 符号栈 步骤 归约(SaAcBe)#aAcBe10接受#S11例：思索文法 G(E): ET|E+T TF|T*F Fi|(E)并假定已给定终极符串(i+i)*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 , )*

3、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 , ) 18=归=(E , ) 19 设Si和Sj是文法的恣意两个符号，那么它们在句型中相邻出现的充要条件是必需满足以下条件之一：1.有形如USiSj 的产生式2.有形如USiW 且W Sj的产生式3.有形如UVSj 且V Si的产生式的产生式4.有形如UVW 且V Si和W Sj的产生式的产生式+6.2

4、6.2 简单优先方法简单优先方法 定义了三种优先关系( , , )其定义如下： Si Sj：当且仅当存在如下的产生式USiSj 例子：AabABc，其中b与A相邻 b A Si Sj：当且仅当存在如下产生式USiW，且有W Sj) + 例子：AabABc Bbcd，其中A与b相邻 A b 例子：AabABc Accd Bbcb，其中d与b相邻 d b Si Sj：当且仅当存在如下产生式 UVW，且有V Si和W Sj) +* 优先关系可用矩阵来表示，称这种矩阵为优先关系矩阵。 详细定义如以下图：Msi,sj当 Si Sj当 Si Sj当 Si Sj空否那么* STEP2：对每个符号对Si，Sj

5、填写优先关系矩阵。构造优先关系矩阵步骤：* STEP1：对每个非终极符号W求下面两种集合 FIRST(W)=S|W S,S(VnVt) LAST(W)=S|W S,S(VnVt)+例子：假设有文法 GZ: ZbMb Ma|( L LM a )第一步： Zb M b b M Zb M b(a b ( b a第二步： Zb M b M b Zb M b)La ) b L b a b)a(bLMZ)a(bLMZ所以对GZ: ZbMb Ma|( L LM a ) 有：FRIST(M)= (,a LAST(M)= ),L,a 有下表：) L abLASTM ( a( abFIRSTLMZ定义3.13 满

6、足下面两个条件的文法称为简单优先文法。 1.恣意两个符号至多成立一种关系 2.恣意两个产生式具有不同右部 例子：GZ: EE+T|T TT*F|F F(E)|i EE+TT*F+ T + T下面文法均不为简单优先文法 v G1:Bav Da (有两个一样的右部)v G2:EE+T|Tv TT*F|F v F(E)|i (其中( E,( E)定理3.10 设S1S2Sn是简单优先文法的规范句型,其子串SiSi+1Sj满足条件:Si-1 Si，Si Si+1 Sj ， Sj Sj+1，那么SiSi+1Sj定为句柄。 例子：ZabCDe a b C D e 那么bCD是句柄。+ 试用简单优先方法分析

7、符号串b( a a )b 能否为该文法的句子。例：设有GZ: ZbMb Ma|( L LM a )分析句子b( a a )b的过程：)a(bLMZ)a(bLMZ(aa)b# #bb(aa)b# #b(aa)b# #归约符 输入流 分析栈 关系 a)b# #b(aMa)b# #b(aa)b# #b(M移进工程的处置移进工程的处置b#bMMb#b(LLb# #b(Ma)b# #b(Maa)b# #b(MMa)b# #b(aaa)b# #b(aa)b# #bb(aa)b# #归约符 输入流 分析栈 Z#bMb停#Z关系 算符优先文法的定义算符优先文法的定义 算符优先关系表的构造算符优先关系表的构造

8、算符优先分析算法算符优先分析算法 算符优先分析法的局限性算符优先分析法的局限性6.3 6.3 算符优先方法算符优先方法分析程序模型分析程序模型总控程序算符优先关系表产生式输入串#输出6.3.1 直观算符优先分析法直观算符优先分析法 自下而上分析算法自下而上分析算法 模型模型-移进归约移进归约 算符优先分析不是规范归约算符优先分析不是规范归约如何确定算符优先关系？如何确定算符优先关系？人为确定：人为确定：1 1i i的优先级最高的优先级最高1 1 优先级次于优先级次于i i，右，右结合结合2 2* *和和/ /优先级次之，左优先级次之，左结合结合3 3+ +和和- -优先级最低，左优先级最低，左

9、结合结合4 4括号括号( (, ,) )的优先级大的优先级大于括号外的运算符，小于于括号外的运算符，小于括号内的运算符，内括号括号内的运算符，内括号的优先性大于外括号的优先性大于外括号5 5# #的优先性低于与其相的优先性低于与其相邻的算符邻的算符文法文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i+-*/ ()i#+-*/ (=i#=算符优先关系表算符优先关系表 6.3.2 算符优先文法的定义算符优先文法的定义 定义：假设不含空产生式的上下文无关文法定义：假设不含空产生式的上下文无关文法 G G 中中没有形如没有形如 A ABCBC的产生式，其中的产生式，其中B B，CVN CV

10、N 那那么称么称G G 为算符文法为算符文法OGOG。 例例6.1 GE6.1 GE：EE+E|E-|EEE+E|E-|E* *E|E/E|EE|E/E|EE|(E)|iE|(E)|i 例例6.2 G6.2 GE: EEE: EET|TT|T TT TT* *F|FF|F FPF FPFP P P(E)|i P(E)|i 性质性质1 1：在算符文法中任何句型都不包含两个相邻：在算符文法中任何句型都不包含两个相邻的非终结符的非终结符. . 性质性质2 2：如：如 Ab Ab 或或 bA bA 出如今算符文法的出如今算符文法的 句型句型 中，其中中，其中 AVN AVN，bVTbVT， 那么那么

11、中任何中任何 含含 b b 的短语必含有的短语必含有A A。算符优先关系算符优先关系在在OGOG中中 定义定义 算符优先关系算符优先关系 a = b G a = b G中有形如：中有形如：A Aabab 或或A A aBb. aBb.的产生式。的产生式。 a b G a b G a b G中有形如中有形如: A : A Bb Bb的产生的产生 式式, ,而而 B a B a 或或 B aC B aC 规定规定 假设假设 S a S a或或 S Ca S Ca 那么那么 # a # # a #在在 OG OG文法文法 G G 中，假设恣意两个终结符间至多中，假设恣意两个终结符间至多有一种算符优先

12、关系存在，那么称有一种算符优先关系存在，那么称G G 为算符优为算符优先文法先文法(OPG)(OPG)。留意：允许留意：允许bc, cb;bc, cb;不允许不允许 bc, bc, bc, b=c中任两个中任两个 同时存在。同时存在。b=c b=c 不一定不一定 c = b c = b。例例6.16.1中：中：“ = = “，“。 结论结论 : : 算符优先文法是无二义的。算符优先文法是无二义的。6.3.3 算符优先关系表的构造算符优先关系表的构造首先定义如下两个集合：首先定义如下两个集合：FIRSTVT(B)=bB b 或或 B CbLASTVT(B)=aB a 或或 B aC按如下算法计算

13、出给定文法中任何两个终结符对按如下算法计算出给定文法中任何两个终结符对(a,b)之间的之间的优先关系：优先关系： 1) =关系关系直接看产生式的右部，假设出现了直接看产生式的右部，假设出现了A ab或或 A aBb,那么那么a=b 2)关系关系求出每个非终结符求出每个非终结符B的的FIRSTVT(B)假设假设AaB,那么那么bFIRSTVT(B),那么那么a关系关系求出每个非终结符求出每个非终结符B的的LASTVT(B)假设假设ABb,那么那么aLASTVT(B),那么那么ab计算算符优先关系计算算符优先关系例例6.3 文法文法GE：(0) E#E#(1) EE+T(2) ET(3) TT*F

14、(4) TF(5) FPF|P(6) P(E)(7) PiFIRSTVT(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) Pi3)关系关系找形如：找形如：ABb的产生式的产生式E#: 那么那么 LASTVT(E)#E+: 那么那么 LASTVT(E)

15、+ T*: 那么那么 LASTVT(T)* P: 那么那么 LASTVT(P) E): 那么那么 LASTVT(E)2关系关系找形如找形如AaB的产生式的产生式#E：那么：那么 #FIRSTVT(E)+T: 那么那么 +FIRSTVT(T) *F: 那么那么 *FIRSTVT(F)F: 那么那么 FIRSTVT(F)(E: 那么那么 ( * ( = i # = 6.3.4 算符优先分析算法算符优先分析算法 算符优先文法句型的性质算符文法的任何一个句型应为如下方式：N1a1N2a2 . Nnan Nn+1其中N k(1kn+1)为非终结符或空，ak(1kn)为终结符算符优先文法句型的最左素短语N

16、iaiNi+1ai+1 . Njaj Nj+1满足：ai-1 aiai =ai+1 = =aj-1 =ajaj aj+1即：ai-1 aj+1 算符优先分析的可归约算符优先分析的可归约 串是句型的最左素短语串是句型的最左素短语 定义定义 cfg上下文无关文法上下文无关文法 G 的句型的素短的句型的素短语是一个短语，它至少包含一个终结符，且除语是一个短语，它至少包含一个终结符，且除本身外不再包含其他素短语。处于句型最左边本身外不再包含其他素短语。处于句型最左边的素短语为最左素短语的素短语为最左素短语 文法文法GS短语的定义短语的定义 S A且且A 那么称那么称是句型是句型相对于非相对于非终结符终

17、结符A的短语的短语 *例：有文法例：有文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF|P(6) P(E)(7) Pi1. 画出句型画出句型T+T*F+i的语法树并写出改句型的一切短语。的语法树并写出改句型的一切短语。2. 写出句型写出句型T+T*F+i的简单短语和句柄。的简单短语和句柄。3.写出句型写出句型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*FiEET+ET* FTTi最左素短语为：最左素短语为：T*FF素短语为：素短语为：T*F， i简单短语为：简单短语为：T ， T*F， i句柄为：句柄为：T句型句型T+T*F+i的语法树的语法树EET+ET* FTTi 句型句型T+T*F+i进进展算符优先分析时语展算符优先分析时语法树的框架法树的框架FNNN+NN* NNi 省略了省略了ET, ET, ET的规约的规约F句型句型T+T+F的素短语为：的素短语为：T+T最左素短语是最左素短语是T+TE+ TE句型句型T+T+i