自底向上语法分析.ppt

《自底向上语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章自底向上语法分析6.1自底向上语法分析一、自底向上方法概述自底向上方法：从给定终极符串进行归约，并归约成文法的初始符。移进-归约方法的四个动作:移进:输入流头符读到分析栈中归约:分析栈句柄归约非终极符接受:分析成功报错:处理错误例子：对输入串abbcde进行分析，检查该串是否是G[S]的句子。G[S]：S→aAcBeA→bA→AbB→d对输入串abbcde的最右推导是：SaAcBeaAcdeaAbcdeabbcdeSaAcBeaAcdeaAbcdeabbcde所以移进-归约方法的分析过程如

2、下：移进e##aAcB9归约(B→d)e##aAcd8移进de##aAc7移进cde##aA6归约(A→Ab)cde##aAb5移进bcde##aA4归约(A→b)bcde##ab3移进bbcde##a2移进abbcde##1Action输入串符号栈步骤归约(S→aAcBe)##aAcBe10接受##S11例：考虑文法G(E):E→T

3、E+TT→F

4、T*FF→i

5、(E)并假定已给定终极符串(i+i)*i。下面是对该串的移入─归约过程:(,(i+i)*i)1=移=>((,i+i)*i)2=移=>((i,+i)*i

6、)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,)18=归=>(E,)19设Si和Sj是文法的任意两个符号，那么它们在句型中相邻出现的充要条件是必须满足下列条

7、件之一：1.有形如U→SiSj的产生式2.有形如U→SiW且WSj的产生式3.有形如U→VSj且VSi的产生式的产生式4.有形如U→VW且VSi和WSj的产生式的产生式++++6.2简单优先方法定义了三种优先关系(,,)其定义如下：SiSj：当且仅当存在如下的产生式U→…SiSj…例子：A→abABc，其中b与A相邻bASiSj：当且仅当存在如下产生式U→…SiW…，且有WSj……)+例子：A→abABcB→bcd，其中A与b相邻Ab例子：A→abABcA→ccdB→bcb

8、，其中d与b相邻dbSiSj：当且仅当存在如下产生式U→…VW…，且有VSi和WSj……)+*优先关系可用矩阵来表示，称这种矩阵为优先关系矩阵。具体定义如下图：M[si,sj]当SiSj当SiSj当SiSj空否则STEP2：对每个符号对Si，Sj填写优先关系矩阵。构造优先关系矩阵步骤：STEP1：对每个非终极符号W求下面两种集合FIRST(W)={S

9、WS,S(Vn∪Vt)}LAST(W)={S

10、WS,S(Vn∪Vt)}++例子：假设有文法G[Z]:Z→bMbM→a

11、(LL→Ma)第一步：①Z

12、→bMbbM②Z→bMb(…a…b(ba第二步：①Z→bMbMb②Z→bMb…)…L…a)bLbab)a(bLMZ)a(bLMZ所以对G[Z]:Z→bMbM→a

13、(LL→Ma)有：FRIST(M)={(,a}LAST(M)={),L,a}有下表：))LabLASTM(a(abFIRSTLMZ定义3.13满足下面两个条件的文法称为简单优先文法。1.任意两个符号至多成立一种关系2.任意两个产生式具有不同右部例子：G[Z]:E→E+T

14、TT→T*F

15、FF→(E)

16、iEE+TT*F+T+T下面文法均不为简单优先

17、文法G1:B→aD→a(有两个相同的右部)G2:E→E+T

18、TT→T*F

19、FF→(E)

20、i(其中(E,(E)定理3.10设S1S2Sn是简单优先文法的规范句型,其子串SiSi+1Sj满足条件:Si-1Si，SiSi+1Sj，SjSj+1，则SiSi+1Sj定为句柄。例子：ZabCDcabCDe则bCD是句柄。分析句子b(aa)b(文法G[Z])的过程：)a(bLMZ)a(bLMZ(aa)b##bb(aa)b##b(aa)b##归约符输入流分析栈关系a)b##b(aMa)b##b(aa)b##b(M移进

21、项目的处理移进项目的处理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关系算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性6.3算符优先方法分析程序模型总控程序算符优先关系表产生式输入串##输出6.3.1直观算符优先分析法自下而