1、第五章第五章 语法分析 自下而上分析所谓自下而上分析法就是从输入串开始，逐步进行 “归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上 “归约 ”，直到根结。5.1 自下而上分析基本问题我们先讨论自下而上分析的一些基本思想和 基本概念：5.1.1归约自下而上分析的关键问题是寻找 可归约串 。对 “可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。在算符优先分析法中我们用 “最左素短语 ”来刻画 “可归约串 ”，在“规范归约 ”中，则用 “句柄 ”来刻画 “可归约串 ”5.1.2 规范归约简述在这一部分应掌握 短语 和 直接短语 和 句柄 三个重要概念第五章 语法分析
2、 -自下而上分析令 G是一个文法， S是文法的开始符，假定是文法 G的一个句型，如果有：S*A 且 A + 则称 是句型 相对于非终结符 A的 短语 。特别是，如果有A 则称 是句型 相对于规则 A 的 直接短语 ，一个句型的最左直接短语成为该句型的 句柄 。注意：短语的 两 个条件是：S*A 且 A + 例 5.1考虑文法：E T|E+TT F|T*FF i | (E) （ 5.2） 对于句型i*i+i 推导解： EE+TT+TT*F+TF*F+Ti*F+Ti*i+F i*i+i第五章 语法分析 -自下而上分析尽管有 E +i+i 但是 , i+i 并不是该句型的一个短语，因为不存在从 E(
3、文法开始符）到 i*E的推导。但是 ， i, i*i,和 i*i+ i 自身都是句型i*i+i 的短语。而且为为直接短语。例 5。 2 上题文法（ 5。 2）的另一个句型 E+T*F+i 的短语有 E+T*F+i ,E+T*F, T*F,和 i. 其中 T*F和 i为直接短语， T*F为句柄。解：EE+TE+T+TE+T*F+TE+T*F+FE+T*F+i第五章 语法分析 -自下而上分析关于 规范归约 精确的说，假定 是文法 G的一个句子，我们称序列n n-1 n-2, 。 , 0是 的一个规范规约，如果此序列满足：（ 1） n = ;(2） 0 为文法的开始符 ,即 0 =S;（ 3） 对于
4、任何的 i， 0b当且仅当 G中含有形如 P Rb 的产生式， R而 R+a 或 R + aQ;第五章 语法分析 -自下而上分析如果一个文法 G中的任何终结符对 （ a, b ） 至多只满足下述三关系之一：a=b, ab 则称 G是一个 算符优先文法 。 应掌握 算符优先表 的构造方法。通过检查 G的每个产生式的每个候选式，可以找出满足 a=b的终结符对。为了找出所有满足关系 的终结符对，我们需要对 G的每个非终结符 P 构造两个集合 FIRSTVT(P)和 LASTVT(P):FIRSTVT(P)=a | P+a 或 P +Qa,a VT而 Q VN LASTVT(P)=a | P+a 或
5、P + aQ,aVT而 Q VN 有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系 的所有终结符对。例如：假定有个产生式的一个候选式为 aP 那末，对任何 bFISTVT(P),我们有 ab.我们首先讨论构造集合 FIRSTVT(P)的算法。按定义，我们可用下面两条规则来构造集合FIRSTVT(P): 若有产生式 Pa 或 P Qa, 则aFIRSTVT(P) 若 aFIRSTVT(Q)， 且有产生式 P Q则 aFIRSTVT(P)同样我们可以构造 LASTVT(P)的算法。在我们有了每个非终结符 P 的 FISTVT(P)和LASTVT(P)之后我们就能够造文法 G的优先表。
6、其算法如下： FOR 每一条产生式 PX1X2 XnFOR i:=1 TO n-1 DOBEGINIF Xi 和 Xi+1 均为终结符 THEN 置 Xi=Xi+1第五章 语法分析 -自下而上分析IF IaEND至此我们完成了从文法 G构造优先表的算法。第五章 语法分析 -自下而上分析5.2.2 算符优先分析算法为了刻画什么是 “可归约串 ”我们将定义算符优先文法的句型的 “最左素短语 ”这个概念。所谓素短语是指这样的一个短语，它至少含有一个终结符，并且出它自身外，不再含有更小的素短语。所谓最左素短语，是指处于句型最左边的那个素短语。我们把算符优先文法句型（括在两个 #号之间）的一般形式写成：#N1a1N2a2 Nnan Nn+1# （ 5.4）其中每个 ai都是终结符， Ni是可有可无的非终结符。一个算符优先文法 G的任何句型（ 5.4）的最左素短语是满足如下条件的最左子串： Njaj Nia i+1, a j-1a i+1 根据这个最左素短语的定义我们可以构造算符优先分析算法。参考 P93第五章 语法分析 -自下而上分析
