第6章自底向上优先分析法

1、编译原理编译原理编译原理编译原理编译原理编译原理第第6 6章章 自底向上优先分析法自底向上优先分析法 自底向上优先分析概述 简单优先分析 算符优先分析返回目录编译原理编译原理编译原理编译原理编译原理编译原理自底向上分析方法自底向上分析方法自底向上分析方法，也称分析法。实现思想：对输入符号串自左向右进行扫描，并，边移入边分析，（该句型对应某产生式的右部），该产生式的非终结符相应右部的文法符号串，这称为。，也就确认输入串是文法的句子。s10） #aacbe # 归约归约(saacbe)文法文法gs：(1) s aacbe(2) a b(3) a ab(4) b da b b c de步骤步骤符号栈

2、符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进a 3） #ab bcde# 归约归约(ab) 4） #aa bcde# 移进移进a 5） #aab cde# 归约归约(aab) 6） #aa cde# 移进移进 7） #aac de# 移进移进b 8） # aacd e# 归约归约(bd) 9） #aacb e# 移进移进11） #s # 接受接受分析符号串分析符号串abbcdeabbcde是否为是否为gsgs的句子？的句子？对输入串abbcde#的移进-规约分析过程saacbe aacde aabcde abbcde编译原理编译原理

3、编译原理编译原理编译原理编译原理算法应考虑的问题算法应考虑的问题 算法是否能够终止？算法是否能够终止？ 算法是否快速？算法是否快速？ 算法是否能够处理所有的情况？算法是否能够处理所有的情况？ 在每一步中如何选择子串进行归约？在每一步中如何选择子串进行归约？编译原理编译原理编译原理编译原理编译原理编译原理自下而上语法分析的策略：移进自下而上语法分析的策略：移进- -规约分析。规约分析。移进移进就是将一个终结符推进栈。就是将一个终结符推进栈。归约归约就是将就是将0 0个或多个符号从栈中弹出，根个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈。据产生式将一个非终结符压入栈。移进移进- -归约过

4、程是自顶向下最右推导的逆过归约过程是自顶向下最右推导的逆过程（规范归约）。程（规范归约）。编译原理编译原理编译原理编译原理编译原理编译原理 简单优先分析法 对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。 算符优先分析法 只规定算符（终结符）之间的优先关系。找到句柄就归约，不是规范归约。优先分析法优先分析法编译原理编译原理编译原理编译原理编译原理编译原理简单优先分析法简单优先分析法按照文法符号（包括终结符和非终结符） 的优先关系确定句柄。编译原理编译原理编译原理编译原理编译原理编译原理文法文法gsgs：(

5、1) s bab(1) s bab(2) a (b|a(2) a (b|a(3) b aa)(3) b aa)sba(ba)#sb=a=(=a=)#步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # b(aa)b# #b,移进移进 2） #b (aa)b# b(,移进移进 3） #b( aa)b# (a,归约归约aa 5） #b(a a)b# a=a,移进移进 6） #b(aa )b# a=),移进移进 7） #b(aa) b# )b,归约归约baa) 8） #b(b b# bb,归约归约a(b 9） #ba b# a=b,移进移进10） #bab # b#,归约归约sbab11） #

6、s # 接受接受对输入串b(aa)#的简单优先分析过程简单优先关系矩阵编译原理编译原理编译原理编译原理编译原理编译原理优先关系优先关系优先关系优先关系1) x=y 文法文法g中存在产生式中存在产生式a.xy.2) xy 文法文法g中存在产生式中存在产生式a.bd.，且且b .x,d y.如何确定两个文法符号之间的优先关系？如何确定两个文法符号之间的优先关系？*返回调用编译原理编译原理编译原理编译原理编译原理编译原理简单优先文法的定义简单优先文法的定义 满足以下条件的文法是简单优先文法（1）在文法符号集v中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部。（

7、3）不含空产生式。编译原理编译原理编译原理编译原理编译原理编译原理简单优先分析法简单优先分析法根据已知优先文法构造相应优先关系矩阵，并将文法的产生式保存，设置符号栈s，算法步骤如下：1. 将输入符号串a1a2a3.an#依次逐个存入符号栈s中，直到遇到栈顶符号ai的优先性下一个待输入符号aj时为止。2. 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1ak为止。3. 由句柄ak.ai在文法的产生式中查找右部为ak.ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。4. 重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符

8、号为止。编译原理编译原理编译原理编译原理编译原理编译原理如何确定优先关系？如何确定优先关系？文法文法gs：(1) s bab(2) a (b|a(3) b aa)1.求求=关系：关系：由由(1)：b=a a=b由由(2)：(=b由由(3)：a=a a=)2.求求关系：关系：由由(1)(2)：b( ba由由(2)(3)：(a ( (关系：关系：由由(1)：bb ab )b由由(3)：ba aa )a4.#查看关系定义sba(ba)#sb=a=(=a=)#编译原理编译原理编译原理编译原理编译原理编译原理算符优先分析法算符优先分析法某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算

9、符的优先顺序，即给出优先级别和同一级别的结合性只考虑算符之间的优先关系来确定句柄编译原理编译原理编译原理编译原理编译原理编译原理文法文法ge：ee+e|e-e|e*e|e/e|e e|(e)|i步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # i+i*i# #i,移进移进 2） #i +i*i# #+,规约规约 3） #e +i*i# #+,移进移进 4） #e+ i*i# +i,移进移进 5） #e+i *i# +*,规约规约 6） #e+e *i# +*,移进移进 7） #e+e* i# *i,移进移进 8） #e+e*i # *#,规约规约 9） #e+e*e # +#,规约规

10、约10） #e+e # #,规约规约11） #e # 接受接受对输入串对输入串i+ii+i* *i i的算符优先分析过程的算符优先分析过程+ - * / ()i #+ -* / (= i# -*/ (=i# =算符优先关系表算符优先关系表编译原理编译原理编译原理编译原理编译原理编译原理算符文法的定义算符文法的定义定义定义 如果不含空产生式的上下文无关文法如果不含空产生式的上下文无关文法 g g 中没有形如中没有形如 u uvwvw的产生式，其中的产生式，其中v,wvv,wvn n则称则称g g 为算符文法（为算符文法（ogog）。）。性质性质1 1：在算符文法中任何句型都不包含两个在算符文法中

11、任何句型都不包含两个相邻的非终结符相邻的非终结符.(.(数学归纳法数学归纳法) )性质性质2 2：如如 vx vx 或或 xv xv 出现在算符文法的句型出现在算符文法的句型 中，其中中，其中vvvvn n,xv,xvt t, , 则则 中任何含中任何含 x x 的短语必含有的短语必含有v.v.（反证法）（反证法）编译原理编译原理编译原理编译原理编译原理编译原理算符优先关系的定义算符优先关系的定义在在ogog中中 定义定义 （算符优先关系）（算符优先关系）1)1) x x = = y g y g中有形如中有形如.u.uxyxy或或u u xvy.xvy.的产的产生式。生式。2)2) x x y

12、 gy g中有形如中有形如.u .u wywy的产生式的产生式, ,而而 w w x x或或w w xv xv规定规定 若若 s xs x或或s vxs vx 则则 # x# #x #编译原理编译原理编译原理编译原理编译原理编译原理算符优先文法的定义算符优先文法的定义在 og文法 g 中，若任意两个终结符间至多有一种算符优先关系存在，则称g 为算符优先文法(opg)。 注意注意：允许bc,cb;不允许bc,bc,b=c 结论： 算符优先文法是无二义的。编译原理编译原理编译原理编译原理编译原理编译原理算符优先关系表的构造算符优先关系表的构造由定义直接构造由定义直接构造由关系图法构造算符优先关系表

13、由关系图法构造算符优先关系表编译原理编译原理编译原理编译原理编译原理编译原理首先引入两个概念首先引入两个概念firstvt(b)=b|b bfirstvt(b)=b|b b或或b cb.b cb.对于非终结符对于非终结符b b，其往下推导所可能出现的，其往下推导所可能出现的首个算符。首个算符。lastvt(b)=a|b lastvt(b)=a|b a a或或b . acb . ac对于非终结符对于非终结符b b，其往下推导所可能出现的，其往下推导所可能出现的最后一个算符。最后一个算符。编译原理编译原理编译原理编译原理编译原理编译原理如何计算算符优先关系如何计算算符优先关系1) =关系关系直接看

14、产生式的右部，若出现了直接看产生式的右部，若出现了a ab或或a abb,则则a=b。2)关系关系求出每个非终结符求出每个非终结符b的的firstvt(b)， 若若aab,则则 bfirstvt(b),则则a关系关系求出每个非终结符求出每个非终结符b的的lastvt(b)， 若若abb,则则 alastvt(b),则则ab。编译原理编译原理编译原理编译原理编译原理编译原理文法文法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)=*,

15、,(,ifirstvt(f)= ,(,ifirstvt(p)=(,ilastvt(e)=#lastvt(e)=+,*, ,),ilastvt(t)=*, ,),ilastvt(f)= ,),ilastvt(p)=),i+-*/ ()i#+-*/ (=i#=1)=关系关系由产生式由产生式(0)和和(6),得得#=#，（，（=）2）关系关系找形如：找形如：aab的产生式的产生式#e：则：则#firstvt(e)+t: 则则+firstvt(t) *f: 则则*firstvt(f) f:则则 firstvt(f)(e: 则则 (关系关系找形如：找形如：abb的产生式的产生式e# ,则则 lastvt

16、(e)#e+ ,则则 lastvt(e)+ t* ,则则 lastvt(t)* p ,则则 lastvt(p) e) ,则则 lastvt(e)编译原理编译原理编译原理编译原理编译原理编译原理算符优先分析算法算符优先分析算法归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的规约过程与规范归约是不同的，p110.为解决在算符优先分析过程中如何寻找句柄，引进最左素短语最左素短语的概念。编译原理编译原理编译原理编译原理编译原理编译原理最左素短语最左素短语算符文法的任一句型有如下形式：#n1a1n2a2.nnannn+1#,若niai

17、.njajnj+1为句柄，则有 ai-1 ai+1对于算符优先文法，如果anb(或ab)出现在句型r中若ab，则在r中必含有a而不含b的短语存在。若a=b，则在r中含有a的短语必含有b，反之亦然。定义 cfg g 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。编译原理编译原理编译原理编译原理编译原理编译原理文法文法gege：(1) ee+t(1) ee+t(2) et(2) et(3) tt(3) tt* *f f(4) tf(4) tf(5) fp(5) fp f|pf|p(6) p(6) p(e)(e)(7) pi(7) pi句型句型#t+t*f+i#其短语有：其短语有：t+t*f+it+t*ftt*fieet