第 6章
ＬＲ分析程序及其自动构造
6.1 自下而上 分析及其 LR分析概述
6.2 LR (0) 分析
6.3 SLR(1) 分析
6.4 LR（ 1） 分析
6.5 LALR分析
6.6 使用二义文法自下而上分析算法 能力强 构造复杂最常用和最有效的模型 ----移进归约 (动作）
总控程序 output
Input#
…
栈状态 文法符号 分析表产生式表将输入分成两部分：未消化和半消化的总控程序 output
Input#未消化半消化的分析表产生式表
S –> E E –> T | E + T T –> int | (E)
Reduce,如能找到一产生式 A –> w 且栈中的内容是 qw
(q 可能为空 ),则可以将其归约为 qA.即倒 过来用这个产生式,
如上例,若栈中内容是 (int,我们使用产生式 T–> int
柄把 栈中内容归约为 (T
Shift,如不能执行一个归约且在未消化的输入中还有
token,就把它从输入移到栈中,
如上例,假定栈中内容是 (,输入中还有 int+int)#.不能对 ( 执行一个归约，因为它不和任何产生式的右端匹配,所以把输入的第一个符号移到栈中,于是栈中内容是 (int,而余留的输入是 +int)#,
Reduce的一个特殊情况：栈中的全部内容
w归约为开始符号 S （ 即施用 S –> w）,
且没有余留输入了，意味着已成功分析了整个输入串,
移进归约分析中还会出现一种情况，就是出错，比如当前的 token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误,
STACK REMAINING INPUT PARSER ACTION
1 (int + int)# Shift
2 ( int + int)# Shift
3 (int + int)# Reduce,T –> int
4 (T + int)# Reduce,E –> T
5 (E + int)# Shift
6 (E + int)# Shift
7 (E + int )# Reduce,T –> int
8 (E + T )# Reduce,E –> E + T
9 (E )# Shift
10 (E) # Reduce,T –> (E)
11 T # Reduce,E –> T
12 E # Reduce,S –> E
13 S #
8 (E + T )# Reduce:E –> E + T
9 why?不用 E –> T
9 (E ) #
若使用了 E –> T,在栈中形成的 (E+E不是规范句型的 活前缀 （ viable prefixes）
（ E+E不能和任何产生式的右端匹配 （ E+E） 不是规范句型活前缀 是规范句型（右句型）的前缀，但不超过句柄
移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导 规范句型 规范归约最右推导：在推导的任何一步 α?β,其中 α,β 是句型，都是对 α 中的最右非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
G[S],S→E E→E+T|T T→(E)|int
S?E?T?(E)?(E+T)?(E+int)
(T+int)?(int+int)
规范归约假定 α 是 G的一个句子，称序列 α n,α n-1 …,α 0是 α 的一个 规范归约如果该序列满足：
（ 1） α n = α
（ 2） α 0为文法的开始符号
（ 3）对任何 j,0<j<=n,α j-1是从 α j经把句柄替换为相应产生式的左部而得到的文法要求
shift-reduce or reduce-reduce 冲突（ conflicts）
分析程序不能决定是 shift 还是 reduce
或者分析程序归约时有多个产生式可选例子 （ dangling else）,
S –> if E then S | if E then S else S
如输入 if E then if E then S else S
分析某一时刻，栈的内容,if E then if E then S
而 else 是下一 token 归约还是移进？
特定的一种 shift-reduce实现技术
ＬＲ分析
L
R 最右推导
分析器模型和分析算法
ＬＲ 分析特征讨论
ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 文法符号
ACTION GOTO
LR分析表产生式表
ACTION GOTO
a c e b d # S A B
0 S2 1
1 acc
2 S4 3
3 S5 S6
4 r2 r2 r2 r2 r2 r2
5 S8 7
6 r3 r3 r3 r3 r3 r3
7 S9
8 r4 r4 r4 r4 r4 r4
9 r1 r1 r1 r1 r1 r1
LR分析算法
置 ip指向输入串 w的第一个符号
– 令 S为栈顶状态
– a是 ip指向的符号
– 重复 begin
– if ACTION[S,a]=Sj
– then begin PUSH j,a(进栈 )
– ip 前进 (指向下一输入符号 )
– end
– else if ACTION[S,a]=rj (第 j条产生式为 A)
ＬＲ分析程序
then begin
pop |?| 项
令当前栈顶状态为 S’
push GOTO[S’,A]和 A(进栈 )
end
else if ACTION[s,a]=acc
then return (成功）
else error
– end.重复
ＬＲ分析程序
例,
– G[S],S?a A c B e [1]
– A?b[2]
– A?Ab[3]
– B?d[4]
w=abbcde#
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2 goto(2,A)
4 023 #aA s6
5 0236 #aAb cde# r3
6 023 #aA s5
7 0235 #aAc de# s8
8 02358 #aAcd e# r4
9 02357 #aAcB s9
10 023579 #aAcBe # r1
11 01 #S acc
文法 G[S]：
(1) S → aAcBe
(2) A → b
(3) A → Ab
(4) B → d
a b b c d e
步骤 符号栈 输入符号串 动作
1） # abbcde# 移进
2） #a bbcde# 移进
A
3） #ab bcde# 归约 (A→ b)
4） #aA bcde# 移进
A
5） #aAb cde# 归约 (A→ Ab)
6） #aA cde# 移进
7） #aAc de# 移进
B
8） # aAcd e# 归约 (B→ d)
9） #aAcB e# 移进
11） #S # 接受
S
10） #aAcBe # 归约符号串 abbcde是否是 G[S]的子对输入串 abbcde#的移进 -规约分析过程
S?aAcBe? aAcde? aAbcde? abbcde
步骤 符号栈 输入符号串 动作
1） # abbcde# 移进 0 S2
2） #a bbcde# 移进 02 S4
4） #aA bcde# 移进 023 S6
6） #aA cde# 移进 023 S5
7） #aAc de# 移进 0235 S8
9） #aAcB e# 移进 02357 S9
11） #S # 接受 01 acc
对输入串 abbcde#的 LR分析过程
3） #ab bcde# 归约 (A→ b) 024 r2 3
5） #aAb cde# 归约 (A→ Ab) 0236 r3 3
8） # aAcd e# 归约 (B→ d) 02358 r4 7
10） #aAcBe # 归约 (S→ aAcBe) 023579 r1 1
AC T I O N GO T O
a c e b d # S A B
0 S
2
1
1 a cc
2 S
4
3
3 S
5
S
6
4 r
2
r
2
r
2
r
2
r
2
r
2
5 S
8
7
6 r
3
r
3
r
3
r
3
r
3
r
3
7 S
9
8 r
4
r
4
r
4
r
4
r
4
r
4
9 r
1
r
1
r
1
r
1
r
1
r
1
状态栈 ACTION GOTO
文法 G[S]：
(1) S → aAcBe
(2) A → b
(3) A → Ab
(4) B → d
Si:移进，将状态 i和 输入符 进栈
ri:归约，用第 i个产生式归约，同时状态栈与符号栈退出相应个符号，并把 GOTO表相应状态和第 i
个产生式的 左部 非终结 符入栈。
ＬＲ分析程序
推导过程
– S?aAcBe[1]?aAcd[4]e[1]?aAb[3]cd[4]e[1]
–?ab[2]b[3]cd[4]e[1]
规约时在栈里的句型的前缀 规约前可在栈里的规范句型 (不含句柄 )
的前缀
– ab[2] a
– aAb[3] a,aA
– aAcd[4] a,aA,aAc
– aAcBe[1] a,aA,aAc,aAcB
R
ＬＲ分析程序
LR 文法
对于一个 cfg 文法,如果能够构造一张 LR
分析表,使得它的每一个入口均是唯一的
（ Sj,rj,acc,空白 ）,则称该 cfg 是 LR 文法,
ＬＲ分析
特征,
–,规范的
–,符号栈中的符号是规范句型的前缀,
且不含句柄以后的任何符号 (活前缀 )
–,分析决策依据 ―― 栈顶状态和现行输入符号,？ 识别活前缀的 DFA.
四种技术
– LR(0) SLR(1) LR(1) LALR(1)
LR(0) 分析
LR(0)文法能力最弱，理论上最重要
存在 FA 识别活前缀
识别活前缀的 DFA如何构造
（ LR(0)项目集规范族的构造）
LR(0)分析表的构造
ＬＲ分析
活前缀
G=(Vn,Vt,P,S),若有 S’? α Aω? α β ω,
γ 是 αβ的前缀,则称是文法 G的活前缀,
其中 S’是对原文法扩充 (S’?S)增加的非终结符,
为使 S’不出现在任何产生式的右部,
如 G=({S},{a},{S?Sa,S?a},S)
RR
*
识别活前缀的 DFA
启示,LR分析使用的信息之一是句柄左部的内容,
定义 (非终结符的左文 )
LC(A)={?| S’A?,V*,Vt*},
对拓广文法的开始符号 S’:
LC(S’)={?}
若 BA? 则,LC(A)?LC(B).{?}
R
*
G[S],(0) S’?S (1) S?a A c B e
(2)A?b (3) A?Ab (4)B?d
每个非终结符的左文方程组
LC(S’)={?}
LC(S)=LC(S’).{?}
LC(A)=LC(S).{a}? LC(A){?}
LC(B)=LC(S).{aAc}
化简为：
[S’]=?
[S]=[S’]
[A]=[S]a+[A]
[B]=[S]aAc
用代入法求解得：
[S’]=?
[S]=?
[A]=a+[A]
[B]=aAc
令?={[S’],[S],[A],[B],a，
A,c}
则方程两边都是?上的正规式而 [A]=a+[A] 即为 [A]=a | [A] 由正规式所表示的正规集
得,[A]=a
G[S],(0) S’?S (1) S?a A c B e
(2)A?b (3) A?Ab (4)B?d
定义 (产生式的 LR(0)左文 )
LR(0)LC(A)={?|? =且 S’A,Vt*}
有推论,LR(0)LC(A)=LC(A).{?}
则有,
LR(0)LC(S’?S)=S
LR(0)(LC(S?aAcBe)=aAcBe
LR(0)LC(A?b)=ab
LR(0)LC(A?Ab)=aAb
LR(0)LC(B?d)=aAcd (? =Vn?Vt)上的正规式
R
*
R
x 5
④
⑧
9
①
2
14
3
0
6 7
10 11 12
1615
⒀
17 18 ⒆
S
a
a
a
a A
A
A
b
c
c
b
d
eB
DFA
x 2 3
5 7
8
9
6
41
A ba
S b c
B e
d
构造 LR(0)项目集规范族
LR(0)项目集规范族 (构成识别一个文法的活前缀的
DFA的状态的全体 )。
LR（ 0） 项目或配置 （ item or configuration）,
---在右端某一位置有圆点的 G的产生式
A? xyz A?.xyz
A?x.yz
A?xy.z
A?xyz.
如,S→aAd
S→,aAd S→a,Ad S→aA,d S→aAd,
活前缀与句柄的关系：
G[S]:
若 S => α Aω =>α β ω r是 αβ的前缀，则
称 r是 G的一个活前缀
1.活前缀已含有句柄的全部符号，表明产生式 A→ β 的右部 β 已出现在栈顶
2.活前缀只含句柄的一部分符号表明 A→ β 1β 2的右部子串 β 1已出现在栈顶，期待从输入串中看到 β 2推出的 符号
3,活前缀不含有句柄的任何符号，此时期望 A→ β 的右部所推出的符号串
R
*
R
活前缀,与句柄,与 LR(0)项目
为刻划这种分析过程中的文法 G的每一个产生式的右部符号已有多大一部分被识别 （ 出现在栈顶 ） 的情况,分别用标有圆点的产生式来指示位置 。
A→ β,刻划产生式 A→ β 的 右部 β 已出现在栈顶
A→ β 1,β 2 刻划 A→ β 1β 2的右部子串 β 1已出现在栈顶,
期待从输入串中看到 β 2推出的 符号
A→,β 刻划没有句柄的任何符号 在栈顶,此时期望 A→ β
的右部所推出的符号串
对于 A→ ε 的 LR(0)项目只有 A→,
构造识别活前缀的 DFA
LR（ 0） 项目集的闭包Ｃ LOSURE,GO 函数,
function CLOSURE (I); /* I 是项目集 */
{ J:= I;
repeat for J 中的每个项目 A,B? 和产生式
B,若 B?,? 不在 J中
do 将 B?,? 加到 J中
until 再没有项目加到 J中
return J
};
GO (I,x)=== CLOSURE(J) ;
其中,I:项目集,x,文法符号,
J={任何形如 A x,? 的项目 |A,xI}
LR（ 0） 项目集的闭包Ｃ LOSURE
若当前处于 A –> X?YZ刻划的情况，期望移进
First(Y)中的某些符号，假如有产生式
Y –> u | w,那么 Y –>?u和 Y –>?w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况,
A –> X?YZ
Y –>?u
Y –>?w
这三个项目对应移进归约分析的同一个状态,这三个项目构成一个 配置集,对应每个配置集，
分析表将有一个状态,
LR(0)项目集规范族
计算 LR（ 0） 项目集规范族
C={I0,I1,..,In }
Procedure itemsets(G’);
Begin C,= { CLOSURE ({S’?.S})}
Repeat
For C 中每一项目集 I和每一文法符号 x
Do if GO(I,x) 非空且不属于 C
Then 把 GO(I,x) 放入 C中
Until C 不再增大
End;
例：文法 G:
（ 0） S`→E (1) E→aA (2) E→bB
(3) A→cA (4) A→d (5) B→cB
(7) B→d
LR(0) 项目集规范族（ 识别 G的活前缀的 DFA)：
I0,S`→,E I1,S`→E,I2,E→a,A
E→,aA A→.cA
E→,bB A→,d
I3,E→b,B I4:A→c,A I5:
B→,cB A→,cA B→c,B
B→,d A →,d B→,cB
B→,d
I6,I7,I8:
E→aA,E→bB,A→cA,
I9,B→cB,I10,A→d,I11,B→cB,
LR(0)分析表的构造
假定 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,因此,G` 的 LR(0)分析表含有状态 0,1,……,n。 令那个含有项目 S`→,S的 Ik的下标 k为初态 。 ACTION和 GOTO可按如下方法构造：
若项目 A→ α,aβ 属于 Ik且 GO (Ik,a)= Ij,a为终结符,则置 ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为
,sj”;
若项目 A→ α,属于 Ik,那么,对任何终结符 a,置
ACTION[k,a]为,用产生式 A→ α 进行规约,,简记为
,rj”;其中,假定 A→ α 为文法 G`的第 j个产生式；
若项目 S`→S,属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
分析表中凡不能用规则 1至 4填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法 G
的一张 LR(0)表。具有 LR(0)表的文法 G称为一个 LR
（ 0） 文法。
LR(0)文法是无二义的。
ACTION GOTO
a c b 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 9
6 r1 r1 r1 r1 r1
7 r2 r2 r2 r2 r2
8 r3 r3 r3 r3 r3 r3
9 r5 r5 r5 r5 r5 r5
10 r4 r4 r4 r4 r4 r4
11 r6 r6 r6 r6 r6 r6
LR(0)项目根据 圆点所在的位置 和 圆点后 是 终结符 还是 非终结符 或为 空 把项目分为以下几种：
移进 项目，形如 A → a? a是 终结符,?,V* 以下同待约 项目，形如 A → B?
归约 项目，形如 A →
接受 项目，形如 S’ → S?
A→ ε 的 LR(0)项目只有 A→? 是 归约 项目作用？
例,（ 0） S`→S (1) S→rD
(2) D→D,i (3) D→i
LR（ 0） 项目
1,S`→,S 2,S`→S,3,S→,rD
4,S→r,D 5,S→rD,6,D→,D,i
7,D→D,,i 8,D→D,,i 9,D→D,i,
10,D→,i 11,D→i,
NFA
1 3 10
7 8
5
9
11
2
i?
S r
r
D
4 6 D?,
例,（ 0） S`→S (1) S→rD
(2) D→D,i (3) D→i
LR（ 0） 项目集规范族
I0,S`→,S I3,S→r D．
S→,r D D→D,i
I1,S`→S,I4,D→i,
I2,S→r,D I5,D→D,i
D→,D i I6,D→Di,
D→,i
其中 I3中含有移进 /归约冲突
文法不是 LR(0)的,如何解决？
SLR(1)技术
若 LR(0) 项目集规范族中有项目集 IK含 移进 /归约 归约 /归约
冲突：
IK,{,..A→ α,bβ,P,,Q,,…}
若 FOLLOWQA)? FOLLOW(P) =?
FOLLOWP(P)? { b } =?
FOLLOW(Q)? { b} =?
则解决冲突的 SLR(1)技术：
action [ k,b ] = 移进
对 a?FOLLOW (P) 则 action [ k,a ] =用 P归约
对 a?FOLLOW (Q) 则 action [ k,a ] =用 Q 归约
能用 SLR(1)技术 解决冲突的文法称为 SLR(1)文法。
SLR(1)文法是无二义的。
SLR表
假定 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,因此,
G` 的 SLR分析表含有状态 0,1,……,n。 令那个含有项目 S`→,S的 Ik的下标 k
为初态 。 函数 ACTION和 GOTO可按如下方法构造：
– 若项目 A→ α,aβ 属于 Ik且 GO (Ik,a)= Ij,a为终结符,则置
ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为,sj”;
– 若项目 A→ α,属于 Ik,那么,对任何输入符号 a,a∈FOLLOW(A),置
ACTION[k,a]为,用产生式 A→ α 进行规约,,简记为,rj”;其中,
假定 A→ α 为文法 G`的第 j个产生式；
– 若项目 S`→S,属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
– 若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
– 分析表中凡不能用规则 1至 4填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表,如果每个入口不含多重定义,则称它为文法 G的一张 SLR表 。 具有 SLR表的文法 G称为一个 SLR（ 1） 文法 。 数字 1的意思是,在分析过程中顶多只要向前看一个符号 。
实数说明文法的 SLR（ 1） 分析表
状态 ACTION GOTO
r,i # S D．
0 S2 1
1 acc
2 S4 3
3 r1 S5 r1 r1
4 r3 r3 r3 r3
5 S6
6 r2 r2 r2 r2
SLR
例：文法 G:
（ 0） S`→S (1) S→aAd (2) S→bAc
(3) S→aec (4) S→bed (5) A→e
LR(0) 项目集规范族（ 识别 G的活前缀的 DFA)：
I0,S`→,S I1,S`→S,I2,S→a,Ad
S→,aAd S→a,ec
S→,bAc A→,e
S→,aec
S→,bed
SLR
I3,S→b,Ac I4,I5:
S→b,ed S→aA,d S→ae,c
A→,e A→e,
I6,I7,I8:
S→bA,c S→be,d S→aAd,
A→e,
I9,S→aec,I10,S→bAc,I11,S→bed,
ACTION GOTO
a c e b d # S A
0 S2 S3 1
1 acc
2 S5 4
3 S7 6
4 S8
5 r5 r5S9 r5 r5 r5 r5
6 S10
7 r7 r7 r7 r7 r7 S11 r7
8 r1 r1 r1 r1 r1 r1
9 r3 r3 r3 r3 r3 r3
10 r2 r2 r2 r2 r2 r2
11 r4 r4 r4 r4 r4 r4
I5,S→ae,c
A →e,
S`==>S==>aAd==>aed
S`==>S==>aec
I7,S →be,d
A→e,
S`==>S==>bAc==>bec
S`==>S==>bed
？ 信息 哪些输入符号能跟在句柄之后
R RR
R R
R R R
R R
Another example
G[S]:
(0) S`→ S (1) S→L=R (2) S→R
(3) L→ *R (4) L→i (5) R→L
LR(0)项目集规范族和 G0函数
I1 S’ →S,I6
I0 S`→,S I2 S→L,=R S →L=,R L →,*R
S→,L=R R→ L,R→,L L→,i
S→,R
L→,*R I3
L→,i S→R,
R→,L I4
L→*,R I7
I5 R→,L L→*R,
L→i,L→,*R
L→,i I8 R→L,
(1)不是 LR(0)文法
∵ I2 S→L,=R R→ L,中存在移进 /归约冲突
（ 2） SLR能否 解决 I2中的冲突
∴ FOLLOW（ R） ={#,=}与 {=}交不为空 不是 SLR（ 1） 文法
S→L.=R R→L,若用 R→L 归约 则形成
R=… 而 R=不是活前缀?早知此信息
向前搜索符 —— LR（ 1） 方法
若 A,B I
则 B?,? （ B 是一产生式）? I
把 FIRST（ B） 中的符号作为用 B 归约的搜索符
LR（ 1） 项目
– [ A,?,a ]
LR（ K） 项目
– [ A,?,a1 a2 …… a K ]
构造 LR(1)项目集 规范族和 G0函数
– closure(I)按如下方式构造
(1) I的任何项目属 closure(I)；
(2)若 [A→ β 1,Bβ 2,a]∈ closure(I),B→ δ 是一产生式，那么对于 FIRST(β 2a)中的每个终结符 b,如果 [B→,δ,b]不在 closure(I)
中，则把它加进去；
(3)重复（ 1）（ 2），直至 closure(I)不再增大。
– GO函数：
若 I是一个项目集,X是一个文法符号
GO(I,X)= closure(J)
其中 J={ 任何形如 [A→ α X,β,a]的项目 ∣ [A→ α,Xβ,a]∈I}
LR(I)项目规范族 C的构造算法类同 LR(0)的，只是初始时：
C={ closure({[S`→,S,#]})};
LR(1)项目集规范族
I0,S`→,S,# I5,S →ae,c,#
S →,aAd,# A →e,,d
S →,bAc,# I6,S →bA,c,#
S →,aec,# I7,S →be,d,#
S →,bed,# A →e,,c
I1,S`→S,,# I8,S→aAd,,#
I2,S` →a,Ad,# I9,S →aec,,#
S →a,ec,# I10,S →bAc,,#
A →,e,d I11,S →bed,,#
I3,S →b,Ac,#
S →b,ed,#
A→,e,c
I4,S →aA,d,#
LR(1)项目集规范族
I1,S`→S,,# I9,S→ L=R.,#
I2,I6,S→L=,R,#
I0,S`→,S,# S→L,=R,# R→,L,#
S→,L=R,# R→L,,# L→,*R,#
S→,R,# I3,L→,i,#
L→,*R,=/# S→R,,#
L→,i,=/# I4,I11:
R→,L,# L→*,R,=/# L→*,R,#
L→,*R,=/# R→,L,#
I5,L→i,,=/# L→,i,=/# L→,*R,#
R→,L,=/# L→,i,#
I7 L→*R,,=/# I8 R→L,,#/= I10 I13
I12,L→i,R→L,,# L→*R,,#
LR(1)分析表的构造
若项目 [A→ α,A]属于 Ik,那么 置 ACTION[k,a]为“用产生式
A→ α 进行规约,，简记为,rj”;其中，假定 A→ α 为文法 G`的第
j个产生式；
At the heart of the table construction is the notion
of an LR(0) configuration or item,A configuration
is a production of the grammar with a dot at some
position on its right side,For example,A –> XYZ
gives four items:
A –>?XYZ
A –> X?YZ
A –> XY?Z
A –> XYZ?
ＬＲ分析程序及其自动构造
6.1 自下而上 分析及其 LR分析概述
6.2 LR (0) 分析
6.3 SLR(1) 分析
6.4 LR（ 1） 分析
6.5 LALR分析
6.6 使用二义文法自下而上分析算法 能力强 构造复杂最常用和最有效的模型 ----移进归约 (动作）
总控程序 output
Input#
…
栈状态 文法符号 分析表产生式表将输入分成两部分：未消化和半消化的总控程序 output
Input#未消化半消化的分析表产生式表
S –> E E –> T | E + T T –> int | (E)
Reduce,如能找到一产生式 A –> w 且栈中的内容是 qw
(q 可能为空 ),则可以将其归约为 qA.即倒 过来用这个产生式,
如上例,若栈中内容是 (int,我们使用产生式 T–> int
柄把 栈中内容归约为 (T
Shift,如不能执行一个归约且在未消化的输入中还有
token,就把它从输入移到栈中,
如上例,假定栈中内容是 (,输入中还有 int+int)#.不能对 ( 执行一个归约，因为它不和任何产生式的右端匹配,所以把输入的第一个符号移到栈中,于是栈中内容是 (int,而余留的输入是 +int)#,
Reduce的一个特殊情况：栈中的全部内容
w归约为开始符号 S （ 即施用 S –> w）,
且没有余留输入了，意味着已成功分析了整个输入串,
移进归约分析中还会出现一种情况，就是出错，比如当前的 token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误,
STACK REMAINING INPUT PARSER ACTION
1 (int + int)# Shift
2 ( int + int)# Shift
3 (int + int)# Reduce,T –> int
4 (T + int)# Reduce,E –> T
5 (E + int)# Shift
6 (E + int)# Shift
7 (E + int )# Reduce,T –> int
8 (E + T )# Reduce,E –> E + T
9 (E )# Shift
10 (E) # Reduce,T –> (E)
11 T # Reduce,E –> T
12 E # Reduce,S –> E
13 S #
8 (E + T )# Reduce:E –> E + T
9 why?不用 E –> T
9 (E ) #
若使用了 E –> T,在栈中形成的 (E+E不是规范句型的 活前缀 （ viable prefixes）
（ E+E不能和任何产生式的右端匹配 （ E+E） 不是规范句型活前缀 是规范句型（右句型）的前缀，但不超过句柄
移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导 规范句型 规范归约最右推导：在推导的任何一步 α?β,其中 α,β 是句型，都是对 α 中的最右非终结符进行替换最右推导被称为规范推导。
由规范推导所得的句型称为规范句型
G[S],S→E E→E+T|T T→(E)|int
S?E?T?(E)?(E+T)?(E+int)
(T+int)?(int+int)
规范归约假定 α 是 G的一个句子，称序列 α n,α n-1 …,α 0是 α 的一个 规范归约如果该序列满足：
（ 1） α n = α
（ 2） α 0为文法的开始符号
（ 3）对任何 j,0<j<=n,α j-1是从 α j经把句柄替换为相应产生式的左部而得到的文法要求
shift-reduce or reduce-reduce 冲突（ conflicts）
分析程序不能决定是 shift 还是 reduce
或者分析程序归约时有多个产生式可选例子 （ dangling else）,
S –> if E then S | if E then S else S
如输入 if E then if E then S else S
分析某一时刻，栈的内容,if E then if E then S
而 else 是下一 token 归约还是移进？
特定的一种 shift-reduce实现技术
ＬＲ分析
L
R 最右推导
分析器模型和分析算法
ＬＲ 分析特征讨论
ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 文法符号
ACTION GOTO
LR分析表产生式表
ACTION GOTO
a c e b d # S A B
0 S2 1
1 acc
2 S4 3
3 S5 S6
4 r2 r2 r2 r2 r2 r2
5 S8 7
6 r3 r3 r3 r3 r3 r3
7 S9
8 r4 r4 r4 r4 r4 r4
9 r1 r1 r1 r1 r1 r1
LR分析算法
置 ip指向输入串 w的第一个符号
– 令 S为栈顶状态
– a是 ip指向的符号
– 重复 begin
– if ACTION[S,a]=Sj
– then begin PUSH j,a(进栈 )
– ip 前进 (指向下一输入符号 )
– end
– else if ACTION[S,a]=rj (第 j条产生式为 A)
ＬＲ分析程序
then begin
pop |?| 项
令当前栈顶状态为 S’
push GOTO[S’,A]和 A(进栈 )
end
else if ACTION[s,a]=acc
then return (成功）
else error
– end.重复
ＬＲ分析程序
例,
– G[S],S?a A c B e [1]
– A?b[2]
– A?Ab[3]
– B?d[4]
w=abbcde#
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2 goto(2,A)
4 023 #aA s6
5 0236 #aAb cde# r3
6 023 #aA s5
7 0235 #aAc de# s8
8 02358 #aAcd e# r4
9 02357 #aAcB s9
10 023579 #aAcBe # r1
11 01 #S acc
文法 G[S]：
(1) S → aAcBe
(2) A → b
(3) A → Ab
(4) B → d
a b b c d e
步骤 符号栈 输入符号串 动作
1） # abbcde# 移进
2） #a bbcde# 移进
A
3） #ab bcde# 归约 (A→ b)
4） #aA bcde# 移进
A
5） #aAb cde# 归约 (A→ Ab)
6） #aA cde# 移进
7） #aAc de# 移进
B
8） # aAcd e# 归约 (B→ d)
9） #aAcB e# 移进
11） #S # 接受
S
10） #aAcBe # 归约符号串 abbcde是否是 G[S]的子对输入串 abbcde#的移进 -规约分析过程
S?aAcBe? aAcde? aAbcde? abbcde
步骤 符号栈 输入符号串 动作
1） # abbcde# 移进 0 S2
2） #a bbcde# 移进 02 S4
4） #aA bcde# 移进 023 S6
6） #aA cde# 移进 023 S5
7） #aAc de# 移进 0235 S8
9） #aAcB e# 移进 02357 S9
11） #S # 接受 01 acc
对输入串 abbcde#的 LR分析过程
3） #ab bcde# 归约 (A→ b) 024 r2 3
5） #aAb cde# 归约 (A→ Ab) 0236 r3 3
8） # aAcd e# 归约 (B→ d) 02358 r4 7
10） #aAcBe # 归约 (S→ aAcBe) 023579 r1 1
AC T I O N GO T O
a c e b d # S A B
0 S
2
1
1 a cc
2 S
4
3
3 S
5
S
6
4 r
2
r
2
r
2
r
2
r
2
r
2
5 S
8
7
6 r
3
r
3
r
3
r
3
r
3
r
3
7 S
9
8 r
4
r
4
r
4
r
4
r
4
r
4
9 r
1
r
1
r
1
r
1
r
1
r
1
状态栈 ACTION GOTO
文法 G[S]：
(1) S → aAcBe
(2) A → b
(3) A → Ab
(4) B → d
Si:移进，将状态 i和 输入符 进栈
ri:归约，用第 i个产生式归约，同时状态栈与符号栈退出相应个符号，并把 GOTO表相应状态和第 i
个产生式的 左部 非终结 符入栈。
ＬＲ分析程序
推导过程
– S?aAcBe[1]?aAcd[4]e[1]?aAb[3]cd[4]e[1]
–?ab[2]b[3]cd[4]e[1]
规约时在栈里的句型的前缀 规约前可在栈里的规范句型 (不含句柄 )
的前缀
– ab[2] a
– aAb[3] a,aA
– aAcd[4] a,aA,aAc
– aAcBe[1] a,aA,aAc,aAcB
R
ＬＲ分析程序
LR 文法
对于一个 cfg 文法,如果能够构造一张 LR
分析表,使得它的每一个入口均是唯一的
（ Sj,rj,acc,空白 ）,则称该 cfg 是 LR 文法,
ＬＲ分析
特征,
–,规范的
–,符号栈中的符号是规范句型的前缀,
且不含句柄以后的任何符号 (活前缀 )
–,分析决策依据 ―― 栈顶状态和现行输入符号,？ 识别活前缀的 DFA.
四种技术
– LR(0) SLR(1) LR(1) LALR(1)
LR(0) 分析
LR(0)文法能力最弱，理论上最重要
存在 FA 识别活前缀
识别活前缀的 DFA如何构造
（ LR(0)项目集规范族的构造）
LR(0)分析表的构造
ＬＲ分析
活前缀
G=(Vn,Vt,P,S),若有 S’? α Aω? α β ω,
γ 是 αβ的前缀,则称是文法 G的活前缀,
其中 S’是对原文法扩充 (S’?S)增加的非终结符,
为使 S’不出现在任何产生式的右部,
如 G=({S},{a},{S?Sa,S?a},S)
RR
*
识别活前缀的 DFA
启示,LR分析使用的信息之一是句柄左部的内容,
定义 (非终结符的左文 )
LC(A)={?| S’A?,V*,Vt*},
对拓广文法的开始符号 S’:
LC(S’)={?}
若 BA? 则,LC(A)?LC(B).{?}
R
*
G[S],(0) S’?S (1) S?a A c B e
(2)A?b (3) A?Ab (4)B?d
每个非终结符的左文方程组
LC(S’)={?}
LC(S)=LC(S’).{?}
LC(A)=LC(S).{a}? LC(A){?}
LC(B)=LC(S).{aAc}
化简为：
[S’]=?
[S]=[S’]
[A]=[S]a+[A]
[B]=[S]aAc
用代入法求解得：
[S’]=?
[S]=?
[A]=a+[A]
[B]=aAc
令?={[S’],[S],[A],[B],a，
A,c}
则方程两边都是?上的正规式而 [A]=a+[A] 即为 [A]=a | [A] 由正规式所表示的正规集
得,[A]=a
G[S],(0) S’?S (1) S?a A c B e
(2)A?b (3) A?Ab (4)B?d
定义 (产生式的 LR(0)左文 )
LR(0)LC(A)={?|? =且 S’A,Vt*}
有推论,LR(0)LC(A)=LC(A).{?}
则有,
LR(0)LC(S’?S)=S
LR(0)(LC(S?aAcBe)=aAcBe
LR(0)LC(A?b)=ab
LR(0)LC(A?Ab)=aAb
LR(0)LC(B?d)=aAcd (? =Vn?Vt)上的正规式
R
*
R
x 5
④
⑧
9
①
2
14
3
0
6 7
10 11 12
1615
⒀
17 18 ⒆
S
a
a
a
a A
A
A
b
c
c
b
d
eB
DFA
x 2 3
5 7
8
9
6
41
A ba
S b c
B e
d
构造 LR(0)项目集规范族
LR(0)项目集规范族 (构成识别一个文法的活前缀的
DFA的状态的全体 )。
LR（ 0） 项目或配置 （ item or configuration）,
---在右端某一位置有圆点的 G的产生式
A? xyz A?.xyz
A?x.yz
A?xy.z
A?xyz.
如,S→aAd
S→,aAd S→a,Ad S→aA,d S→aAd,
活前缀与句柄的关系：
G[S]:
若 S => α Aω =>α β ω r是 αβ的前缀，则
称 r是 G的一个活前缀
1.活前缀已含有句柄的全部符号，表明产生式 A→ β 的右部 β 已出现在栈顶
2.活前缀只含句柄的一部分符号表明 A→ β 1β 2的右部子串 β 1已出现在栈顶，期待从输入串中看到 β 2推出的 符号
3,活前缀不含有句柄的任何符号，此时期望 A→ β 的右部所推出的符号串
R
*
R
活前缀,与句柄,与 LR(0)项目
为刻划这种分析过程中的文法 G的每一个产生式的右部符号已有多大一部分被识别 （ 出现在栈顶 ） 的情况,分别用标有圆点的产生式来指示位置 。
A→ β,刻划产生式 A→ β 的 右部 β 已出现在栈顶
A→ β 1,β 2 刻划 A→ β 1β 2的右部子串 β 1已出现在栈顶,
期待从输入串中看到 β 2推出的 符号
A→,β 刻划没有句柄的任何符号 在栈顶,此时期望 A→ β
的右部所推出的符号串
对于 A→ ε 的 LR(0)项目只有 A→,
构造识别活前缀的 DFA
LR（ 0） 项目集的闭包Ｃ LOSURE,GO 函数,
function CLOSURE (I); /* I 是项目集 */
{ J:= I;
repeat for J 中的每个项目 A,B? 和产生式
B,若 B?,? 不在 J中
do 将 B?,? 加到 J中
until 再没有项目加到 J中
return J
};
GO (I,x)=== CLOSURE(J) ;
其中,I:项目集,x,文法符号,
J={任何形如 A x,? 的项目 |A,xI}
LR（ 0） 项目集的闭包Ｃ LOSURE
若当前处于 A –> X?YZ刻划的情况，期望移进
First(Y)中的某些符号，假如有产生式
Y –> u | w,那么 Y –>?u和 Y –>?w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况,
A –> X?YZ
Y –>?u
Y –>?w
这三个项目对应移进归约分析的同一个状态,这三个项目构成一个 配置集,对应每个配置集，
分析表将有一个状态,
LR(0)项目集规范族
计算 LR（ 0） 项目集规范族
C={I0,I1,..,In }
Procedure itemsets(G’);
Begin C,= { CLOSURE ({S’?.S})}
Repeat
For C 中每一项目集 I和每一文法符号 x
Do if GO(I,x) 非空且不属于 C
Then 把 GO(I,x) 放入 C中
Until C 不再增大
End;
例：文法 G:
（ 0） S`→E (1) E→aA (2) E→bB
(3) A→cA (4) A→d (5) B→cB
(7) B→d
LR(0) 项目集规范族（ 识别 G的活前缀的 DFA)：
I0,S`→,E I1,S`→E,I2,E→a,A
E→,aA A→.cA
E→,bB A→,d
I3,E→b,B I4:A→c,A I5:
B→,cB A→,cA B→c,B
B→,d A →,d B→,cB
B→,d
I6,I7,I8:
E→aA,E→bB,A→cA,
I9,B→cB,I10,A→d,I11,B→cB,
LR(0)分析表的构造
假定 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,因此,G` 的 LR(0)分析表含有状态 0,1,……,n。 令那个含有项目 S`→,S的 Ik的下标 k为初态 。 ACTION和 GOTO可按如下方法构造：
若项目 A→ α,aβ 属于 Ik且 GO (Ik,a)= Ij,a为终结符,则置 ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为
,sj”;
若项目 A→ α,属于 Ik,那么,对任何终结符 a,置
ACTION[k,a]为,用产生式 A→ α 进行规约,,简记为
,rj”;其中,假定 A→ α 为文法 G`的第 j个产生式；
若项目 S`→S,属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
分析表中凡不能用规则 1至 4填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法 G
的一张 LR(0)表。具有 LR(0)表的文法 G称为一个 LR
（ 0） 文法。
LR(0)文法是无二义的。
ACTION GOTO
a c b 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 9
6 r1 r1 r1 r1 r1
7 r2 r2 r2 r2 r2
8 r3 r3 r3 r3 r3 r3
9 r5 r5 r5 r5 r5 r5
10 r4 r4 r4 r4 r4 r4
11 r6 r6 r6 r6 r6 r6
LR(0)项目根据 圆点所在的位置 和 圆点后 是 终结符 还是 非终结符 或为 空 把项目分为以下几种：
移进 项目，形如 A → a? a是 终结符,?,V* 以下同待约 项目，形如 A → B?
归约 项目，形如 A →
接受 项目，形如 S’ → S?
A→ ε 的 LR(0)项目只有 A→? 是 归约 项目作用？
例,（ 0） S`→S (1) S→rD
(2) D→D,i (3) D→i
LR（ 0） 项目
1,S`→,S 2,S`→S,3,S→,rD
4,S→r,D 5,S→rD,6,D→,D,i
7,D→D,,i 8,D→D,,i 9,D→D,i,
10,D→,i 11,D→i,
NFA
1 3 10
7 8
5
9
11
2
i?
S r
r
D
4 6 D?,
例,（ 0） S`→S (1) S→rD
(2) D→D,i (3) D→i
LR（ 0） 项目集规范族
I0,S`→,S I3,S→r D．
S→,r D D→D,i
I1,S`→S,I4,D→i,
I2,S→r,D I5,D→D,i
D→,D i I6,D→Di,
D→,i
其中 I3中含有移进 /归约冲突
文法不是 LR(0)的,如何解决？
SLR(1)技术
若 LR(0) 项目集规范族中有项目集 IK含 移进 /归约 归约 /归约
冲突：
IK,{,..A→ α,bβ,P,,Q,,…}
若 FOLLOWQA)? FOLLOW(P) =?
FOLLOWP(P)? { b } =?
FOLLOW(Q)? { b} =?
则解决冲突的 SLR(1)技术：
action [ k,b ] = 移进
对 a?FOLLOW (P) 则 action [ k,a ] =用 P归约
对 a?FOLLOW (Q) 则 action [ k,a ] =用 Q 归约
能用 SLR(1)技术 解决冲突的文法称为 SLR(1)文法。
SLR(1)文法是无二义的。
SLR表
假定 C={I0,I1,……,In},令每个项目集 Ik的下标 k 为分析器的一个状态,因此,
G` 的 SLR分析表含有状态 0,1,……,n。 令那个含有项目 S`→,S的 Ik的下标 k
为初态 。 函数 ACTION和 GOTO可按如下方法构造：
– 若项目 A→ α,aβ 属于 Ik且 GO (Ik,a)= Ij,a为终结符,则置
ACTION[k,a]为,把状态 j和符号 a移进栈,,简记为,sj”;
– 若项目 A→ α,属于 Ik,那么,对任何输入符号 a,a∈FOLLOW(A),置
ACTION[k,a]为,用产生式 A→ α 进行规约,,简记为,rj”;其中,
假定 A→ α 为文法 G`的第 j个产生式；
– 若项目 S`→S,属于 Ik,则置 ACTION[k,#]为,接受,,简记为,acc”;
– 若 GO (Ik,A)= Ij,A为非终结符,则置 GOTO(k,A)=j;
– 分析表中凡不能用规则 1至 4填入信息的空白格均置上,出错标志,。
按上述算法构造的含有 ACTION和 GOTO两部分的分析表,如果每个入口不含多重定义,则称它为文法 G的一张 SLR表 。 具有 SLR表的文法 G称为一个 SLR（ 1） 文法 。 数字 1的意思是,在分析过程中顶多只要向前看一个符号 。
实数说明文法的 SLR（ 1） 分析表
状态 ACTION GOTO
r,i # S D．
0 S2 1
1 acc
2 S4 3
3 r1 S5 r1 r1
4 r3 r3 r3 r3
5 S6
6 r2 r2 r2 r2
SLR
例：文法 G:
（ 0） S`→S (1) S→aAd (2) S→bAc
(3) S→aec (4) S→bed (5) A→e
LR(0) 项目集规范族（ 识别 G的活前缀的 DFA)：
I0,S`→,S I1,S`→S,I2,S→a,Ad
S→,aAd S→a,ec
S→,bAc A→,e
S→,aec
S→,bed
SLR
I3,S→b,Ac I4,I5:
S→b,ed S→aA,d S→ae,c
A→,e A→e,
I6,I7,I8:
S→bA,c S→be,d S→aAd,
A→e,
I9,S→aec,I10,S→bAc,I11,S→bed,
ACTION GOTO
a c e b d # S A
0 S2 S3 1
1 acc
2 S5 4
3 S7 6
4 S8
5 r5 r5S9 r5 r5 r5 r5
6 S10
7 r7 r7 r7 r7 r7 S11 r7
8 r1 r1 r1 r1 r1 r1
9 r3 r3 r3 r3 r3 r3
10 r2 r2 r2 r2 r2 r2
11 r4 r4 r4 r4 r4 r4
I5,S→ae,c
A →e,
S`==>S==>aAd==>aed
S`==>S==>aec
I7,S →be,d
A→e,
S`==>S==>bAc==>bec
S`==>S==>bed
？ 信息 哪些输入符号能跟在句柄之后
R RR
R R
R R R
R R
Another example
G[S]:
(0) S`→ S (1) S→L=R (2) S→R
(3) L→ *R (4) L→i (5) R→L
LR(0)项目集规范族和 G0函数
I1 S’ →S,I6
I0 S`→,S I2 S→L,=R S →L=,R L →,*R
S→,L=R R→ L,R→,L L→,i
S→,R
L→,*R I3
L→,i S→R,
R→,L I4
L→*,R I7
I5 R→,L L→*R,
L→i,L→,*R
L→,i I8 R→L,
(1)不是 LR(0)文法
∵ I2 S→L,=R R→ L,中存在移进 /归约冲突
（ 2） SLR能否 解决 I2中的冲突
∴ FOLLOW（ R） ={#,=}与 {=}交不为空 不是 SLR（ 1） 文法
S→L.=R R→L,若用 R→L 归约 则形成
R=… 而 R=不是活前缀?早知此信息
向前搜索符 —— LR（ 1） 方法
若 A,B I
则 B?,? （ B 是一产生式）? I
把 FIRST（ B） 中的符号作为用 B 归约的搜索符
LR（ 1） 项目
– [ A,?,a ]
LR（ K） 项目
– [ A,?,a1 a2 …… a K ]
构造 LR(1)项目集 规范族和 G0函数
– closure(I)按如下方式构造
(1) I的任何项目属 closure(I)；
(2)若 [A→ β 1,Bβ 2,a]∈ closure(I),B→ δ 是一产生式，那么对于 FIRST(β 2a)中的每个终结符 b,如果 [B→,δ,b]不在 closure(I)
中，则把它加进去；
(3)重复（ 1）（ 2），直至 closure(I)不再增大。
– GO函数：
若 I是一个项目集,X是一个文法符号
GO(I,X)= closure(J)
其中 J={ 任何形如 [A→ α X,β,a]的项目 ∣ [A→ α,Xβ,a]∈I}
LR(I)项目规范族 C的构造算法类同 LR(0)的，只是初始时：
C={ closure({[S`→,S,#]})};
LR(1)项目集规范族
I0,S`→,S,# I5,S →ae,c,#
S →,aAd,# A →e,,d
S →,bAc,# I6,S →bA,c,#
S →,aec,# I7,S →be,d,#
S →,bed,# A →e,,c
I1,S`→S,,# I8,S→aAd,,#
I2,S` →a,Ad,# I9,S →aec,,#
S →a,ec,# I10,S →bAc,,#
A →,e,d I11,S →bed,,#
I3,S →b,Ac,#
S →b,ed,#
A→,e,c
I4,S →aA,d,#
LR(1)项目集规范族
I1,S`→S,,# I9,S→ L=R.,#
I2,I6,S→L=,R,#
I0,S`→,S,# S→L,=R,# R→,L,#
S→,L=R,# R→L,,# L→,*R,#
S→,R,# I3,L→,i,#
L→,*R,=/# S→R,,#
L→,i,=/# I4,I11:
R→,L,# L→*,R,=/# L→*,R,#
L→,*R,=/# R→,L,#
I5,L→i,,=/# L→,i,=/# L→,*R,#
R→,L,=/# L→,i,#
I7 L→*R,,=/# I8 R→L,,#/= I10 I13
I12,L→i,R→L,,# L→*R,,#
LR(1)分析表的构造
若项目 [A→ α,A]属于 Ik,那么 置 ACTION[k,a]为“用产生式
A→ α 进行规约,，简记为,rj”;其中，假定 A→ α 为文法 G`的第
j个产生式；
At the heart of the table construction is the notion
of an LR(0) configuration or item,A configuration
is a production of the grammar with a dot at some
position on its right side,For example,A –> XYZ
gives four items:
A –>?XYZ
A –> X?YZ
A –> XY?Z
A –> XYZ?
