《自底向上语法分析》由会员分享，可在线阅读，更多相关《自底向上语法分析（39页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 自底向上语法分析自底向上语法分析6.1 自底向上语法分析一、自底向上方法概述自底向上方法：从给定终极符串进 行归约，并归约成文法的初始符。 移进-归约方法的四个动作: 移进:输入流头符读到分析栈中 归约:分析栈句柄归约非终极符 接受:分析成功 报错:处理错误 例子：对输入串abbcde进行分析，检查该 串是否是GS的句子。GS： SaAcBe Ab AAb Bd 对输入串abbcde的最右推导是： SaAcBeaAcdeaAbcdeabbcde SaAcBeaAcdeaAbcdeabbcde所以移进-归约方法的分析过程如下：移进e#aAcB9归约(Bd)e#aAcd8移进de#
2、 #aAc7移进cde# #aA6归约(AAb)cde# #aAb5移进bcde# #aA4归约(Ab)bcde# #ab3移进bbcde# #a2移进abbcde# #1Action 输入串 符号栈 步骤 归约 (SaAcBe)#aAcBe10 接受#S11例：考虑文法 G(E): ET|E+TTF|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
3、+ , 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是文法的任意两个符号，那 么它们在句型中相邻出现的充要条件是 必须满足下列条件之一： 1.有形如USiSj 的产生式 2.有形如USiW 且W Sj的产生式 3.有形如UVSj 且V Si的产生式
4、的产生式 4.有形如UVW 且V Si和W Sj的 产生式的产生式+6.2 简单优先方法定义了三种优先关系( , , ) 其定义如下： Si Sj：当且仅当存在如下的产生式 USiSj 例子：AabABc，其中b与A相邻b A Si Sj：当且仅当存在如下产生式 USiW，且有W Sj) +例子：AabABcBbcd，其中A与b相邻A b例子：AabABcAccdBbcb，其中d与b相邻d b Si Sj：当且仅当存在如下产生式 UVW，且有V Si和W Sj) +*优先关系可用矩阵来表示，称这种矩 阵为优先关系矩阵。具体定义如下图：Msi,sj当 Si Sj当 Si Sj当 Si Sj空否则
5、* STEP2：对每个符号对Si，Sj填写优 先关系矩阵。构造优先关系矩阵步骤：* STEP1：对每个非终极符号W求下面两 种集合 FIRST(W)=S|W S,S(VnVt) LAST(W)=S|W S,S(VnVt)+例子：假设有文法GZ: ZbMbMa|( LLM a ) 第一步： Zb M b b MZb M b( a b ( b a第二步： Zb M b M bZb M b)La ) b L b a b)a(bLMZ)a(bLMZ所以对GZ: ZbMbMa|( LLM a ) 有：FRIST(M)= (,a LAST(M)= ),L,a 有下表：) L abLASTM ( a( ab
6、FIRSTLMZ定义3.13 满足下面两个条件的文法称 为简单优先文法。1.任意两个符号至多成立一种关系2.任意两个产生式具有不同右部 例子：GZ: EE+T|TTT*F|F F(E)|i EE+TT*F+ T + T下面文法均不为简单优先文法 v G1:BaDa (有两个相同的右部)v G2:EE+T|TTT*F|F F(E)|i (其中( E,( E)定理3.10 设S1S2Sn是简单优先文法的 规范句型,其子串SiSi+1Sj满足条件:Si-1 Si，Si Si+1 Sj ， Sj Sj+1，则SiSi+1Sj定为句柄。 例子：ZabCDca b C D e 则bCD是句柄 。分析句子b
7、( a a )b(文法GZ)的过程：)a(bLMZ)a(bLMZ(aa)b# #bb(aa)b# #b(aa)b# #归约符 输入流 分析栈 关系 a)b# #b(a Ma)b# #b(a a)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关系 算符优先文法的定义算符优先关系表的构造 算符优先分析算法 算符优先分析法的局限性6.3 算符优先方法分析程序模型总控程序算符优先关系表产生式输入串#输出6.3.1 直观算
8、符优先分析法 自下而上分析算法 模型-移进归约 算符优先分析不是规范归约如何确定算符优先关系？人为确定：（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
9、-|E*E|E/E|EE|(E)|i例6.2 GE: EET|TTT*F|FFPFPP(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)。 注意：允许bc,
10、 cb; 不允许 bc, b“（”。结论 : 算符优先文法是无二义的。6.3.3 算符优先关系表的构造首先定义如下两个集合： FIRSTVT(B)=bB b 或 B CbLASTVT(B)=aB a 或 B aC 按如下算法计算出给定文法中任何两个终结符对(a,b)之间的 优先关系：1) =关系 直接看产生式的右部，若出现了 A ab或 A aBb,则a=b2)关系 求出每个非终结符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) P
11、(E) (7) PiFIRSTVT(E)=# FIRSTVT(E)=+,*,(,i FIRSTVT(T)=*,(,i FIRSTVT(F)=,(,i FIRSTVT(P)=(,i LASTVT(E)=# LASTVT(E)=+,*,),i LASTVT(T)=*,),i LASTVT(F)=,),i LASTVT(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)+ T*: 则 LASTVT(T)* P:
12、则 LASTVT(P) E): 则 LASTVT(E)2） 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 句型T+T*F+i 其短语有： T+T*F+i T+T*F T T*F iEET+ET* FTTi最左素短语为：T*FF素短语
13、为：T*F， i句型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的素短语为：T+T, I 最左素短语为T+T (注：T+T不是简单短语，但是素短语）ETT例：有文法GE ： (1) EE+T (2) ET (3) TT*F (4) TF (5) FPF|P (6) P(E) (7) PiFE+ TEETTi分析程序模型总控程序算符优先关系表产生式输入串#输出算符优先分析法 简单，直观，有利于表达式分析，易于 手工实现 比规范归约快 可能导致把错误的句子得到正确的归约
