语法分析自下而上分析

最左素短语满足以下条件的最左子串 Njaj… NiaiNi+1， aj-1 aj
aj aj+1 , … , ai-1 ai ai ai+1
也即：
aj-1
ai+1
Nj aj … … ai Ni+1
2 例6.5 i1 *( i2 + i3) #
∵# i1 * ( i2 + i3 ) # ∴i1，i2，i3是素短语；i1是最左素短语。
算法分析：
k:=1; S[k]:=‘#’; REPEAT
把下一个输入符号读进a中； IF S[k]∈VT THEN j:=k ELSE j:=k-1; WHILE S[j] a DO
BEGIN REPEAT
Q:=S[j]; IF S[j-1]∈VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] Q 把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N; END OF WHILE;
i2->OPND
三 算符优先分析
1 算符优先文法
①定义一
如果一个文法的任何产生式右部都不含两 个相继（并列）的非终结符，即不含有如下形式 的产生式右部：
…QR… 则我们称该文法为算符文法。
②定义二
假定G是一个不含ε-产生式的算符文法。对于任 何一对终结符a、b，我们说：
a b， 当且仅当文法G中含有形如P->…ab… 或P->…aQb…的产生式；
FIRSTVT(P)的自动构造
过程INSERT：
PROCEDURE INSERT(P,a) IF NOT F[P,a] THEN BEGIN F[P,a] := TRUE； 把(P,a)下推进STACK栈 END;
主程序：
BEGIN FOR 每个非终结符P和终结符a DO F[P,a] := FALSE; FOR 每个形如P->a …或P->Qa…的产生式 DO
⑤这是因为，假定有个产生式候选式：
…aP…，那么对任何 b∈FIRSTVT(P),有a b；
…Pb…，那么对任何 a∈LASTVT(P)，有a b；
因此，问题归结为：
①构造该二个集合的算法，对每一 VN的 FIRSTVT(P) 、LASTVT(P）
②使用每个VN的FIRSTVT(P) 、LASTVT(P），检 查每一个产生式，找出所有（a，b）的关 系，就完成了构造优先关系表。
E（1）θE（2） ；然后重新进入第3步；（其中， E（1） 、E（2）分 别为OPND栈的次栈顶和栈顶）
a
θ ……
#
E （2） E （1）
…
OPTR
OPND
=> E（3）
④若θ a，则
•若θ=‘(’,a=‘)’,则逐出OPTR栈顶的‘(’,放弃a中的‘ )’,
转第
1步;
•若θ=a=‘#’,分析成功结束；
2）存在性：
并非总能把表映射到优先函数。
例6.6 对于下述关系表就不存在优先函数 f 和 g ：
g(x)
a
b
f(x)
a
b
不然，应有：
① f(a) = g(a)
② f(a) > g(b)
③ f(b) = g(a)
④ f(b) = g(b)
那么，f(a)>g(b)=f(b)=g(a)=f(a)，矛盾。
使用优先函数的优缺点： 优：便于比较运算；节省存储空间。 缺：对不存在优先关系的两个终结符，由于与自然数相
对应，变成可比较。
优先函数的性质： 1）正确性：
优先函数掩盖了矩阵中出错元素对，若f(id)<g(id)， 暗示id id，但id之间无优先关系，因此失去发现错误能 力，但并未严重到妨碍在可解地方使用优先函数。
规范归约：是关于句型α的一个最右推导的 逆过程，也称最左归约。
例6.2 文法G
E —＞ T | E +T T —＞ F | T * F F —＞ i |（E）
的一个句型 i1*i2+i3
短语: i1 ,i2 ,i3 , i1*i2 , i1*i2+i3
直接短语: i1 ,i2 ,i3
句柄: i1
3）唯一性： 存在一个优先函数，就有无数多对，加一常数，不等
式也成立。
构造优先函数的方法 （如果优先函数存在的话）
对每个a（包括＃）∈VT，对应两个符号fa，ga。 把所建立的符号尽可能划分为许多组：
若a b，则fa和gb就在一组； 若a b，c b，则fa和fc同组； 建立一个有向图，其结点是上一步中找出的组。 对于任何a和b，若 a b，画 fa→gb 弧，意味着f(a)>g(b)；
（如：（E），则（ ））
a b， 当且仅当G中含有形如P->…aR…的产生 式，而R b… 或 R Qb…；
a b， 当且仅当G中含有形如P->…Rb…的产生 式，而R …a 或 R …aQ。
③定义三 如果一个算符文法G中的任何终结符对（a，b）
至多只满足下述三种关系之一： a b，a b，a b
IF S[j] a OR S[j] a THEN BEGIN k:=k+1;S[k]:=a END
ELSE ERROR
UNTIL a=‘#’
7 优先函数
定义： 我们把每个终结符θ与两个自然数f(θ) 和g(θ)相对
应，使得：
若θ1 θ2，则f(θ1)<g(θ2) 若θ1 θ2，则f(θ1)=g(θ2) 若θ1 θ2，则f(θ1)>g(θ2) 函数 f 称为入栈优先函数，g 称为比较优先函数。
2 、自下而上分析法的基本思想：
自左向右逐个扫描输入串，一边把输入符号移入分 析栈内，一边检查位于栈顶部的一串符号是否与某个产生 式的右部相同。
若相同，则执行“归约”； 若不相同，就继续向栈内移进输入符号，并继续进行 判断。 分析成功：上述过程一直重复到输入串结束，而栈内恰好 为给定文法的开始符号为止。
主程序：
BEGIN FOR 每个非终结符P和终结符a DO L[P,a] := FALSE; FOR 每个形如P-> … a 或P-> … aQ的产生式 DO
INSERT(P,a); WHILE STACK 非空 DO
BEGIN 把STACK的顶项，记为(Q,a)，弹出去 FOR 每条形如P-> … Q的产生式 DO INSERT(P,a)
E
E
+
T
T
F
T*F
ii3
F
ii
2
ii1
语法树
3 符号栈的使用
规范归约用来作语法分析需要解决的问题： ①如何在句型中找出句柄? ②在相同的右部有不止一个产生式时,选哪一个?
①实现移进-归约分析的一个方便途径是用一个栈和一个输 入缓冲区,用#表示栈底和输入的结束
栈
输入
#
w#
② 分析程序的动作
移进: 下一输入符号移进栈顶 归约: 把句柄按产生式的右部进行归约 接收: 分析程序报告成功 出错: 发现了一个语法错,调用出错处理程序
3 构造集合FIRSTVT(P)的算法
① P->a…或P->Qa…,则a∈FIRSTVT(P)； ②若a∈FIRSTVT(Q),且有产生式P->Q…，则 a∈FIRSTVT(P)
4 构造集合LASTSTVT(P)的算法
① P->…a 或 P->…aQ,则a∈LASTVT(P)； ②若a∈LASTVT(Q),且有产生式P->…Q，则 a∈LASTVT(P)
第六、七章 语法分析——自下而上分析
本章内容 自下而上分析基本问题 直观算符优先分析法 算符优先分析 LR分析法
自下而上分析法 从输入串开始，逐步进行“归约”，直至
归约到文法的开始符号；
一、自下而上分析基本问题
1 、归约 利用栈，输入符号移进栈，当栈顶形成P的
候选式时，就归约为它的左P符号
5 构造优先表方法
① 对形如 P->…ab…和形如P->…aQb…，有a b； ②对形如 P->…aR…，而b∈FIRSTVT(R)，有a b； ③对形如 P->…Rb…，而a∈LASTVT(R)，有a b； ④对文法开始符号S，有# FIRSTVT(S)，LASTVT(S) #，
且对 #S#，有# #。
⑤若θ a，a—>OPTR栈，转第1步；
⑥θ与a不存在优先关系，则输入串错误，调出错处理
成功！
#)
a
θ
(
……
#
E （2） E （1）
…
OPTR
OPND
2 例6.4 由文法G: E —> E + E | E * E | E↑E | ( E ) | i
的终结符的优先关系表及上述分析算法
分析算术表达式 i1 + i2 * i3 # 的过程。
注意: 可归约的串在栈顶,不会在内部
二 直观算符优先分析法
1 定义:
任二个相继出现的终结符a与b(可能中间有VN),可能有以 下优先关系:
ab
a的优先性低于b
ab
a的优先性等于b
ab
a的优先性高于b
2 例6.3 文法G:
E —> E + E | E * E | E↑E | ( E ) | i 的终结符的优先关系见下表。
E—> E+E | E*E | E↑E |( E )| i
优先表
+* ↑
i（
）#
+ * ↑ i （
）
#
3 使用如上分析表，构造分析算法（直观算符 优先分析法）
记号使用说明： #：语句括号（栈底 w后）
θ：现行栈顶符 a：刚读入字符 OPTR：运算符栈 OPND：操作符栈