第五章 语法分析——自下而上分析
5.1自下而上分析基本问题
一、移进-归约法
这种方法的大致意思是：用一个寄存符号的先进先出后进栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选
式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。
例如：设文法G(S)：
(1) S —> aAcBe
(2) A —> b
(3) A —> Ab
(4) B —> d
分析：首先让a进栈，然后把b进栈，根据第二条规则，把b归约成A，再让第二个b进栈，此时栈顶有Ab，根据第三条规则，将
Ab归约成A，让c进栈，d进栈，根据第四条规则，将d归约成B，最后让e进栈，此时栈里的符号为aAcBe，最后根据第一条规则
将其归约为S。
二、规范归约
定义:令G是一个文法，S是文法的开始符号，假定αβ△是文法G的一个句型
其中α,β,△∈(VN∪VT)*，A∈VN ，如果有
则称β是句型αβ△相对于非终结符A的短语。
特别是，如果有A=>β则称β是句型αβ△相对于规则A—>β的直接短语，一个句型的最左直接短语称为该句型的句柄。
注：因为句型是由开始符号推出来的，而短语是由非终结符号推出来的。所以，短语是句型的一部份或全部符号串。
考虑文法
G ： E —> T | E+T
T—> F | T*F
F—> (E) | i
求证i1*i2+i3是G的一个句型，并找出该句型的全部短语、直接短语和句柄。
分析：证明i1*i2+i3是G的一个句型
E => E+T=> T+T => T*F+T => F*F+T
=> i1*F+T => i1*i2+T=> i1*i2+F
=> i1*i2+i3找i1*i2+i3的所有短语
(1)假设i1*i2+i3是一个短语
因为 E =>*E 且 E =>+i1*i2+i3
所以i1*i2+i3是句型i1*i2+i3关于E的一个短语(2)假设i1*i2是一个短语
因为 E =>*T+i3 且 T =>+i1*i2
所以i1*i2是句型i1*i2+i3关于T的一个短语(3)假设i1是一个短语
因为 E =>*F*i2+i3 且 F =>+ i1
所以i1是句型i1*i2+i3关于F的一个短语(4)假设i2是一个短语
因为 E=>*i1*F+i3 且 F=>+i2
所以i2是句型i1*i2+i3关于F的一个短语
(5)假设i3是一个短语
因为 E=>*i1*i2+F且 F=>+i3
所以i3是句型i1*i2+i3关于F的一个短语(6)假设i2+i3是一个短语
因为 E=>*i1*E不成立， 且 E=>+i2+i3成立
所以i2+i3不是句型i1*i2+i3的一个短语注：
缺一不可
所以短语有：i1*i2+i3， i1*i2， i1，i2，i3
找直接短语：
根据定义，如果有A=>β,则称β是句型αβ△相对于规则A—>β的直接短语
因为有：F —> i
所以i1、i2、i3是直接短语
找句柄：
根据定义，一个句型的最左直接短语称为该句型的句柄。
i1是句型i1*i2+i3的句柄
规范归约定义：假定α是文法G的一个句子，我们称序列 αn， αn-1，… ，α0 是α的一个规范归约，如果此序列满足：
(1) αn=α
(2) α0为文法的开始符号，即α0=S
(3) 对任何i，0 < i <=n， αi-1是从αi经把句柄替换成为相应产生式左部符号而得到的。
容易看到，规范归约是关于α的一个最右推导的逆过程。因此，规范归约也称最左归约。
例：设文法G(S)：
(1) S —> aAcBe
(2) A —> b
(3) A —> Ab
(4) B —> d
求句子abbcde的规范归约abbcdeE=> aAbcde E=>aAcde E=> aAcBeE=> S
把上例倒过来写，则得到：
S => aAcBe=> aAcde => aAbcde =>abbcde
注：
1.在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。如果文法G是无二义的，那么，规范推
导的逆过程必是规范规约（最左归约）。
2.由于规范句型由最右推导推出的句型，故该句型的句柄右边只含有终结符号
修剪语法树
(1)子树：是由该树的某个结点(子树的根)连同它的所有子孙组成。
(2)简单子树：只有单层分支的子树(只有父子两代没有第三代)
(3) 对语法树有如下结论：
①每个句型都有一棵语法树与之对应
②每棵语法树的叶结点自左至右排列就组成一个句型
③每棵子树的叶结点自左至右排列就组成一个短语
④每棵简单子树的叶结点自左至右排列就组成一个直接短语
⑤每棵最左简单子树的叶结点自左至右排列就组成一个句柄
例如，句子abbcde的语法树为：
它最左边的两代子树是用虚线勾出的部分。这棵子树是端末结b就是句型abbcde的句柄。若把这棵子树的端末结都剪去（归
约），就得到句型aAbcde的语法树
它的最左两代子树是虚线勾出的部分。这棵子树的端末结A与b（连成Ab）构成句型aAbcde句柄。若把这棵子树的端末结都剪
去，就得到句型aAcde的语法树
照此办理，当剪到只剩下根结时，就完成了整个归约过程。
三、用符号栈进行自下而上的语法分析
栈是语法分析的一种基本数据结构。
1.’#’的使用
(1)在分析开始时，将’#’预先进栈，作为栈底符号
(2)将’#’作为输入串的结束符
即分析开始时的格局为
2.分析过程
自左向右对输入串ω不断向栈中进行移进——归约，直到形成如下格局
表示分析成功，否则意味着输入串ω有错。
5.2算符优先分析
1.算符优先分析法思路：定义算符之间优先关系，借助这种关系来寻找“可归约串”和进行归约
2.定义两个终结符‘a’与‘b’的优先关系
a =.b 表示a的优先性等于b
a >.b 表示a的优先性大于b
a <.b 表示a的优先性小于b
注意：=. >. <. 不同于数学上的 = < >
a =.b 不一定对应着 b =. a
a >.b 不一定对应着 b <. a
a <.b 不一定对应着 b >. a
算符优先文法及优先表构造
1.一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：
…QR…则我们称该文法为算符文法，也称OG文法 。
2.定义终结符之间的优先关系
假定G是一个不含ε产生式的算符文法。对于任何一对终结符a、b，我们说：
1） a =. b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
2）a <. b 当且仅当G中含有形如P→…aR…的产生式， 而R=>b…或R =>Qb…；
3 ) a>.b 当且仅当G中含有形如P→…Rb…的产生式，而 R=> …a或R=> …aQ。
3.如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：
a=.b
a>.b
a<.b
则称G是一个算符优先文法(OPG文法)。
构造算符优先关系表
(1)通过检查产生式的每一个候选式可以找出满足a=.b
（即P→…ab…或P→…aQb…的产生式）
(2)为了满足<.和>.，需对G中每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：
(3)构造集合FIRSTVT(P)的算法
按其定义，可用下面两条规则来构造集合FIRSTVT(P)：① 若有产生式P→a…或P→Qa…，
则aFIRSTVT(P)；② 若aFIRSTVT(Q)，且有产生式P→Q…，
则aFIRSTVT(P)。
(4)同理构造构造集合LASTVT(P)的算法
按其定义，可用下面两条规则来构造集合LASTVT(P)：① 若有产生式P→… a或P→… aQ ，
则a LASTVT(P)；② 若a LASTVT(Q)，且有产生式P→… Q ，
则a LASTVT(P)。
(5)有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系<.和>.的所有终结符对。
(1)假定有个产生式的一个候选形为…aP…
那么，对任何b ∈FIRSTVT(P)，有a <. b。
(2)假定有个产生式的一个候选形为…Pb…
那么，对任何a∈LASTVT(P)，有a >. b。
算符优先分析算法的设计
1.问题的提出
自下而上分析
移进-归约法：句柄为可归纳串
算符优先分析法：最左素短语为可归纳串
2.素短语
指一个句型的短语，它至少包括有一个终结符号且除去它本身之外不再含任何更小的素短语
3.最左素短语
处在句型最左端那个素短语成为最左素短语
4.算符优先分析算法和设计
(1)句型的一般表示形式：
#N1a1N2a2…NnanNn+1#
其中，每个ai都是终结符，Ni是可有可无的非终结符
(2)定理：
一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串 Njaj…NiaiNi+1，
aj-1 <. aj
aj =. aj+1，aj+1 =. aj+2，…，ai-1 =. ai
ai >. ai+1
注：出现在左端或右端的非终结符一定属于这个素短语
优先函数
1.优先函数的定义：把每个终结符与两个自然数f(θ)与g(θ)相对应，使得
若θ1 <. θ2，则f(θ1) < g(θ2)
若θ1 =. θ2，则f(θ1) = g(θ2)
若θ1 >. θ2，则f(θ1) > g(θ2)
f称为入栈优先函数，g称为比较优先函数。
(1)优点:便于比较，节省空间；
(2)缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。
2.优先函数的构造方法
如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:
(1)对于每个终结符a，令其对应两个符号fa和ga，画一张以所有符号fa和ga为结点的方向图。如果a>.b，则从fa画一条弧至gb如
果a<.b，则从gb画一条弧至fa 。
(2)对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)赋给ga的数作为
g(a)。
(3)检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函
数。
3.构造方法证明
现在必须证明：
若a=.b，则f(a)＝g(b)；若a<.b，则f(a)< g(b)；若a>.b，则f(a)> g(b)。
第一个关系可从函数的构造直接获得。因为，若a=.b，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结
是全同的。
至于a<.b和a>.b的情形，只须证明其一。
如果a>.b，则有从fa到gb的弧。也就是gb能到达的任何结fa也能到达。因此，f(a) g(b)。所需证明的是，在这种情况下，
f(a)=g(b)不应成立。
我们将指出，如果f(a)=g(b)，则根本不存在优先函数。假若f(a)=g(b)，那么必有如下的回路：
因此有
a>.b, a1<.=.b, a1>.=.b1, …, am>.=.bm, a<.=.bm
对任何优先函数f’和g’来说，必定有f’(a)> g’(b) f’(a1) g’(b1) … f’(am) g’(bm) f’(a)
从而导致f’(a)> f’(a)，产生矛盾。因此，不存在优先函数f和g。