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

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:ba da (有两个相同的右部)v g2:ee+t|t tt*f|f 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是句柄。+ 试用简单优先方法分析符号串b( a

7、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 1）i i的优先级最高的优先级最高（1 1） 优先级次于优先级次于i i，右结合，右结合（2 2）* *和和/ /优先级次之，左结合优先级次之，左结合（3 3）+ +和和- -优先级最低，左结合优先级最低

9、，左结合（4 4）括号）括号(,)(,)的优先级大于的优先级大于括号外的运算符，小于括号内的运括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号算符，内括号的优先性大于外括号（5 5）# #的优先性低于与其相邻的算符的优先性低于与其相邻的算符文法文法ge：ee+e|e-e|e*e|e/e|e e|(e)|i+-*/ ()i#+-*/ (=i#=算符优先关系表算符优先关系表 6.3.2 算符优先文法的定义算符优先文法的定义 定义定义：如果不含空产生式的上下文无关文法：如果不含空产生式的上下文无关文法 g g 中中没有形如没有形如 a abcbc的产生式，其中的产生式，其中b b，cvc

10、vn n 则称则称g g 为算符文法（为算符文法（ogog）。）。例例6.1 ge：ee+e|e-|e*e|e/e|e e|(e)|i例例6.2 ge: eet|t tt*f|f fpfp p(e)|i性质性质1 1：在算符文法中任何句型都不包含两个相邻的非终结符：在算符文法中任何句型都不包含两个相邻的非终结符. .性质性质2 2：如：如 a ab b 或或 b ba a 出现在算符文法的出现在算符文法的 句型句型 中，其中中，其中 avavn n，b bv vt t， 则则 中任何中任何 含含 b b 的短语必含有的短语必含有a a。算符优先关系算符优先关系在在og中中 定义定义 （算符优先

11、关系）（算符优先关系） a = b g中有形如中有形如：aab 或或a abb.的产生式。的产生式。 a b g中有形如中有形如: a bb的产生的产生 式式,而而 b a 或或 b ac 规定规定 若若 s a或或 s ca 则则 # #在在 og文法文法 g 中，若中，若任意两个终结符间至多有任意两个终结符间至多有一种一种算符优先关系存在，则称算符优先关系存在，则称g 为为算符优先文算符优先文法法(opg)。注意：允许注意：允许bc, cb;不允许不允许 bc, bc, b=c中中任两个任两个 同时同时存在。存在。b=c 不一不一定定 c = b。例例6.1中：中：“（” = “）”，“）

12、”“（”。 结论结论 : 算符优先文法是无二义的。算符优先文法是无二义的。6.3.3 算符优先关系表的构造算符优先关系表的构造首先定义如下两个集合：首先定义如下两个集合：firstvt(b)=bb b 或或 b cblastvt(b)=ab a 或或 b ac按如下算法计算出给定文法中任何两个终结符对按如下算法计算出给定文法中任何两个终结符对(a,b)之间的之间的优先关系：优先关系： 1) =关系关系 直接看产生式的右部，若出现了直接看产生式的右部，若出现了a ab或或 a abb,则则a=b 2)关系关系 求出每个非终结符求出每个非终结符b的的firstvt(b) 若若aab,则则 bfir

13、stvt(b),则则a关系关系 求出每个非终结符求出每个非终结符b的的lastvt(b) 若若abb,则则 alastvt(b),则则ab计算算符优先关系计算算符优先关系例例6.3 文法文法ge：(0) e#e#(1) ee+t(2) et(3) tt*f(4) tf(5) fp f|p(6) p(e)(7) pifirstvt(e)=#firstvt(e)=+,*, ,(,ifirstvt(t)=*, ,(,ifirstvt(f)= ,(,ifirstvt(p)=(,ilastvt(e)=#lastvt(e)=+,*, ,),ilastvt(t)=*, ,),ilastvt(f)= ,),i

14、lastvt(p)=),i(0)e#e# (1) ee+t (2) et (3) tt*f (4) tf(5) fp f|p (6) p(e) (7) pi3)关系关系找形如：找形如：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: 则则 ( * ( = i

15、 # = 6.3.4 算符优先分析算法算符优先分析算法 算符优先文法句型的性质算符文法的任何一个句型应为如下形式：n1a1n2a2 . nnan nn+1其中n k(1kn+1)为非终结符或空，ak(1kn)为终结符算符优先文法句型的最左素短语niaini+1ai+1 . njaj nj+1满足：ai-1 aiai =ai+1 = =aj-1 =ajaj aj+1即：即：a ai-1i-1 a aj+1j+1 算符优先分析的算符优先分析的可归约可归约 串串是是句型的句型的最左素短语最左素短语定义定义 cfgcfg（上下文无关文法）（上下文无关文法） g g 的句型的的句型的素短语素短语是一个短

16、语，它是一个短语，它至少包含一个终至少包含一个终结符结符，且除自身外，且除自身外不再包含其他素短语不再包含其他素短语。处于句型最左边的素短语为处于句型最左边的素短语为最左素短语最左素短语文法文法gs短语的定义短语的定义 s a且且a 则称则称是句型是句型相对于相对于非终结符非终结符a的的短语短语 *例：有文法例：有文法ge：(1) ee+t(2) et(3) tt*f(4) tf(5) fp f|p(6) p(e)(7) pi1. 画出句型画出句型t+t*f+i的语法树并写出改句型的所有短语。的语法树并写出改句型的所有短语。2. 写出句型写出句型t+t*f+i的简单短语和句柄。的简单短语和句柄

17、。3.写出句型写出句型t+t*f+i的素短语和最左素短语。的素短语和最左素短语。文法文法ge：(1) ee+t(2) et(3) tt*f(4) tf(5) fp f|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的素短语为的素短语为