2.5.1.1 归约 (Reduce)
自下而上 (Bottom-Up)分析采用,移进－归约,(shift-reduce)的 基本思想
把输入符号逐个移进到一个符号栈,当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成
(归约 为 )该产生式的左部符号。
2.5 语法分析 ——自下而上分析例：设文法 G(S)：
(1) S? aAcBe
(2) A? b
(3) A? Ab
(4) B? d
试对 abbcde进行,移进－归约,分析。
a
bbcde
b
bcde
A
b cdec de
d eabbcde
e
B
S
c
a
e
步骤,1 2 3 4 5 6 7 8 9 10
动作,进 a 进 b 归 (2 ) 进 b 归 (3 ) 进 c 进 d 归 (4 ) 进 e 归 (1 )
e
d B B
b c c c c
b A A A A A A A
a a a a a a a a a S
b
db
a c e
S
A B
A
自下而上分析过程：边输入单词符号，边归约。
核心问题：识别可归约串
2.5.1.2 规范归约定义：令 G是一个文法,S是文法的开始符号，假定是文法 G的一个句型，如果有且
AS *A
则?称是句型相对于非终结符 A的 短语 。
特别是，如果有 A,则称?是句型相对于规则 A的 直接短语 。一个句型的最左直接短语称为该句型的 句柄 。
考虑文法 G(E),E? T | E+T
T? F | T*F
F? (E) | i
和句型 i1*i2+i3：
E? E+T? E+F? E+i3? T+i3
T*F+i3? T*i2+i3? F*i2+i3
i1*i2+i3
问题：对于句型 i1*i2+i3而言，有哪些短语、
直接短语和句柄？
因为
E *? F*i2+i3? i1*i2+i3,所以 i1是句型相对于非终结符 F
的短语和直接短语。
E*?i1*F+i3? i1*i2+i3,所以 i2是句型相对于非终结符 F的短语和直接短语。
E*?i1*i2+F?i1*i2+i3,所以 i3是句型相对于非终结符 F的短语和直接短语。
E*?E+i3 +? i1*i2+i3,所以 i1*i2是句型相对于非终结符 E
的短语。
E *? E? i1*i2+i3,所以 i1*i2+i3是句型相对于非终结符 E
的短语。
结论：对于句型 i1*i2+i3而言：
短语,i1,i2,i3,i1*i2,i1*i2+i3
直接短语,i1,i2,i3
句柄,i1
在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。 而最左直接短语就是句柄。
E
F
F
T
T
T
i1
+
*
E
F
i3
i2
根据语法树找短语、直接短语、句柄可用句柄来对句子进行归约句型 归约规则
abbcde (2) A? b
aAbcde (3) A? Ab
aAcde (4) B? d
aAcBe (1) S? aAcBe
S
定义：假定?是文法 G的一个句子，我们称序列
n,?n-1,?,?0
是一个 规范归约,如果此序列满足：
1?n=?
2?0为文法的开始符号，即?0=S
3 对任何 i,0? i? n,?i-1是从?i经把句柄替换成为相应产生式左部符号而得到的。
把上例倒过来写，则得到：
S? aAcBe? aAcde? aAbcde? abbcde
显然这是一个最右推导。
规范归约是一个最右推导的逆过程。
最左归约 规范推导由规范推导推出的句型称为 规范句型 。
b
db
a c e
S
A B
A d
b
a c e
S
A B
A
d
a c e
S
A B a c e
S
A B
利用语法树寻找句柄
2.5.1.3符号栈的使用和分析树的表示栈是语法分析的一种基本数据结构。 ’ #?作为栈底符号考虑文法 G(E)：
E? T | E+T
T? F | T*F
F? (E) | i
输入串为 i1*i2+i3,分析步骤为：
步骤 符号栈 输入串 动作
0 # i1*i2+i3# 预备
1 #i1 *i2+i3# 进
2 #F *i2+i3# 归，用 F→i
3 #T *i2+i3# 归，用 T→F
4 #T* i2+i3# 进
5 #T*i2 +i3# 进
6 #T*F +i3# 归，用 F→i
7 #T +i3# 归，用 T→T*F
步骤 符号栈 输入串 动作
8 #E +i3# 归，用 E→T
9 #E+ i3# 进
10 #E+i3 # 进
11 #E+F # 归，用 F→i
12 #E+T # 归，用 T→F
13 #E # 归，用 E→E+T
14 #E # 接受
2.5.2 算符优先分析四则运算的优先规则：
先乘除后加减，同级从左到右考虑二义文法文法 G(E)：
G(E),E? i| E+E|E-E|E*E|E/E|(E)
它的句子有几种 不同的规范规约 。
例如：句子 i+i-i*(i+i)
E
i
( )
i
*
E
i
E E
+
E
EE
-
i i
+
E
EE
句子 i+i-i*(i+i)的归约过程是：
(1) i+i-i*(i+i)
(2) E+i-i*(i+i)
(3) E+E-i*(i+i)
(4) E-i*(i+i)
(5) E-E*(i+i)
(6) E-E*(E+i)
(7) E-E*(E+E)
(8) E-E*(E)
(9) E-E*E
(10) E-E
(11) E
E
i
( )
i
*
E
i
E
E
+
E
EE
-
i
i+
E
E
E
返回句子 i+i-i*(i+i)的归约过程是：
(1) i+i-i*(i+i)
(2) E+i-i*(i+i)
(3) E+E-i*(i+i)
(4) E-i*(i+i)
(5) E-E*(i+i)
(6) E*(i+i)
(7) E*(E+i)
(8) E*(E＋ E)
(9) E*E
(10) E
此例中归约即计算表达式的值。归约顺序不同，
则计算的顺序也不同，结果也不一样。
起决定作用的是相邻的两个算符之间的优先关系 。
如果规定算符的优先次序，并按这种规定进行归约，则归约过程是 唯一 的。
所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找,可归约串,
和进行归约 。
首先必须定义任何两个可能相继出现的终结符 a与 b的优先关系三种关系
a <,b a的优先级低于 b
a b a的优先级等于 b
a,> b a的优先级高于 b
注意：与数学上的 <>=不同,a <.b并不意味着 b,> a
2.5.2.1 算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继 (并列 )的非终结符，即不含如下形式的产生式右部：
… QR…
则我们称该文法为 算符文法 。
约定：
a,b代表任意终结符；
P,Q,R代表任意非终结符；
‘ …? 代表由终结符和非终结符组成的任意序列，包括空字。
假定 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 。
如果一个算符文法 G中的任何终结符对 (a,b)至多只满足下述三关系之一：
a <,b,a,> b,a b
则称 G是一个 算符优先文法 。
例,考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
由第 (4)条规则，有 ‘ ()?；
由规则 E→E＋ T和 T?T*F,有 ＋ <,*；
由 (2)和 (3)，可得 * <.↑；
由 (1)E→E＋ T和 E? E+T，可得 +,>+；
由 (3)F→P?F和 F? P?F，可得 ↑ <,↑ 。
由 (4)P→(E)和 E?E+T?T+T?T*F+T?F*F+T
P↑F*F+T?i↑F*F+T
有 (<,+,(<,*,(<,↑和 (<,i。
优先关系表从算符优先文法 G构造优先关系表的算法。
通过检查 G的每个产生式的每个候选式，可找出所有满足 a b的终结符对。
确定满足关系 <.和,>的所有终结符对：
首先需要对 G的每个非终结符 P构造两个集合
FIRSTVT(P)和 LASTVT(P)：
F I R S T V T P a P a P Qa a V Q VT N( ) { |,,}或 而
},,|{)( NT VQVaaQPaPaPL AS T VT 而或
有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系 <.和,>的所有终结符对。
假定有个产生式的一个候选形为
…aP…
那么，对任何 b?FIRSTVT(P)，有 a <,b。
假定有个产生式的一个候选形为
…Pb…
那么，对任何 a?LASTVT(P)，有 a,> b。
首先讨论构造集合 FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合
FIRSTVT(P)：
1,若有产生式 P→a… 或 P→Qa…,则
a?FIRSTVT(P)；
2,若 a?FIRSTVT(Q)，且有产生式 P→Q…,则
a?FIRSTVT(P)。
构造 FIRSTVT(P)的算法：
引入一个布尔数组 F[P,a]，使得 F[P,a]为真的条件是，当且仅当 a?FIRSTVT(P)。开始时，
按上述的规则 (1)对每个数组元素 F[P,a]赋初值。
引入一个栈 STACK，把所有初值为真的数组元素 F[P,a]的符号对 (P,a)全都压入 STACK中。
运算：
如果栈 STACK不空，就将顶项逐出，记此项为 (Q,a)。对于每个形如
P→Q…
的产生式，若 F[P,a]为假，则变其值为真且将 (P,a)推进 STACK栈。
上述过程必须一直重复，直至栈 STACK拆空为止。
PROCEDURE INSERT(P,a)；
IF NOT F[P,a] THEN
BEGIN
F[P,a]:=TRUE；
把 (P,a)下推进 STACK栈
END；
构造 FIRSTVT(P)的伪代码主程序；
BEGIN
FOR 每个非终结符 P和终结符 a DO
F[P,a]:=FALSE；
FOR 每个形如 P→a… 或 P→Qa… 的产生式
DO
INSERT(P,a)；
WHILE STACK 非空 DO
BEGIN
弹出栈顶，记为 (Q,a) ；
FOR 每条形如 P→Q… 的产生式 DO
INSERT(P,a)；
END OF WHILE；
END
这个算法的工作结果得到一个二维数组 F，
从它可得任何非终结符 P的 FIRSTVT。
FIRSTVT(P)＝ {a | F[P,a]=TRUE}
同理，可构造计算 LASTVT的算法。
使用每个非终结符 P的 FIRSTVT(P)和
LASTVT(P)，就能够构造文法 G的优先表。构造优先表的算法是：
FOR 每条产生式 P→X1X2… Xn DO
FOR i:=1 TO n-1 DO
BEGIN
IF Xi和 Xi+1均为终结符 THEN 置 Xi Xi+1
IF i?n-2且 Xi和 Xi+2都为终结符但 Xi+1为非终结符 THEN 置 Xi Xi+2；
IF Xi为终结符而 Xi+1为非终结符 THEN
FOR FIRSTVT(Xi+1)中的每个 a DO
置 Xi <,a；
IF Xi为非终结符而 Xi+1为终结符 THEN
FOR LASTVT(Xi)中的每个 a DO
置 a.>Xi+1
END
例,考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
1,计算文法 G的 FIRSTVT和 LASTVT;
2,构造优先关系表 ;
3,G是算符优先文法吗?
}{ (,)(
}(,,,*,{)(
}(,,{)(
}(,,{ *,)(
iPF I R ST V T
iEF I R ST V T
iFF I R ST V T
iTF I R ST V T
}{ ),)(
}),,,*,{)(
}),,{)(
}),,{ *,)(
iPL A ST V T
iEL A ST V T
iFL A ST V T
iTL A ST V T
课堂练习,LASTVT的计算（ 8分钟）
+ *? ( ) i
+
*
(
)
i
结论,G是算符优先文法
G的算符优先关系表
2.5.2.2 算符优先分析算法可归约串，句型，短语，直接短语，句柄，规范归约。
一个文法 G的句型的 素短语 是指这样一个短语，它至少含有一个终结符，并且，
除它自身之外不再含任何更小的素短语。
最左素短语 是指处于句型最左边的那个素短语。
考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
E
E
F
+
*
T
i
F
T
F
T
P
+E
T
P
句型,T+F*P+i
短语,T+F*P+i,T,F，
P,F*P,i,T+F*P
直接短语,T,F,P,i
句柄,T
素短语,F*P,i
最左素短语,F*P
算符优先文法句型 (括在两个＃之间 )的一般形式写成：
#N1a1N2a2… NnanNn+1#
其中，每个 ai都是终结符,Ni是可有可无的非终结符。
定理,一个算符优先文法 G的任何句型的最左素短语是满足如下条件的最左子串
Njaj… NiaiNi+1，
aj-1 <,aj
aj aj+1,…,ai-1 ai
ai,> ai+1
算符优先分析算法使用一个符号栈 S，用它寄存终结符和非终结符,k代表符号栈 S的使用深度。
1 k:=1; S[k]:=?#?;
2 REPEAT
3 把下一个输入符号读进 a中；
4 IF S[k]?VT THEN j:=k ELSE j:=k-1;
5 WHILE S[j],>a DO
6 BEGIN
7 REPEAT
8 Q:=S[j];
9 IF S[j-1]?VT THEN j:=j-1 ELSE j:=j-2
10 UNTIL S[j]<.Q;
11 把 S[j+1]… S[k]归约为某个 N；
12 k:=j+1;
13 S[k]:=N
14 END OF WHILE;
15 IF S[j]<.a OR S[j] a THEN
16 BEGIN k:=k+1;S[k]:=a END
17 ELSE ERROR /*调用出错诊察程序 */
18 UNTIL a=?#?
在算法的工作过程中，若出现 j减 1后的值小于等于 0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈
S应呈现,# N #。
算法的第 11行中的 N是指那样一个产生式的左部符号，此产生式的右部和
S[j+1]… S[k] 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈 S。
算符优先分析一般并不等价于规范归约。
E
E +
*
iT
P
+
i
P
i
P
i
P
E
E
F
+
*
T
i
F
T
F
T
P
+E
T
i
F
P
i
P i
P
算符优先分析法特点：
优点,简单，快速
缺点,可能错误接受非法句子，能力有限,
算符优先分析法是一种广为应用、行之有效的方法。
用于分析各类表达式
ALGOL 60
2.5.2.3 优先函数把每个终结符?与两个自然数 f(?)与 g(?)相对应，使得若?1 <,?2，则 f(?1) < g(?2)
若?1?2，则 f(?1) = g(?2)
若?1,>?2，则 f(?1) > g(?2)
f称为入栈优先函数,g称为比较优先函数。
优点,便于比较，节省空间；
缺点,原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。
文法 G(E)
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
的优先函数如下表
+ * ↑ ( ) i #
F 2 4 4 0 6 6 0
G 1 3 5 5 0 5 0
有许多优先关系表不存在优先函数，如：
a b
a
b
不存在对应的优先函数 f和 g
假定存在 f和 g，则有
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 对于每个终结符 a，令其对应两个符号 fa和 ga，画一以所有符号和为结点的方向图。如果 a.> b，则从 fa画一条弧至 gb，如果 a<,b，则画一条弧从 gb至
fa 。
2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点 (包括出发点自身 )。赋给 fa的数作为 f(a)，赋给 ga的数作为 g(a)。
3 检查所构造出来的函数 f和 g是否与原来的关系矛盾。
若没有矛盾，则 f和 g就是要求的优先函数，若有矛盾，则不存在优先函数。
现在必须证明：若 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,b.> a1,a1,> b1,…,am,> bm,bm,> a
对任何优先函数 f和 g来说，必定有
f(a)> g(b)? f(a1)? g(b1)? …? f(am)? g(bm)?
f(a)
从而导致 f(a)> f(a)，产生矛盾。因此，不存在优先函数 f和 g。
fa1fa fam
gb1gb gbm
…
…
例,取前面文法 G(E)
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
的终结符 +,*,↑,i
f+ f* f? fi
g+ g* g? gi
+ *? i
+
*
i
+ * ↑ i
f 2 4 4 7
g 1 3 6 6
2.5.3 LR分析法
LR分析法,1965年 由 Knuth提出分析表产生器文法 分析表
LR分析总 控程 序输入 输出
产生分析表
LR分析器工作主要介绍
1,总控程序 (LR分析器 )的处理思想
2,LR分析表的构造原理及方法
2.5.3.1 LR分析器规范归约 的关键问题是寻找 句柄,
,历史,,已移入符号栈的内容
,展望,,根据产生式推测未来可能遇到的输入符号
,现实,,当前的输入符号
X n 输入串
X 2 a #
X 1
#
LR分析方法：把 "历史 "及 "展望 "综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作
LR分析程 序状态 符号
S
m
X
m
S
1
X
1
S
0
#
分析栈 action goto
LR分析表
a1a2? ai? an# 输入串输出
LR分析器的核心是一张分析表：
ACTION[s,a]：当状态 s面临输入符号 a时，
应采取什么动作,
GOTO[s,X]：状态 s面对文法符号 X时，下一状态是什么每一项 ACTION[s,a]所规定的四种动作,
1,移进 把 (s,a)的下一状态 s?=GOTO[s,a]和输入符号 a推进栈，下一输入符号变成当前输入符号,
2,归约 指用某产生式 A进行归约,假若?的长度为 r,归约动作是,去除栈顶 r个项，使状态
sm-r变成栈顶状态，然后把 (sm-r,A)的下一状态
s?=GOTO[sm-r,A]和文法符号 A推进栈,
3,接受 宣布分析成功，停止分析器工作,
4,报错分析开始时,
状态 已归约串 输入串
(s0,#,a1a2? an #)
以后每步的结果可以表示为,
(s0 s1? sm,# X1? Xm,aiai+1? an #)
(s0 s1? sm,# X1? Xm,aiai+1? an #)
分析器根据 ACTION(sm,ai)确定下一步动作
1,若 ACTION(sm,ai)为移进，且 s=GOTO(sm,ai)，则三元式格局变为,
(s0 s1? sms,# X1? Xm ai,ai+1? an #))
2,若 ACTION(sm,ai)为按 A归约，三元式变为,
(s0 s1? sm-rs,# X1? Xm-rA,aiai+1? an #))
此处,s=GOTO(sm-r,A),r为?的长度,?= Xm-r+1? Xm
3,若 ACTION(sm,ai)为 "接受 "，则三元式不再变化，变化过程终止，宣布分析成功,
4,若 ACTION(sm,ai)为 "报错 "，则三元式变化过程终止，
报告错误,
LR分析器示例：
文法 G(E)：
(1) E→E＋ T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→i
ACTION GO TO
状态 i + * ( ) # E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
其 LR分析表为,
假定输入串为 i*i+i,LR分析器的工作过程,
步骤 状态 符号 输入串
(1) 0 # i*i+i#
(2) 05 #i *i+i#
(3) 03 #F *i+i#
(4) 02 #T *i+i#
(5) 027 #T* i+i#
(6) 0275 #T*i +i#
(7) 02710 #T*F +i#
(8) 02 #T +i#
(9) 01 #E +i#
(10) 016 #E+ i#
步骤 状态 符号 输入串
(11) 0165 #E+i #
(12) 0163 #E+F #
(13) 0169 #E+T #
(14) 01 #E #
(15) 接受
E
E
*T
T+
F
F
F
i
ii
定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为 LR文法 。
定义：一个文法，如果能用一个每步最多向前检查 k个输入符号的 LR分析器进行分析，则这个文法就称为 LR(k)文法,
非 LR结构
LR文法不是二义的，二义文法肯定不会是 LR
的。
S? iCtS | iCtSeS
栈 输入
… iCtS e… #
非 LR结构例：某语言的词法分析器将任何标识符都送回单词符号 i。若它的数组和过程调用采用相同的结构，如,A(i,j），则不能识别是过程调用还是数组引用。
在移进 i（ i后不能确定用（ 5)还是（ 7)进行规约非 LR结构思考：关键是（ 1)和（ 6）首部相同，
怎样解决这个问题？
2.5.3.2 LR(0)项目集族和
LR(0)分析表的构造字的前缀,是指字的任意首部，如字 abc的前缀有?,a,ab,abc
活前缀,是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
LR分析过程中,分析栈中符号自底向上应该构成活前缀,只要栈中是活前缀，就说明已扫描过的部分没有错。活前缀配上输入串的剩下部分就构成一个规范句型。
对于一个文法 G,可以构造一个 DFA,它能识别
G的所有活前缀,
文法 G的每个产生式的右部添加一个圆点称为 G的 LR(0)项目如,A?XYZ有四个项目：
A?.XYZ A?X.YZ A?XY.Z
A?XYZ.
A,称为 "归约项目 "
归约项目 S,称为 "接受项目 "
A,a? (a?VT) 称为 "移进项目 "
A,B? (B?VN) 称为 "待约项目 ".
文法 G(S?)
S?→E
E→aA|bB
A→cA|d
B→cB|d
该文法的项目有：
1,S?→·E 2,S?→E· 3,E→·aA
4,E→a·A 5,E→aA· 6,A→·cA
7,A→c·A 8,A→cA· 9,A→·d
10,A→d· 11,E→·bB 12,E→b·B
13,E→bB· 14,B→·cB 15,B→c·B
16,B→cB· 17,B→·d 18,B→d·
构造识别文法所有活前缀的
NFA方法
1.拓广文法
设文法 G的开始符号为 S，增加一条产生式 S?→S，构造一个新文法 G?。
S?是 G?的开始符号，称 G?是 G的 拓广文法 。
拓广文法的主要目的：
让文法只有唯一的,接受,态，即项目
S?→S.。
2,若状态 i为 X?X1 … Xi-1.Xi … Xn,
状态 j为 X?X1 … Xi-1Xi,Xi+1 … Xn,
则从状态 i画一条标记为 Xi的有向边到状态 j；
3,若状态 i为 X.A?,A为非终结符，
则从状态 i画一条?边到所有状态 A?.?。
4.把识别文法所有活前缀的 NFA确定化。
构成识别一个文法活前缀的 DFA的项目集
(状态 )的全体称为文法的 LR(0)项目集规范族 。
6 7 8
9 10
4 53
1 2
11 12 13
14 15 16
1817
a
A
E
b B
B
c A
c
d
识别活前缀的 NFA
识别活前缀的 DFA
0,S?→·E
E→·aA
E→·bB
4:A→c·A
A→·cA
A→·d
2,E→a·A
A→·cA
A→·d
1,S?→E·
3,E→b·B
B→·cB
B→·d
5,B→c·B
B→·cB
B→·d
11,B→d·
9,B→cB·
7,E→bB·
10,A→d·
6,E→aA·
8,A→cA·
c
c
b
E
a
d
Ac
c
d
d
d
B
A
B
假定 I是文法 G?的任一项目集，定义和构造
I的闭包 CLOSURE(I)如下：
1,I的任何项目都属于 CLOSURE(I)；
2,若 A→?·B?属于 CLOSURE(I)，那么，
对任何关于 B的产生式 B→?，项目 B→·?也属于 CLOSURE(I)；
3,重复执行上述两步骤直至 CLOSURE(I)
不再增大为止。
LR(0)项目集规范族的构造设 I是一个项目集,X是一个文法符号，引入状态转换函数 GO(I,X)描述在状态集合 I在识别 X后转换后的新状态，定义为：
GO(I,X)＝ CLOSURE(J)
其中
J＝ {任何形如 A→?X·?的项目 | A→? ·X?属于 I}。
状态转换函数 GO
构造文法 G的拓广文法 G?的 LR(0)项目集规范族算法：
PROCEDURE ITEMSETS(G?)；
BEGIN
C:={CLOSURE({S·S})}；
REPEAT
FOR C中每个项目集 I和 G?的每个符号 X DO
IF GO(I,X)非空且不属于 C THEN
把 GO(I,X)放入 C族中 ;
UNTIL C 不再增大
END
转换函数 GO把项目集连接成一个 DFA转换图,
文法 G(S?)
S?→E
E→aA|bB
A→cA|d
B→cB|d
I0= closure({S?→·E}) = {S?→·E,E→·aA,E→·bB}
GO(I0,E)= closure(J) = closure({S?→E·})=I1
GO(I0,a)= closure(J)=closure({E→a·A})
={ E→a·A,A→·cA,A→·d} )=I2
GO(I0,b)= closure(J) = closure({E →b.B})
=｛ E→b·B,B→·cB,B→·d}=I3
0,S?→·E
E→·aA
E→·bB
4:A→c·A
A→·cA
A→·dc
5,B→c·B
B→·cB
B→·d
c
3,E→b·B
B→·cB
B→·d
b
1,S?→E·E
2,E→a·A
A→·cA
A→·d
a
11,B→d·d
8,A→cA·A
c
c
d
10,A→d·
d
d
9,B→cB·B
6,E→aA·A
7,E→bB·B
LR(0)分析表的构造假若一个文法 G的拓广文法 G?的活前缀识别自动机中的每个状态 (项目集 )不存在任何下述情况：
1) 既含移进项目又含归约项目
（移进－归约冲突）
2) 含有多个归约项目
（归约－归约冲突）
则称 G是一个 LR(0)文法 。
构造 LR(0)分析表的算法令每个项目集 Ik的下标 k作为分析器的状态，包含项目 S?→·S的集合 Ik的下标 k为分析器的初态。
分析表的 ACTION和 GOTO子表构造方法：
1,若项目 A→?·a?属于 Ik且 GO(Ik,a)＝ Ij,a为终结符，
则置 ACTION[k,a] 为,sj”。
2,若项目 A→?·属于 Ik，那么，对任何终结符 a(或结束符 #)，置 ACTION[k,a]为,rj”(假定产生式 A→?是文法 G?的第 j个产生式 )。
3,若项目 S?→S·属于 Ik，则置 ACTION[k,#]为,acc”。
4,若 GO(Ik,A)＝ Ij,A为非终结符，则置 GOTO[k,A]=j。
5,分析表中凡不能用规则 1至 4填入信息的空白格均置上,报错标志,。
上例的 LR(0)分析表为
ACTION GO TO
状态 a b c d # E A B
0 s2 s3 1
1 acc
2 s4 s10 6
3 s5 s11 7
4 s4 s10 8
5 s5 s11
6 r1 r1 r1 r1 r1 9
7 r2 r2 r2 r2 r2
8 r3 r3 r3 r3 r3
9 r5 r5 r5 r5 r5
10 r4 r4 r4 r4 r4
11 r6 r6 r6 r6 r6
例,按上表对 acccd进行分析步骤 状态 符号 输入串
1 0 # acccd#
2 02 #a cccd#
3 024 #ac ccd#
4 0244 #acc cd#
5 02444 #accc d#
6 0244410 #acccd #
7 024448 #acccA #
8 02448 #accA #
9 0248 #acA #
10 026 #aA #
11 01 #E #
2.5.3.3 SLR分析表的构造
LR(0)文法太简单，没有实用价值,
假定一个 LR(0)规范族中含有如下的一个项目集 (状态 )II＝ {X→?·b?,A→?·,B→?·}。
FOLLOW(A) ∩FOLLOW(B)=?，且不包含 b，
那么，当状态 I面临任何输入符号 a时，可以,
1,若 a=b，则移进；
2,若 a?FOLLOW(A),用产生式 A→?进行归约；
3,若 a?FOLLOW(B),用产生式 B→?进行归约；
4,此外，报错。
更一般地，假定 LR(0)规范族的一个项目集
I={A1→?·a1?1,A2→?·a2?2,…,
Am→?·am?m,B1→?·,B2→?·,…,Bn→?·}
如果集合 {a1,…,am},FOLLOW(B1),…,
FOLLOW(Bn)两两不相交 (包括不得有两个
FOLLOW集合有 #)，则：
1,若 a是某个 ai,i=1,2,…,m，则移进；
2,若 a?FOLLOW(Bi),i=1,2,…,n，则用产生式
Bi→?进行归约；
3,此外，报错。
冲突性动作的这种解决办法叫做 SLR(1)解决办法 。
构造 SLR(1)分析表方法,
首先把 G拓广为 G?，对 G?构造 LR(0)项目集规范族 C和活前缀识别自动机的状态转换函数 GO.
然后使用 C和 GO，按下面的算法构造 SLR
分析表：
令每个项目集 Ik的下标 k作为分析器的状态，
包含项目 S?→·S的集合 Ik的下标 k为分析器的初态。
分析表的 ACTION和 GOTO子表构造方法：
1,若项目 A→?·a?属于 Ik且 GO(Ik,a)=Ij,a为终结符，则置
ACTION[k,a]为,sj”；
2,若项目 A→?·属于 Ik，那么，对任何终结符 a，
a?FOLLOW(A)，置 ACTION[k,a]为,rj”；其中，假定 A为文法 G?的第 j个产生式；
3,若项目 S?→S·属于 Ik，则置 ACTION[k,#]为,acc”;
4,若 GO(Ik,A)＝ Ij,A为非终结符，则置 GOTO[k,A]=j；
5,分析表中凡不能用规则 1至 4填入信息的空白格均置上
,出错标志,。
按上述方法构造出的 ACTION与 GOTO表如果不含多重入口，则称该文法为 SLR(1)文法 。
使用 SLR表的分析器叫做一个 SLR分析器 。
每个 SLR(1)文法都是无二义的。但也存在许多无二义文法不是 SLR(1)的,
例 5.11 考察下面的拓广文法：
(0) S?→E
(1) E→E+T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→i
这个文法的 LR(0)项目集规范族为：
I0,S?→·E
E→·E+T
E→·T
T→·T*F
T→·F
F→· (E)
F→·i
I1,S?→E·
E→E·+T
I2,E→T·
T→T·*F
I3,T→F·
I4,F→(·E)
E→·E+T
E→·T
T→·T*F
T→·F
F→· (E)
F→·i
I5,F→i·
I6,E→E+·T
T→·T*F
T→·F
F→·(F)
F→·i
I7,T→T*·F
F→·(E)
F→·i
I8,F→(E·)
E→E·+T
I9,E→E+T·
T→T·*F
I10,T→T*F ·
I11,F→(E)·
I1,I2和 I9都含有,移进－归约,冲突。
FOLLOW(S?）＝｛ #｝ FOLLOW(E)＝ {#,),+}，
I0
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
E
+ T *
T T
i
F
( i
( F
E
(F
i
+
F*
(
)
AC TION GO TO
状态 i + * ( ) # E T F
0 s5 s4 1 2 3
1 s6 a cc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s1 1
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
其分析表如下,
非 SLR文法示例：考虑如下文法：
(0) S?→S
(1) S→L=R
(2) S→R
(3) L→*R
(4) L→i
(5) R→L
计算 FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。
这个文法的 LR(0)项目集规范族为：
I0,S?→·S
S→·L=R
S→·R
L→·*R
L→·i
R→·L
I1,S?→S·
I2,S→L·=R
R→L·
I3,S→R·
I4,L→*·R
R→·L
L→·*R
L→·i
I5,L→i·
I6,S→L=·R
R→·L
L→·*R
L→·i
I7,L→*R·
I9,S→L=R·
I8,R→L·
R
S = i
L
R * L
*
* R
i
i L
活前缀识别器
1
2
0
3
4
6
7
5
8
9
在 SLR方法中,如果项目集 Ii含项目 A.而且下一输入符号 a?FOLLOW(A),则状态 i
面临 a时,可选用,用 A归约,动作。但在有些情况下,当状态 i显现于栈顶时,栈里的 活前缀 未必允许把?归约为 A，因为可能根本就不存在一个形如,?Aa”的规范句型。
因此，在这种情况下，用,A”归约不一定合适。
如上例,当状态 2显现于栈顶而且面临输入符号为 ‘ =?时，实际上不能用对栈顶 L
进行归约，因为这个文法不含,R=”为前缀的规范句型。
2.5.3.4 规范 LR分析表的构造我们需要重新定义项目，使得每个项目都附带有 k个终结符。每个项目的一般形式是 [A→?·?,a1a2… ak],这样的一个项目称为一个 LR(k)项目 。项目中的 a1a2… ak 称为它的 向前搜索符串 (或 展望串 )。
向前搜索符串仅对归约项目 [A→?·，
a1a2… ak]有意义。对于任何移进或待约项目 [A→?·?,a1a2… ak],，搜索符串
a1a2… ak 没有作用。
归约项目 [A→?·,a1a2… ak]意味着：当它所属的状态呈现在栈顶且后续的 k个输入符号为 a1a2… ak 时，才可以把栈顶上的?归约为
A。
我们只对 k?1的情形感兴趣，向前搜索 (展望 )
一个符号就多半可以确定,移进,或,归约,。为构造有效的 LR(1)项目集族我们需要两个函数 CLOSURE和 GO。
项目集 I 的闭包 CLOSURE(I)构造方法：
1,I的任何项目都属于 CLOSURE(I)。
2,若项目 [A→?·B?,a]属于 CLOSURE(I),B→?
是一个产生式，那么，对于 FIRST(?a) 中的每个终结符 b，如果 [B→·?,b]原来不在
CLOSURE(I)中，则把它加进去。
3,重复执行步骤 2，直至 CLOSURE(I)不再增大为止。
令 I是一个项目集,X是一个文法符号，
函数 GO(I,X)定义为：
GO(I,X)＝ CLOSURE(J)
其中
J＝ {任何形如 [A→?X·?,a]的项目
| [A→?·X?,a]?I}
文法 G?的 LR(1)项目集族 C的构造算法：
BEGIN
C:={CLOSURE({[S?→·S,#]})};
REPEAT
FOR C中每个项目集 I和 G?的每个符号 X DO
IF GO(I,X)非空且不属于 C,THEN
把 GO(I,X)加入 C中
UNTIL C不再增大
END
例 5.13 (5.10)的拓广文法 G( S?)
(0) S?→S
(1) S→BB
(2) B→aB
(3) B→b
LR(1)的项目集 C和函数 GO可构造为,
I0,SS,#
SBB,#
BaB,a/b
Bb,a/b
S I
1,SS?,#
B I
2,S?B? B,#
BaB,a/b
Bb,a/ba
I3,B?a?B,a/b
BaB,a/b
Bb,a/b
b
I4,B?b?,a/b
B
I5,S?BB?,#
a I6,B?a?B,#BaB,#
Bb,#
b
I7,B?b?,#
B
I8,B?aB?,a/b
ab
a
I9,B?aB?,#
Bb
构造 LR(1)分析表的算法。
令每个 Ik的下标 k为分析表的状态，令含有
[S?→·S,#]的 Ik的 k为分析器的初态。
动作 ACTION和状态转换 GOTO构造如下：
1,若项目 [A→?·a?,b]属于 Ik且 GO(Ik,a)＝ Ij，
a为终结符，则置 ACTION[k,a]为,sj”。
2,若项目 [A→?·,a]属于 Ik，则置 ACTION[k,
a]为,rj”；其中假定 A→?为文法 G?的第 j个产生式。
3,若项目 [S?→S·,#]属于 Ik，则置 ACTION[k,#]
为,acc”。
4,若 GO(Ik,A)＝ Ij，则置 GOTO[k,A]=j。
5,分析表中凡不能用规则 1至 4填入信息的空白栏均填上,出错标志,。
按上述算法构造的分析表，若不存在多重定义的入口 (即，动作冲突 )的情形，则称它是文法 G
的一张 规范的 LR(1)分析表 。
使用这种分析表的分析器叫做一个 规范的 LR分析器 。
具有规范的 LR(1)分析表的文法称为一个 LR(1)
文法 。
LR(1)状态比 SLR多，
LR(0)?SLR（ 1）? LR(1)?无二义文法
ACTION GO TO
状态 a b # S B
0 s3 s4 1 2
1 acc
2 s6 s7 5
3 s3 s4 8
4 r3 r3
5 r1
6 s6 s7 9
7 r3
8 r2 r2
9 r2
上例的 LR(1)分析表为,
例,按上表对 aabab进行分析步骤 状态 符号 输入串
0 0 # aabab#
1 03 #a abab#
2 033 #aa bab#
3 0334 #aab ab#
4 0338 #aaB ab#
5 038 #aB ab#
6 02 #B ab#
7 026 #Ba b#
8 0267 #Baa #
9 0269 #BaB #
10 025 #BB #
11 01 #S # acc
例,按上表对 abab进行分析步骤 状态 符号 输入串
0 0 # abab#
1 03 #a bab#
2 034 #ab ab#
3 038 #aB ab#
4 02 #B ab#
5 026 #Ba b#
6 0267 #Bab #
7 0269 #BaB #
8 025 #BB #
9 01 #S # acc
(1) LALR(1)分析的第 1个原则
LR(1)项目的 DFA的 状态核心 是 LR(0)项目的 DFA的一个状态。
(2) LALR(1)分析的第 2个原则（同心转换后仍同心）
若有具有 相同核心 的 LR(1)项目的 DFA的两个状态 s1
和 s2，假设在符号 X上有一个从 s1到状态 t1的转换，则在 X上也有一个从状态 s2到一个状态 t2的转换，且状态
t1和 t2具有相同的核心。
LALR(1)分析
(合并同心集的 LR(1)分析）
LALR(1)项 DFA的构造方法
LALR(1)项 DFA是在 LR(1)项目的 DFA基础上构造出来的。
通过合并具有相同核心的所有状态，同时将那些同心状态的先行符号的并起来获得。
每个 LALR(1)项目都包含一个 LR(0)项目和一个先行记号的集合。
LALR（ 1)项中多先行记号的表示法在先行之间写一个 /来表示多重先行。
因此,LALR(1)项目 [A→a.b,a/b/c] 具有一个由符号 a,b 和 c 组成的先行集合。
LALR(1)分析例,考虑文法,A→(A)|a
(1) A→(A) (2) A→a 找出其中的同心集！
图 5－ 7
LALR(1)分析例,考虑文法,A→(A)|a
(1) A→(A) (2) A→a
图 5－ 9
LALR(1)文法的判断方法定义：
若在 LALR(1)分析算法中没有出现分析冲突则称这个文法为 LALR(1)文法 (LALR(1)
grammar)。
四种文法的相互比较
1.若一个文法是 LR(0)文法，就一定是 SLR(1)文法；
2.若一个文法是 LR(1)文法，则它的 LALR(1)分析表不会有移进 -归约冲突，但却可能有归约 -归约冲突。
3,若一个文法是 SLR(1)文法，那么它肯定就是
LALR(1)文法。
自下而上 (Bottom-Up)分析采用,移进－归约,(shift-reduce)的 基本思想
把输入符号逐个移进到一个符号栈,当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成
(归约 为 )该产生式的左部符号。
2.5 语法分析 ——自下而上分析例：设文法 G(S)：
(1) S? aAcBe
(2) A? b
(3) A? Ab
(4) B? d
试对 abbcde进行,移进－归约,分析。
a
bbcde
b
bcde
A
b cdec de
d eabbcde
e
B
S
c
a
e
步骤,1 2 3 4 5 6 7 8 9 10
动作,进 a 进 b 归 (2 ) 进 b 归 (3 ) 进 c 进 d 归 (4 ) 进 e 归 (1 )
e
d B B
b c c c c
b A A A A A A A
a a a a a a a a a S
b
db
a c e
S
A B
A
自下而上分析过程：边输入单词符号，边归约。
核心问题：识别可归约串
2.5.1.2 规范归约定义：令 G是一个文法,S是文法的开始符号，假定是文法 G的一个句型，如果有且
AS *A
则?称是句型相对于非终结符 A的 短语 。
特别是，如果有 A,则称?是句型相对于规则 A的 直接短语 。一个句型的最左直接短语称为该句型的 句柄 。
考虑文法 G(E),E? T | E+T
T? F | T*F
F? (E) | i
和句型 i1*i2+i3：
E? E+T? E+F? E+i3? T+i3
T*F+i3? T*i2+i3? F*i2+i3
i1*i2+i3
问题：对于句型 i1*i2+i3而言，有哪些短语、
直接短语和句柄？
因为
E *? F*i2+i3? i1*i2+i3,所以 i1是句型相对于非终结符 F
的短语和直接短语。
E*?i1*F+i3? i1*i2+i3,所以 i2是句型相对于非终结符 F的短语和直接短语。
E*?i1*i2+F?i1*i2+i3,所以 i3是句型相对于非终结符 F的短语和直接短语。
E*?E+i3 +? i1*i2+i3,所以 i1*i2是句型相对于非终结符 E
的短语。
E *? E? i1*i2+i3,所以 i1*i2+i3是句型相对于非终结符 E
的短语。
结论：对于句型 i1*i2+i3而言：
短语,i1,i2,i3,i1*i2,i1*i2+i3
直接短语,i1,i2,i3
句柄,i1
在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。 而最左直接短语就是句柄。
E
F
F
T
T
T
i1
+
*
E
F
i3
i2
根据语法树找短语、直接短语、句柄可用句柄来对句子进行归约句型 归约规则
abbcde (2) A? b
aAbcde (3) A? Ab
aAcde (4) B? d
aAcBe (1) S? aAcBe
S
定义：假定?是文法 G的一个句子，我们称序列
n,?n-1,?,?0
是一个 规范归约,如果此序列满足：
1?n=?
2?0为文法的开始符号，即?0=S
3 对任何 i,0? i? n,?i-1是从?i经把句柄替换成为相应产生式左部符号而得到的。
把上例倒过来写，则得到：
S? aAcBe? aAcde? aAbcde? abbcde
显然这是一个最右推导。
规范归约是一个最右推导的逆过程。
最左归约 规范推导由规范推导推出的句型称为 规范句型 。
b
db
a c e
S
A B
A d
b
a c e
S
A B
A
d
a c e
S
A B a c e
S
A B
利用语法树寻找句柄
2.5.1.3符号栈的使用和分析树的表示栈是语法分析的一种基本数据结构。 ’ #?作为栈底符号考虑文法 G(E)：
E? T | E+T
T? F | T*F
F? (E) | i
输入串为 i1*i2+i3,分析步骤为：
步骤 符号栈 输入串 动作
0 # i1*i2+i3# 预备
1 #i1 *i2+i3# 进
2 #F *i2+i3# 归，用 F→i
3 #T *i2+i3# 归，用 T→F
4 #T* i2+i3# 进
5 #T*i2 +i3# 进
6 #T*F +i3# 归，用 F→i
7 #T +i3# 归，用 T→T*F
步骤 符号栈 输入串 动作
8 #E +i3# 归，用 E→T
9 #E+ i3# 进
10 #E+i3 # 进
11 #E+F # 归，用 F→i
12 #E+T # 归，用 T→F
13 #E # 归，用 E→E+T
14 #E # 接受
2.5.2 算符优先分析四则运算的优先规则：
先乘除后加减，同级从左到右考虑二义文法文法 G(E)：
G(E),E? i| E+E|E-E|E*E|E/E|(E)
它的句子有几种 不同的规范规约 。
例如：句子 i+i-i*(i+i)
E
i
( )
i
*
E
i
E E
+
E
EE
-
i i
+
E
EE
句子 i+i-i*(i+i)的归约过程是：
(1) i+i-i*(i+i)
(2) E+i-i*(i+i)
(3) E+E-i*(i+i)
(4) E-i*(i+i)
(5) E-E*(i+i)
(6) E-E*(E+i)
(7) E-E*(E+E)
(8) E-E*(E)
(9) E-E*E
(10) E-E
(11) E
E
i
( )
i
*
E
i
E
E
+
E
EE
-
i
i+
E
E
E
返回句子 i+i-i*(i+i)的归约过程是：
(1) i+i-i*(i+i)
(2) E+i-i*(i+i)
(3) E+E-i*(i+i)
(4) E-i*(i+i)
(5) E-E*(i+i)
(6) E*(i+i)
(7) E*(E+i)
(8) E*(E＋ E)
(9) E*E
(10) E
此例中归约即计算表达式的值。归约顺序不同，
则计算的顺序也不同，结果也不一样。
起决定作用的是相邻的两个算符之间的优先关系 。
如果规定算符的优先次序，并按这种规定进行归约，则归约过程是 唯一 的。
所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找,可归约串,
和进行归约 。
首先必须定义任何两个可能相继出现的终结符 a与 b的优先关系三种关系
a <,b a的优先级低于 b
a b a的优先级等于 b
a,> b a的优先级高于 b
注意：与数学上的 <>=不同,a <.b并不意味着 b,> a
2.5.2.1 算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继 (并列 )的非终结符，即不含如下形式的产生式右部：
… QR…
则我们称该文法为 算符文法 。
约定：
a,b代表任意终结符；
P,Q,R代表任意非终结符；
‘ …? 代表由终结符和非终结符组成的任意序列，包括空字。
假定 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 。
如果一个算符文法 G中的任何终结符对 (a,b)至多只满足下述三关系之一：
a <,b,a,> b,a b
则称 G是一个 算符优先文法 。
例,考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
由第 (4)条规则，有 ‘ ()?；
由规则 E→E＋ T和 T?T*F,有 ＋ <,*；
由 (2)和 (3)，可得 * <.↑；
由 (1)E→E＋ T和 E? E+T，可得 +,>+；
由 (3)F→P?F和 F? P?F，可得 ↑ <,↑ 。
由 (4)P→(E)和 E?E+T?T+T?T*F+T?F*F+T
P↑F*F+T?i↑F*F+T
有 (<,+,(<,*,(<,↑和 (<,i。
优先关系表从算符优先文法 G构造优先关系表的算法。
通过检查 G的每个产生式的每个候选式，可找出所有满足 a b的终结符对。
确定满足关系 <.和,>的所有终结符对：
首先需要对 G的每个非终结符 P构造两个集合
FIRSTVT(P)和 LASTVT(P)：
F I R S T V T P a P a P Qa a V Q VT N( ) { |,,}或 而
},,|{)( NT VQVaaQPaPaPL AS T VT 而或
有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系 <.和,>的所有终结符对。
假定有个产生式的一个候选形为
…aP…
那么，对任何 b?FIRSTVT(P)，有 a <,b。
假定有个产生式的一个候选形为
…Pb…
那么，对任何 a?LASTVT(P)，有 a,> b。
首先讨论构造集合 FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合
FIRSTVT(P)：
1,若有产生式 P→a… 或 P→Qa…,则
a?FIRSTVT(P)；
2,若 a?FIRSTVT(Q)，且有产生式 P→Q…,则
a?FIRSTVT(P)。
构造 FIRSTVT(P)的算法：
引入一个布尔数组 F[P,a]，使得 F[P,a]为真的条件是，当且仅当 a?FIRSTVT(P)。开始时，
按上述的规则 (1)对每个数组元素 F[P,a]赋初值。
引入一个栈 STACK，把所有初值为真的数组元素 F[P,a]的符号对 (P,a)全都压入 STACK中。
运算：
如果栈 STACK不空，就将顶项逐出，记此项为 (Q,a)。对于每个形如
P→Q…
的产生式，若 F[P,a]为假，则变其值为真且将 (P,a)推进 STACK栈。
上述过程必须一直重复，直至栈 STACK拆空为止。
PROCEDURE INSERT(P,a)；
IF NOT F[P,a] THEN
BEGIN
F[P,a]:=TRUE；
把 (P,a)下推进 STACK栈
END；
构造 FIRSTVT(P)的伪代码主程序；
BEGIN
FOR 每个非终结符 P和终结符 a DO
F[P,a]:=FALSE；
FOR 每个形如 P→a… 或 P→Qa… 的产生式
DO
INSERT(P,a)；
WHILE STACK 非空 DO
BEGIN
弹出栈顶，记为 (Q,a) ；
FOR 每条形如 P→Q… 的产生式 DO
INSERT(P,a)；
END OF WHILE；
END
这个算法的工作结果得到一个二维数组 F，
从它可得任何非终结符 P的 FIRSTVT。
FIRSTVT(P)＝ {a | F[P,a]=TRUE}
同理，可构造计算 LASTVT的算法。
使用每个非终结符 P的 FIRSTVT(P)和
LASTVT(P)，就能够构造文法 G的优先表。构造优先表的算法是：
FOR 每条产生式 P→X1X2… Xn DO
FOR i:=1 TO n-1 DO
BEGIN
IF Xi和 Xi+1均为终结符 THEN 置 Xi Xi+1
IF i?n-2且 Xi和 Xi+2都为终结符但 Xi+1为非终结符 THEN 置 Xi Xi+2；
IF Xi为终结符而 Xi+1为非终结符 THEN
FOR FIRSTVT(Xi+1)中的每个 a DO
置 Xi <,a；
IF Xi为非终结符而 Xi+1为终结符 THEN
FOR LASTVT(Xi)中的每个 a DO
置 a.>Xi+1
END
例,考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
1,计算文法 G的 FIRSTVT和 LASTVT;
2,构造优先关系表 ;
3,G是算符优先文法吗?
}{ (,)(
}(,,,*,{)(
}(,,{)(
}(,,{ *,)(
iPF I R ST V T
iEF I R ST V T
iFF I R ST V T
iTF I R ST V T
}{ ),)(
}),,,*,{)(
}),,{)(
}),,{ *,)(
iPL A ST V T
iEL A ST V T
iFL A ST V T
iTL A ST V T
课堂练习,LASTVT的计算（ 8分钟）
+ *? ( ) i
+
*
(
)
i
结论,G是算符优先文法
G的算符优先关系表
2.5.2.2 算符优先分析算法可归约串，句型，短语，直接短语，句柄，规范归约。
一个文法 G的句型的 素短语 是指这样一个短语，它至少含有一个终结符，并且，
除它自身之外不再含任何更小的素短语。
最左素短语 是指处于句型最左边的那个素短语。
考虑下面的文法 G(E)：
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
E
E
F
+
*
T
i
F
T
F
T
P
+E
T
P
句型,T+F*P+i
短语,T+F*P+i,T,F，
P,F*P,i,T+F*P
直接短语,T,F,P,i
句柄,T
素短语,F*P,i
最左素短语,F*P
算符优先文法句型 (括在两个＃之间 )的一般形式写成：
#N1a1N2a2… NnanNn+1#
其中，每个 ai都是终结符,Ni是可有可无的非终结符。
定理,一个算符优先文法 G的任何句型的最左素短语是满足如下条件的最左子串
Njaj… NiaiNi+1，
aj-1 <,aj
aj aj+1,…,ai-1 ai
ai,> ai+1
算符优先分析算法使用一个符号栈 S，用它寄存终结符和非终结符,k代表符号栈 S的使用深度。
1 k:=1; S[k]:=?#?;
2 REPEAT
3 把下一个输入符号读进 a中；
4 IF S[k]?VT THEN j:=k ELSE j:=k-1;
5 WHILE S[j],>a DO
6 BEGIN
7 REPEAT
8 Q:=S[j];
9 IF S[j-1]?VT THEN j:=j-1 ELSE j:=j-2
10 UNTIL S[j]<.Q;
11 把 S[j+1]… S[k]归约为某个 N；
12 k:=j+1;
13 S[k]:=N
14 END OF WHILE;
15 IF S[j]<.a OR S[j] a THEN
16 BEGIN k:=k+1;S[k]:=a END
17 ELSE ERROR /*调用出错诊察程序 */
18 UNTIL a=?#?
在算法的工作过程中，若出现 j减 1后的值小于等于 0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈
S应呈现,# N #。
算法的第 11行中的 N是指那样一个产生式的左部符号，此产生式的右部和
S[j+1]… S[k] 构成如下一一对应关系：自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈 S。
算符优先分析一般并不等价于规范归约。
E
E +
*
iT
P
+
i
P
i
P
i
P
E
E
F
+
*
T
i
F
T
F
T
P
+E
T
i
F
P
i
P i
P
算符优先分析法特点：
优点,简单，快速
缺点,可能错误接受非法句子，能力有限,
算符优先分析法是一种广为应用、行之有效的方法。
用于分析各类表达式
ALGOL 60
2.5.2.3 优先函数把每个终结符?与两个自然数 f(?)与 g(?)相对应，使得若?1 <,?2，则 f(?1) < g(?2)
若?1?2，则 f(?1) = g(?2)
若?1,>?2，则 f(?1) > g(?2)
f称为入栈优先函数,g称为比较优先函数。
优点,便于比较，节省空间；
缺点,原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。
文法 G(E)
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
的优先函数如下表
+ * ↑ ( ) i #
F 2 4 4 0 6 6 0
G 1 3 5 5 0 5 0
有许多优先关系表不存在优先函数，如：
a b
a
b
不存在对应的优先函数 f和 g
假定存在 f和 g，则有
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 对于每个终结符 a，令其对应两个符号 fa和 ga，画一以所有符号和为结点的方向图。如果 a.> b，则从 fa画一条弧至 gb，如果 a<,b，则画一条弧从 gb至
fa 。
2 对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点 (包括出发点自身 )。赋给 fa的数作为 f(a)，赋给 ga的数作为 g(a)。
3 检查所构造出来的函数 f和 g是否与原来的关系矛盾。
若没有矛盾，则 f和 g就是要求的优先函数，若有矛盾，则不存在优先函数。
现在必须证明：若 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,b.> a1,a1,> b1,…,am,> bm,bm,> a
对任何优先函数 f和 g来说，必定有
f(a)> g(b)? f(a1)? g(b1)? …? f(am)? g(bm)?
f(a)
从而导致 f(a)> f(a)，产生矛盾。因此，不存在优先函数 f和 g。
fa1fa fam
gb1gb gbm
…
…
例,取前面文法 G(E)
(1) E→E+T | T
(2) T→T*F | F
(3) F→P? F | P
(4) P→(E) | i
的终结符 +,*,↑,i
f+ f* f? fi
g+ g* g? gi
+ *? i
+
*
i
+ * ↑ i
f 2 4 4 7
g 1 3 6 6
2.5.3 LR分析法
LR分析法,1965年 由 Knuth提出分析表产生器文法 分析表
LR分析总 控程 序输入 输出
产生分析表
LR分析器工作主要介绍
1,总控程序 (LR分析器 )的处理思想
2,LR分析表的构造原理及方法
2.5.3.1 LR分析器规范归约 的关键问题是寻找 句柄,
,历史,,已移入符号栈的内容
,展望,,根据产生式推测未来可能遇到的输入符号
,现实,,当前的输入符号
X n 输入串
X 2 a #
X 1
#
LR分析方法：把 "历史 "及 "展望 "综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作
LR分析程 序状态 符号
S
m
X
m
S
1
X
1
S
0
#
分析栈 action goto
LR分析表
a1a2? ai? an# 输入串输出
LR分析器的核心是一张分析表：
ACTION[s,a]：当状态 s面临输入符号 a时，
应采取什么动作,
GOTO[s,X]：状态 s面对文法符号 X时，下一状态是什么每一项 ACTION[s,a]所规定的四种动作,
1,移进 把 (s,a)的下一状态 s?=GOTO[s,a]和输入符号 a推进栈，下一输入符号变成当前输入符号,
2,归约 指用某产生式 A进行归约,假若?的长度为 r,归约动作是,去除栈顶 r个项，使状态
sm-r变成栈顶状态，然后把 (sm-r,A)的下一状态
s?=GOTO[sm-r,A]和文法符号 A推进栈,
3,接受 宣布分析成功，停止分析器工作,
4,报错分析开始时,
状态 已归约串 输入串
(s0,#,a1a2? an #)
以后每步的结果可以表示为,
(s0 s1? sm,# X1? Xm,aiai+1? an #)
(s0 s1? sm,# X1? Xm,aiai+1? an #)
分析器根据 ACTION(sm,ai)确定下一步动作
1,若 ACTION(sm,ai)为移进，且 s=GOTO(sm,ai)，则三元式格局变为,
(s0 s1? sms,# X1? Xm ai,ai+1? an #))
2,若 ACTION(sm,ai)为按 A归约，三元式变为,
(s0 s1? sm-rs,# X1? Xm-rA,aiai+1? an #))
此处,s=GOTO(sm-r,A),r为?的长度,?= Xm-r+1? Xm
3,若 ACTION(sm,ai)为 "接受 "，则三元式不再变化，变化过程终止，宣布分析成功,
4,若 ACTION(sm,ai)为 "报错 "，则三元式变化过程终止，
报告错误,
LR分析器示例：
文法 G(E)：
(1) E→E＋ T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→i
ACTION GO TO
状态 i + * ( ) # E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
其 LR分析表为,
假定输入串为 i*i+i,LR分析器的工作过程,
步骤 状态 符号 输入串
(1) 0 # i*i+i#
(2) 05 #i *i+i#
(3) 03 #F *i+i#
(4) 02 #T *i+i#
(5) 027 #T* i+i#
(6) 0275 #T*i +i#
(7) 02710 #T*F +i#
(8) 02 #T +i#
(9) 01 #E +i#
(10) 016 #E+ i#
步骤 状态 符号 输入串
(11) 0165 #E+i #
(12) 0163 #E+F #
(13) 0169 #E+T #
(14) 01 #E #
(15) 接受
E
E
*T
T+
F
F
F
i
ii
定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为 LR文法 。
定义：一个文法，如果能用一个每步最多向前检查 k个输入符号的 LR分析器进行分析，则这个文法就称为 LR(k)文法,
非 LR结构
LR文法不是二义的，二义文法肯定不会是 LR
的。
S? iCtS | iCtSeS
栈 输入
… iCtS e… #
非 LR结构例：某语言的词法分析器将任何标识符都送回单词符号 i。若它的数组和过程调用采用相同的结构，如,A(i,j），则不能识别是过程调用还是数组引用。
在移进 i（ i后不能确定用（ 5)还是（ 7)进行规约非 LR结构思考：关键是（ 1)和（ 6）首部相同，
怎样解决这个问题？
2.5.3.2 LR(0)项目集族和
LR(0)分析表的构造字的前缀,是指字的任意首部，如字 abc的前缀有?,a,ab,abc
活前缀,是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
LR分析过程中,分析栈中符号自底向上应该构成活前缀,只要栈中是活前缀，就说明已扫描过的部分没有错。活前缀配上输入串的剩下部分就构成一个规范句型。
对于一个文法 G,可以构造一个 DFA,它能识别
G的所有活前缀,
文法 G的每个产生式的右部添加一个圆点称为 G的 LR(0)项目如,A?XYZ有四个项目：
A?.XYZ A?X.YZ A?XY.Z
A?XYZ.
A,称为 "归约项目 "
归约项目 S,称为 "接受项目 "
A,a? (a?VT) 称为 "移进项目 "
A,B? (B?VN) 称为 "待约项目 ".
文法 G(S?)
S?→E
E→aA|bB
A→cA|d
B→cB|d
该文法的项目有：
1,S?→·E 2,S?→E· 3,E→·aA
4,E→a·A 5,E→aA· 6,A→·cA
7,A→c·A 8,A→cA· 9,A→·d
10,A→d· 11,E→·bB 12,E→b·B
13,E→bB· 14,B→·cB 15,B→c·B
16,B→cB· 17,B→·d 18,B→d·
构造识别文法所有活前缀的
NFA方法
1.拓广文法
设文法 G的开始符号为 S，增加一条产生式 S?→S，构造一个新文法 G?。
S?是 G?的开始符号，称 G?是 G的 拓广文法 。
拓广文法的主要目的：
让文法只有唯一的,接受,态，即项目
S?→S.。
2,若状态 i为 X?X1 … Xi-1.Xi … Xn,
状态 j为 X?X1 … Xi-1Xi,Xi+1 … Xn,
则从状态 i画一条标记为 Xi的有向边到状态 j；
3,若状态 i为 X.A?,A为非终结符，
则从状态 i画一条?边到所有状态 A?.?。
4.把识别文法所有活前缀的 NFA确定化。
构成识别一个文法活前缀的 DFA的项目集
(状态 )的全体称为文法的 LR(0)项目集规范族 。
6 7 8
9 10
4 53
1 2
11 12 13
14 15 16
1817
a
A
E
b B
B
c A
c
d
识别活前缀的 NFA
识别活前缀的 DFA
0,S?→·E
E→·aA
E→·bB
4:A→c·A
A→·cA
A→·d
2,E→a·A
A→·cA
A→·d
1,S?→E·
3,E→b·B
B→·cB
B→·d
5,B→c·B
B→·cB
B→·d
11,B→d·
9,B→cB·
7,E→bB·
10,A→d·
6,E→aA·
8,A→cA·
c
c
b
E
a
d
Ac
c
d
d
d
B
A
B
假定 I是文法 G?的任一项目集，定义和构造
I的闭包 CLOSURE(I)如下：
1,I的任何项目都属于 CLOSURE(I)；
2,若 A→?·B?属于 CLOSURE(I)，那么，
对任何关于 B的产生式 B→?，项目 B→·?也属于 CLOSURE(I)；
3,重复执行上述两步骤直至 CLOSURE(I)
不再增大为止。
LR(0)项目集规范族的构造设 I是一个项目集,X是一个文法符号，引入状态转换函数 GO(I,X)描述在状态集合 I在识别 X后转换后的新状态，定义为：
GO(I,X)＝ CLOSURE(J)
其中
J＝ {任何形如 A→?X·?的项目 | A→? ·X?属于 I}。
状态转换函数 GO
构造文法 G的拓广文法 G?的 LR(0)项目集规范族算法：
PROCEDURE ITEMSETS(G?)；
BEGIN
C:={CLOSURE({S·S})}；
REPEAT
FOR C中每个项目集 I和 G?的每个符号 X DO
IF GO(I,X)非空且不属于 C THEN
把 GO(I,X)放入 C族中 ;
UNTIL C 不再增大
END
转换函数 GO把项目集连接成一个 DFA转换图,
文法 G(S?)
S?→E
E→aA|bB
A→cA|d
B→cB|d
I0= closure({S?→·E}) = {S?→·E,E→·aA,E→·bB}
GO(I0,E)= closure(J) = closure({S?→E·})=I1
GO(I0,a)= closure(J)=closure({E→a·A})
={ E→a·A,A→·cA,A→·d} )=I2
GO(I0,b)= closure(J) = closure({E →b.B})
=｛ E→b·B,B→·cB,B→·d}=I3
0,S?→·E
E→·aA
E→·bB
4:A→c·A
A→·cA
A→·dc
5,B→c·B
B→·cB
B→·d
c
3,E→b·B
B→·cB
B→·d
b
1,S?→E·E
2,E→a·A
A→·cA
A→·d
a
11,B→d·d
8,A→cA·A
c
c
d
10,A→d·
d
d
9,B→cB·B
6,E→aA·A
7,E→bB·B
LR(0)分析表的构造假若一个文法 G的拓广文法 G?的活前缀识别自动机中的每个状态 (项目集 )不存在任何下述情况：
1) 既含移进项目又含归约项目
（移进－归约冲突）
2) 含有多个归约项目
（归约－归约冲突）
则称 G是一个 LR(0)文法 。
构造 LR(0)分析表的算法令每个项目集 Ik的下标 k作为分析器的状态，包含项目 S?→·S的集合 Ik的下标 k为分析器的初态。
分析表的 ACTION和 GOTO子表构造方法：
1,若项目 A→?·a?属于 Ik且 GO(Ik,a)＝ Ij,a为终结符，
则置 ACTION[k,a] 为,sj”。
2,若项目 A→?·属于 Ik，那么，对任何终结符 a(或结束符 #)，置 ACTION[k,a]为,rj”(假定产生式 A→?是文法 G?的第 j个产生式 )。
3,若项目 S?→S·属于 Ik，则置 ACTION[k,#]为,acc”。
4,若 GO(Ik,A)＝ Ij,A为非终结符，则置 GOTO[k,A]=j。
5,分析表中凡不能用规则 1至 4填入信息的空白格均置上,报错标志,。
上例的 LR(0)分析表为
ACTION GO TO
状态 a b c d # E A B
0 s2 s3 1
1 acc
2 s4 s10 6
3 s5 s11 7
4 s4 s10 8
5 s5 s11
6 r1 r1 r1 r1 r1 9
7 r2 r2 r2 r2 r2
8 r3 r3 r3 r3 r3
9 r5 r5 r5 r5 r5
10 r4 r4 r4 r4 r4
11 r6 r6 r6 r6 r6
例,按上表对 acccd进行分析步骤 状态 符号 输入串
1 0 # acccd#
2 02 #a cccd#
3 024 #ac ccd#
4 0244 #acc cd#
5 02444 #accc d#
6 0244410 #acccd #
7 024448 #acccA #
8 02448 #accA #
9 0248 #acA #
10 026 #aA #
11 01 #E #
2.5.3.3 SLR分析表的构造
LR(0)文法太简单，没有实用价值,
假定一个 LR(0)规范族中含有如下的一个项目集 (状态 )II＝ {X→?·b?,A→?·,B→?·}。
FOLLOW(A) ∩FOLLOW(B)=?，且不包含 b，
那么，当状态 I面临任何输入符号 a时，可以,
1,若 a=b，则移进；
2,若 a?FOLLOW(A),用产生式 A→?进行归约；
3,若 a?FOLLOW(B),用产生式 B→?进行归约；
4,此外，报错。
更一般地，假定 LR(0)规范族的一个项目集
I={A1→?·a1?1,A2→?·a2?2,…,
Am→?·am?m,B1→?·,B2→?·,…,Bn→?·}
如果集合 {a1,…,am},FOLLOW(B1),…,
FOLLOW(Bn)两两不相交 (包括不得有两个
FOLLOW集合有 #)，则：
1,若 a是某个 ai,i=1,2,…,m，则移进；
2,若 a?FOLLOW(Bi),i=1,2,…,n，则用产生式
Bi→?进行归约；
3,此外，报错。
冲突性动作的这种解决办法叫做 SLR(1)解决办法 。
构造 SLR(1)分析表方法,
首先把 G拓广为 G?，对 G?构造 LR(0)项目集规范族 C和活前缀识别自动机的状态转换函数 GO.
然后使用 C和 GO，按下面的算法构造 SLR
分析表：
令每个项目集 Ik的下标 k作为分析器的状态，
包含项目 S?→·S的集合 Ik的下标 k为分析器的初态。
分析表的 ACTION和 GOTO子表构造方法：
1,若项目 A→?·a?属于 Ik且 GO(Ik,a)=Ij,a为终结符，则置
ACTION[k,a]为,sj”；
2,若项目 A→?·属于 Ik，那么，对任何终结符 a，
a?FOLLOW(A)，置 ACTION[k,a]为,rj”；其中，假定 A为文法 G?的第 j个产生式；
3,若项目 S?→S·属于 Ik，则置 ACTION[k,#]为,acc”;
4,若 GO(Ik,A)＝ Ij,A为非终结符，则置 GOTO[k,A]=j；
5,分析表中凡不能用规则 1至 4填入信息的空白格均置上
,出错标志,。
按上述方法构造出的 ACTION与 GOTO表如果不含多重入口，则称该文法为 SLR(1)文法 。
使用 SLR表的分析器叫做一个 SLR分析器 。
每个 SLR(1)文法都是无二义的。但也存在许多无二义文法不是 SLR(1)的,
例 5.11 考察下面的拓广文法：
(0) S?→E
(1) E→E+T
(2) E→T
(3) T→T*F
(4) T→F
(5) F→(E)
(6) F→i
这个文法的 LR(0)项目集规范族为：
I0,S?→·E
E→·E+T
E→·T
T→·T*F
T→·F
F→· (E)
F→·i
I1,S?→E·
E→E·+T
I2,E→T·
T→T·*F
I3,T→F·
I4,F→(·E)
E→·E+T
E→·T
T→·T*F
T→·F
F→· (E)
F→·i
I5,F→i·
I6,E→E+·T
T→·T*F
T→·F
F→·(F)
F→·i
I7,T→T*·F
F→·(E)
F→·i
I8,F→(E·)
E→E·+T
I9,E→E+T·
T→T·*F
I10,T→T*F ·
I11,F→(E)·
I1,I2和 I9都含有,移进－归约,冲突。
FOLLOW(S?）＝｛ #｝ FOLLOW(E)＝ {#,),+}，
I0
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
E
+ T *
T T
i
F
( i
( F
E
(F
i
+
F*
(
)
AC TION GO TO
状态 i + * ( ) # E T F
0 s5 s4 1 2 3
1 s6 a cc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s1 1
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
其分析表如下,
非 SLR文法示例：考虑如下文法：
(0) S?→S
(1) S→L=R
(2) S→R
(3) L→*R
(4) L→i
(5) R→L
计算 FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。
这个文法的 LR(0)项目集规范族为：
I0,S?→·S
S→·L=R
S→·R
L→·*R
L→·i
R→·L
I1,S?→S·
I2,S→L·=R
R→L·
I3,S→R·
I4,L→*·R
R→·L
L→·*R
L→·i
I5,L→i·
I6,S→L=·R
R→·L
L→·*R
L→·i
I7,L→*R·
I9,S→L=R·
I8,R→L·
R
S = i
L
R * L
*
* R
i
i L
活前缀识别器
1
2
0
3
4
6
7
5
8
9
在 SLR方法中,如果项目集 Ii含项目 A.而且下一输入符号 a?FOLLOW(A),则状态 i
面临 a时,可选用,用 A归约,动作。但在有些情况下,当状态 i显现于栈顶时,栈里的 活前缀 未必允许把?归约为 A，因为可能根本就不存在一个形如,?Aa”的规范句型。
因此，在这种情况下，用,A”归约不一定合适。
如上例,当状态 2显现于栈顶而且面临输入符号为 ‘ =?时，实际上不能用对栈顶 L
进行归约，因为这个文法不含,R=”为前缀的规范句型。
2.5.3.4 规范 LR分析表的构造我们需要重新定义项目，使得每个项目都附带有 k个终结符。每个项目的一般形式是 [A→?·?,a1a2… ak],这样的一个项目称为一个 LR(k)项目 。项目中的 a1a2… ak 称为它的 向前搜索符串 (或 展望串 )。
向前搜索符串仅对归约项目 [A→?·，
a1a2… ak]有意义。对于任何移进或待约项目 [A→?·?,a1a2… ak],，搜索符串
a1a2… ak 没有作用。
归约项目 [A→?·,a1a2… ak]意味着：当它所属的状态呈现在栈顶且后续的 k个输入符号为 a1a2… ak 时，才可以把栈顶上的?归约为
A。
我们只对 k?1的情形感兴趣，向前搜索 (展望 )
一个符号就多半可以确定,移进,或,归约,。为构造有效的 LR(1)项目集族我们需要两个函数 CLOSURE和 GO。
项目集 I 的闭包 CLOSURE(I)构造方法：
1,I的任何项目都属于 CLOSURE(I)。
2,若项目 [A→?·B?,a]属于 CLOSURE(I),B→?
是一个产生式，那么，对于 FIRST(?a) 中的每个终结符 b，如果 [B→·?,b]原来不在
CLOSURE(I)中，则把它加进去。
3,重复执行步骤 2，直至 CLOSURE(I)不再增大为止。
令 I是一个项目集,X是一个文法符号，
函数 GO(I,X)定义为：
GO(I,X)＝ CLOSURE(J)
其中
J＝ {任何形如 [A→?X·?,a]的项目
| [A→?·X?,a]?I}
文法 G?的 LR(1)项目集族 C的构造算法：
BEGIN
C:={CLOSURE({[S?→·S,#]})};
REPEAT
FOR C中每个项目集 I和 G?的每个符号 X DO
IF GO(I,X)非空且不属于 C,THEN
把 GO(I,X)加入 C中
UNTIL C不再增大
END
例 5.13 (5.10)的拓广文法 G( S?)
(0) S?→S
(1) S→BB
(2) B→aB
(3) B→b
LR(1)的项目集 C和函数 GO可构造为,
I0,SS,#
SBB,#
BaB,a/b
Bb,a/b
S I
1,SS?,#
B I
2,S?B? B,#
BaB,a/b
Bb,a/ba
I3,B?a?B,a/b
BaB,a/b
Bb,a/b
b
I4,B?b?,a/b
B
I5,S?BB?,#
a I6,B?a?B,#BaB,#
Bb,#
b
I7,B?b?,#
B
I8,B?aB?,a/b
ab
a
I9,B?aB?,#
Bb
构造 LR(1)分析表的算法。
令每个 Ik的下标 k为分析表的状态，令含有
[S?→·S,#]的 Ik的 k为分析器的初态。
动作 ACTION和状态转换 GOTO构造如下：
1,若项目 [A→?·a?,b]属于 Ik且 GO(Ik,a)＝ Ij，
a为终结符，则置 ACTION[k,a]为,sj”。
2,若项目 [A→?·,a]属于 Ik，则置 ACTION[k,
a]为,rj”；其中假定 A→?为文法 G?的第 j个产生式。
3,若项目 [S?→S·,#]属于 Ik，则置 ACTION[k,#]
为,acc”。
4,若 GO(Ik,A)＝ Ij，则置 GOTO[k,A]=j。
5,分析表中凡不能用规则 1至 4填入信息的空白栏均填上,出错标志,。
按上述算法构造的分析表，若不存在多重定义的入口 (即，动作冲突 )的情形，则称它是文法 G
的一张 规范的 LR(1)分析表 。
使用这种分析表的分析器叫做一个 规范的 LR分析器 。
具有规范的 LR(1)分析表的文法称为一个 LR(1)
文法 。
LR(1)状态比 SLR多，
LR(0)?SLR（ 1）? LR(1)?无二义文法
ACTION GO TO
状态 a b # S B
0 s3 s4 1 2
1 acc
2 s6 s7 5
3 s3 s4 8
4 r3 r3
5 r1
6 s6 s7 9
7 r3
8 r2 r2
9 r2
上例的 LR(1)分析表为,
例,按上表对 aabab进行分析步骤 状态 符号 输入串
0 0 # aabab#
1 03 #a abab#
2 033 #aa bab#
3 0334 #aab ab#
4 0338 #aaB ab#
5 038 #aB ab#
6 02 #B ab#
7 026 #Ba b#
8 0267 #Baa #
9 0269 #BaB #
10 025 #BB #
11 01 #S # acc
例,按上表对 abab进行分析步骤 状态 符号 输入串
0 0 # abab#
1 03 #a bab#
2 034 #ab ab#
3 038 #aB ab#
4 02 #B ab#
5 026 #Ba b#
6 0267 #Bab #
7 0269 #BaB #
8 025 #BB #
9 01 #S # acc
(1) LALR(1)分析的第 1个原则
LR(1)项目的 DFA的 状态核心 是 LR(0)项目的 DFA的一个状态。
(2) LALR(1)分析的第 2个原则（同心转换后仍同心）
若有具有 相同核心 的 LR(1)项目的 DFA的两个状态 s1
和 s2，假设在符号 X上有一个从 s1到状态 t1的转换，则在 X上也有一个从状态 s2到一个状态 t2的转换，且状态
t1和 t2具有相同的核心。
LALR(1)分析
(合并同心集的 LR(1)分析）
LALR(1)项 DFA的构造方法
LALR(1)项 DFA是在 LR(1)项目的 DFA基础上构造出来的。
通过合并具有相同核心的所有状态，同时将那些同心状态的先行符号的并起来获得。
每个 LALR(1)项目都包含一个 LR(0)项目和一个先行记号的集合。
LALR（ 1)项中多先行记号的表示法在先行之间写一个 /来表示多重先行。
因此,LALR(1)项目 [A→a.b,a/b/c] 具有一个由符号 a,b 和 c 组成的先行集合。
LALR(1)分析例,考虑文法,A→(A)|a
(1) A→(A) (2) A→a 找出其中的同心集！
图 5－ 7
LALR(1)分析例,考虑文法,A→(A)|a
(1) A→(A) (2) A→a
图 5－ 9
LALR(1)文法的判断方法定义：
若在 LALR(1)分析算法中没有出现分析冲突则称这个文法为 LALR(1)文法 (LALR(1)
grammar)。
四种文法的相互比较
1.若一个文法是 LR(0)文法，就一定是 SLR(1)文法；
2.若一个文法是 LR(1)文法，则它的 LALR(1)分析表不会有移进 -归约冲突，但却可能有归约 -归约冲突。
3,若一个文法是 SLR(1)文法，那么它肯定就是
LALR(1)文法。
