编译原理第6章 自底向上优先分析法 自底向上优先分析概述 简单优先分析 算符优先分析返回目录编译原理自底向上分析方法 自底向上分析方法，也称移进移进- -归约归约分析法。 实现思想： 对输入符号串自左向右进行扫描，并 将输入符逐个移入一个后进先出栈中将输入符逐个移入一个后进先出栈中，边 移入边分析，一旦栈顶符号串形成某个句一旦栈顶符号串形成某个句 型的句柄时，型的句柄时，（该句型对应某产生式的右 部），就用就用该产生式的左部左部非终结符代替代替 相应右部的文法符号串，这称为归约归约。 重复这一过程直到归约到栈中只剩文重复这一过程直到归约到栈中只剩文 法的开始符号时则为分析成功法的开始符号时则为分析成功，也就确认 输入串是文法的句子。S10） #aAcBe # 归约 (SaAcBe)文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B da b b c de步骤符号栈输入符号串动作1） # abbcde# 移进2） #a bbcde# 移进A3） #ab bcde# 归约(Ab)4） #aA bcde# 移进A5） #aAb cde# 归约(AAb)6） #aA cde# 移进7） #aAc de# 移进B8） # aAcd e# 归约(Bd)9） #aAcB e# 移进11） #S # 接受分析符号串abbcde是否为GS的句子 ？对输入串abbcde#的移进-规约分析过程SaAcBe aAcde aAbcde abbcde编译原理算法应考虑的问题 算法是否能够终止？ 算法是否快速？ 算法是否能够处理所有的情况？ 在每一步中如何选择子串进行归约？编译原理自下而上语法分析的策略：移进-规约分析 。移进就是将一个终结符推进栈。归约就是将0个或多个符号从栈中弹出，根 据产生式将一个非终结符压入栈。移进-归约过程是自顶向下最右推导的逆过 程（规范归约）。编译原理 简单优先分析法对一个文法按一定原则求出该文 法所有符号（终结符和非终结符）之间的 优先关系，按照这种关系确定归约过程中 的句柄，它的归约实际上是一种规范归约 。 算符优先分析法只规定算符（终结符）之间的优 先关系。找到句柄就归约，不是规范归约 。优先分析法编译原理简单优先分析法 按照文法符号（包括终结符和非终结符 ） 的优先关系确定句柄。编译原理文法GS： (1) S bAb (2) A (B|a (3) B Aa)步骤符号栈输入符号串动作1） # b(aa)b# #a,归约Aa5） #b(A a)b# A=a,移进6） #b(Aa )b# a=),移进7） #b(Aa) b# )b,归约BAa)8） #b(B b# Bb,归约A(B9） #bA b# A=b,移进 10） #bAb # b#,归约SbAb11） #S # 接受对输入串b(aa)#的简单优先分析过程简单优先关系矩阵编译原理优先关系优先关系 1) X=Y 文法G中存在产生式A.XY. 2) XY 文法G中存在产生式A.BD.， 且B .X,D Y.如何确定两个文法符号之间的优先关系？返回调用编译原理简单优先文法的定义满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最 多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右 部。（3）不含空产生式。编译原理 简单优先分析法 根据已知优先文法构造相应优先关系矩阵，并将 文法的产生式保存，设置符号栈S，算法步骤如下 ： 将输入符号串a1a2a3.an#依次逐个存入符号栈S 中，直到遇到栈顶符号ai的优先性下一个待输入 符号aj时为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找句 柄的头符号ak，即找到ak-1关系： 由(1)：Bb ab )b 由(3)：Ba aa )a4.# 查看关系定义编译原理算符优先分析法 某些文法具有“算符”特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给 出优先级别和同一级别的结合性 只考虑算符之间的优先关系来确定句柄编译原理文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i步骤符号栈输入符号串动作1） # i+i*i# #+,规约3） #E +i*i# #*,规约6） #E+E *i# +#,规约9） #E+E*E # +#,规约 10） #E+E # #,规约11） #E # 接受对输入串i+i*i的算符优先分析过程算符优先关系表编译原理如何确定算符优先关系？1) i的优先级最高 2) 优先级次于i，右结合 3) *和/优先级次之，左结合 4) +和-优先级最低，左结合 5) 括号(,)的优先级大于括号 外的运算符，小于括号内的运算符 ，内括号的优先性大于外括号 6) #的优先性低于与其相邻的算符文法GE：EE+E|E-E|E*E|E/E|EE|(E)|i算符优先关系表编译原理算符文法的定义 定义 如果不含空产生式的上下文无关文法 G 中没有形如 UVW的产生式，其中 V,WVN则称G 为算符文法（OG）。性质1：在算符文法中任何句型都不包含两个 相邻的非终结符.(数学归纳法)性质2：如 Vx 或 xV 出现在算符文法的句型 中，其中VVN,xVT, 则 中任何含 x 的短语必含有V.（反证法）编译原理 算符优先关系的定义 在OG中 定义 （算符优先关系） x = y G中有形如.Uxy或U xVy的产 生式。 x y G中有形如.U Wy的产生式,而 W x或W xV 规定 若 S x或S Vx 则 # #编译原理算符优先文法的定义 在 OG文法 G 中，若任意两个终结符间至多 有一种算符优先关系存在，则称G 为算符优 先文法(OPG)。 注意：允许bc,cb;不允许 bc,b关系 求出每个非终结符B的LASTVT(B)，若ABb,则aLASTVT(B),则ab 。编译原理文法GE： (0) E#E# (1) EE+T (2) ET (3) TT*F (4) TF (5) FPF|P (6) P(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)=),i1)=关系 由产生式(0)和(6),得 #=#，（=） 2）关系 找形如：ABb的产生式 E# ,则 LASTVT(E)# E+ ,则 LASTVT(E)+ T* ,则 LASTVT(T)* P ,则 LASTVT(P) E) ,则 LASTVT(E)编译原理算符优先分析算法 归约过程中，只考虑终结符之间的优先 关系来确定句柄，而与非终结符无关。 这样去掉了单非终结符的归约，所以用 算符优先分析法的规约过程与规范归约 是不同的，P110. 为解决在算符优先分析过程中如何寻找 句柄，引进最左素短语的概念。编译原理 最左素短语 算符文法的任一句型有如下形式： #N1a1N2a2NnanNn+1#,若NiaiNjajNj+1为句 柄，则有 ai-1 ai+1 对于算符优先文法，如果aNb(或ab)出现在句型r中 若ab，则在r中必含有a而不含b的短语存在 。 若a=b，则在r中含有a的短语必含有b，反之 亦然。 定义 cfg G 的句型的素短语是一个短语，它至 少包含一个终结符，且除自身外不再包含其他素短 语。处于句型最左边的素短语为最左素短语。编译原理文法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+ETF* FTTi最左素短语为：T*F句型#N+N*N+i#的归约过程 NN+NNi* NNN编译原理优先函数 优先函数比优先矩阵节省空间 当发生错误时不能准确指出出错位置 如：i+ii*i#，两个相邻i不存在优先关 系，但优先函数存在，会归约成N+NN.而 发现错误。 优先函数的构造 由定义直接构造 用关系图构造优先函数编译原理算符优先分析法的局限性 一般语言的方法很难满足算符优先文法的 条件。 很难避免把错误的句子得到正确的归约。