第六章ＬＲ分析自下而上的语法分析特定的一种 shift-reduce实现技术能力强几乎所有 CFG的语言结构都能用 LR分析不需要对文法附加条件难点几乎不可能用手工编写 LR分析器现实有 LR分析器的生成器第六章ＬＲ分析
6.1 概述自下而上的语法分析
LR分析器
6.2 LR(0)分析
6.3 SLR(1)分析技术，二义文法的应用
6.4 LR(1)和 LALR(1)分析
6.1 概述自下而上的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否该文法的 句子
S
A A
c a b d c a b d c d
归约 过程构造的推导,cAd? cabd S? cAd
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，那么在 c A b d
中无法找到一个可归约串了，
最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子在自下而上的分析方法中 如何识别可归约的串？
在分析程序工作的每一步，
都是从当前串中 选择一个子串,将它 归约 到 某个非终结符号,该子串称为
,可归约串,
c a b d
c A b d
a
刻画,可归约串,
文法 G[S]
句型的短语
S =>* α Aδ 且 A =>+ β,则称 β 是 句型 α β δ
相对于非终结符 A的 短语句型的直接短语若有 A? β,则称 β 是句型 α β δ 相对于非终结符 A 的 直接短语句型的句柄一个句型的 最左直接短语 称为 该句型 的 句柄例,i*i+i 的短语、直接短语和句柄
E
E + T
T F
T * F
i3 短语,i1*i2+ i3,i1* i2,
F i2 i1,i2,i3 。
i1 直接短语,i1,i2,i3 。 句柄,
i1
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型,i*i+i
自下而上的语法分析在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为
,可归约串,
选择,可归约串,是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）
选择,可归约串,是句型的句柄－规范归约
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型 i*i+i 的自下而上分析,总是归约当前句型的句柄形成的规范推导序列：
E?E+T?E+F?E+i?T+i?T*F+i?T*i+i?F*i+i?i*i+i
句型 i*i+i 的自下而上分析 总是归约当前句型的最左素短语形成的推导：
E?T+F?T+i?F*F+i?F*i+i?i*i+i
自下而上的分析模式 移进－归约模式
Shift:移进,输入符 进栈
reduce:归约，用第 i个产生式归约总控程序 output…
产生式表
Input$(#)
…
移进归约依据表文法 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 # 归约 (S →aAcBe)
符号串 abbcde是否是 G[S]的句子对输入串 abbcde#的移进 -归约分析过程
S?aAcBe? aAcde? aAbcde? abbcde
6.1 概述 ＬＲ分析 特定的一种 shift-reduce实现技术
L 从左到右扫描输入串 R 构造最右推导
ＬＲ分析 器模型总控程序 output
Input$(#)
…
栈
LR分析表产生式表
LR分析表
(1)S?a A c B e (2)A?b (3)A?Ab (4)B?d
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分析使用两张表
ACTION表告诉分析器：栈顶状态为 S,当前输入符号是 a时做什麽
1,ACTION[S,a]= Sj
2,ACTION[S,a]=rj (第 j条产生式为 A)
3,ACTION[S,a]=acc
4,ACTION[S,a]= error
GOTO表
GOTO[S,A]栈顶状态为 S，归约之后的非终结符為 A时，
要放到栈顶的新状态
ＬＲ分析
– G[S],(1)S?a A c B e
– (2)A?b
– (3)A?Ab
– (4)B?d
w=abbcde#
Step states.,The rest of input action goto
1 0 abbcde# s2
2 02 bbcde# s4
3 024 bcde# r2 goto(2,A)
4 023 bcde# s6
5 0236 cde# r3 goto(2,A)
6 023 cde# s5
7 0235 de# s8
8 02358 e# r4 goto(5,B)
9 02357 e# s9
10 023579 # r1 goto(0,S)
11 01 # acc
1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id
id + (id)
LR分析算法置 ip指向输入串 w的第一个符号令 S为栈顶状态
a是 ip指向的符号重复 begin
if ACTION[S,a]=Sj
then begin PUSH j(进栈 )
ip 前进 (指向下一输入符号 )
end
else if ACTION[S,a]=rj (第 j条产生式为 A)
ＬＲ分析 算法 (continue)
then begin
pop |?| 项令当前栈顶状态为 S’
push GOTO[S’,A]
end
else if ACTION[s,a]=acc
then return (成功）
else error
end.重复
ＬＲ 分析特征
栈顶状态为 S,当前输入符号是 a时做什麽 ---?有穷狀态自动机
规范推导进一步讨论ＬＲ分析特征
– G[S],(1)S?a A c B e
– (2)A?b
– (3)A?Ab
– (4)B?d
w=abbcde#
(带符号栈的）ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 文法符号
ACTION GOTO
LR分析表产生式表
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2
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
ＬＲ分析
特征,
–,规范的
–,符号栈中的符号是规范句型的前缀,且不含句柄以后的任何符号
–,分析决策依据 ―― 栈顶状态和现行输入符号,？ 识别规范句型特定前缀 (就到句柄为止 )的 DFA.
四种技术
– LR(0) SLR(1) LR(1) LALR(1)
文法 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
个产生式的 左部 非终结 符入栈。
6.2 LR(0) 分析
LR(0)文法能力最弱，理论上最重要
存在 DFA识别规范句型特定前缀 (就到句柄为止 ).
该 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)
则拓广文法 G‘=({S,S‘},{a},{S’?S,
S?Sa,S?a},S)
RR
*
DFA
启示,LR分析使用的信息之一是句柄左部的内容,
定义 (非终结符的左文 )
LC(A)={? | S’A?,V*,Vt*},
对拓广文法的开始符号 S’:
LC(S’)={?}
若有 BA? 则,LC(A)?LC(B).{?}因为,
S’BA
R
*
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).{?}
[S’]=?
[S]=?
[A]=a
[B]=aAc
则有,
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→d,
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填入信息的空白格均置上
,出错标志,。
LR(0)文法
按上述算法构造的含有 ACTION和 GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法 G
的一张 LR(0)表。具有 LR(0)表的文法 G称为一个 LR
（ 0） 文法。
LR(0)文法是无二义的。
例 文法 G:（ 0） S`→E (1) E→aA (2) E→bB
(3) A→cA (4) A→d (5) B→cB
(6) B→d
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→? 是 归约项目作用？
例 G[S]为,
S?a A c B e
A?b
A?Ab
B?d
1)构造识别活前缀的 DFA
2)构造它的 LR(0)分析表。
3)分别给出对输入 符号串 abbcde和
Abbbce的 LR(0)分析步骤。
G[S]拓广 为,
S’? S
S?a A c B e
A?b
A?Ab
B?d
I0,S’ S
S a A c B e
I1,S’? S? I2,S? a? A c B eA b
A Ab
I3,S? a A? c B e
A? A? b
I4,A? b?
I5,S? a A c? B e
B d I7,S? a A c B? e
I8,B? d? I9,S? a A c B e?
I6,A? A b?
S a
A
b b
c
B
ed
G[L]= ab+ cde
例 G[S]的 LR(0)分析表
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
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2 3
4 023 #aA bcde# s6
5 0236 #aAb cde# r3 3
6 023 #aA cde# s5
7 0235 #aAc de# s8
8 02358 #aAcd e# r4 7
9 02357 #aAcB e# s9
10 023579 #aAcBe # r1 1
11 01 #S # acc
对输入串 abbcde#的分析过程
Step states,Syms,The rest of input action goto
1 0 # abbce# s2
2 02 #a bbce# s4
3 024 #ab bce# r2 3
4 023 #aA bce# s6
5 0236 #aAb ce# r3 3
6 023 #aA ce# s5
7 0235 #aAc e# 出错说明 abbce#不是 文法 G[S]的 句子对输入串 abbce#的分析过程构造识别活前缀的 NFA
文法 G’：
S’→E
E→aA ∣ bB
A→cA |d
B→cB | d
把文法的所有产生式的项目都列出，
每个项目都为 NFA
的一个状态。
该文法的项目有：
1 S’→ ·E 10 A→d.
2 S’→E · 11 E→ ·bB
3 E→ ·aA 12 E→b ·B
4 E→a ·A 13 E→bB ·
5 E→aA · 14 B→ ·cB
6 A→ ·cA 15 B→c ·B
7 A→c ·A 16 B→cB ·
8 A→cA · 17 B→ ·d
9 A→ ·d 18 B→d ·
构造识别活前缀的 NFA
由于 Sˊ 仅在第一个产生式的左部出现，因此规定项目 1
为初态，其余每个状态都为活前缀的识别态，圆点在最后的项目为句柄识别态，第一个产生式的句柄识别态为句子识别态。状态之间的转换关系确定方法为如下：
若 i项目为,X→X 1X2… Xi-1?Xi… Xn
j项目为,X→X→X 1X2… Xi-1 Xi? Xi+1 … Xn
i项目和 j项目出于同一个产生式。对应于 NAF为状态 j的圆点只落后于状态 I的圆点一个符号的位置，那么从状态
i到状态连一条标记为 Xi的箭弧。
如果 Xi为非终结符，则一定会有 Xi为左部的有关项目及其相应的状态，例如：
j项目,X→? A i项目,A→ k项目,A →则对于 A
的所有产生式圆点在最左边的项目相应的状态都做一条从 j状态到该状态（这里是 i和 k)的箭弧，其上标记为 ε
6.1 概述自下而上的语法分析
LR分析器
6.2 LR(0)分析
6.3 SLR(1)分析技术，二义文法的应用
6.4 LR(1)和 LALR(1)分析
6.1 概述自下而上的语法分析例：文法 G,S → cAd
A → ab
A → a
识别输入串 w=cabd是否该文法的 句子
S
A A
c a b d c a b d c d
归约 过程构造的推导,cAd? cabd S? cAd
(1)S → cAd (2) A → ab (3)A → a
识别输入串 w=cabd是否为该文法的 句子自下而上的语法分析对串 cabd的分析中，如果不是选择 ab用产生式 (2),而是选择 a用产生式 (3)将 a归约到了 A，那么在 c A b d
中无法找到一个可归约串了，
最终就达不到归约到 S的结果，因而也无从知道 cabd是一个句子在自下而上的分析方法中 如何识别可归约的串？
在分析程序工作的每一步，
都是从当前串中 选择一个子串,将它 归约 到 某个非终结符号,该子串称为
,可归约串,
c a b d
c A b d
a
刻画,可归约串,
文法 G[S]
句型的短语
S =>* α Aδ 且 A =>+ β,则称 β 是 句型 α β δ
相对于非终结符 A的 短语句型的直接短语若有 A? β,则称 β 是句型 α β δ 相对于非终结符 A 的 直接短语句型的句柄一个句型的 最左直接短语 称为 该句型 的 句柄例,i*i+i 的短语、直接短语和句柄
E
E + T
T F
T * F
i3 短语,i1*i2+ i3,i1* i2,
F i2 i1,i2,i3 。
i1 直接短语,i1,i2,i3 。 句柄,
i1
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型,i*i+i
自下而上的语法分析在分析程序工作的每一步，都是从当前串中 选择一个 子串,将它 归约 到 某个非终结符号,该子串称为
,可归约串,
选择,可归约串,是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）
选择,可归约串,是句型的句柄－规范归约
G[E],E→E+T|T
T→T*F|F
F→(E)|i
句型 i*i+i 的自下而上分析,总是归约当前句型的句柄形成的规范推导序列：
E?E+T?E+F?E+i?T+i?T*F+i?T*i+i?F*i+i?i*i+i
句型 i*i+i 的自下而上分析 总是归约当前句型的最左素短语形成的推导：
E?T+F?T+i?F*F+i?F*i+i?i*i+i
自下而上的分析模式 移进－归约模式
Shift:移进,输入符 进栈
reduce:归约，用第 i个产生式归约总控程序 output…
产生式表
Input$(#)
…
移进归约依据表文法 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 # 归约 (S →aAcBe)
符号串 abbcde是否是 G[S]的句子对输入串 abbcde#的移进 -归约分析过程
S?aAcBe? aAcde? aAbcde? abbcde
6.1 概述 ＬＲ分析 特定的一种 shift-reduce实现技术
L 从左到右扫描输入串 R 构造最右推导
ＬＲ分析 器模型总控程序 output
Input$(#)
…
栈
LR分析表产生式表
LR分析表
(1)S?a A c B e (2)A?b (3)A?Ab (4)B?d
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分析使用两张表
ACTION表告诉分析器：栈顶状态为 S,当前输入符号是 a时做什麽
1,ACTION[S,a]= Sj
2,ACTION[S,a]=rj (第 j条产生式为 A)
3,ACTION[S,a]=acc
4,ACTION[S,a]= error
GOTO表
GOTO[S,A]栈顶状态为 S，归约之后的非终结符為 A时，
要放到栈顶的新状态
ＬＲ分析
– G[S],(1)S?a A c B e
– (2)A?b
– (3)A?Ab
– (4)B?d
w=abbcde#
Step states.,The rest of input action goto
1 0 abbcde# s2
2 02 bbcde# s4
3 024 bcde# r2 goto(2,A)
4 023 bcde# s6
5 0236 cde# r3 goto(2,A)
6 023 cde# s5
7 0235 de# s8
8 02358 e# r4 goto(5,B)
9 02357 e# s9
10 023579 # r1 goto(0,S)
11 01 # acc
1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id
id + (id)
LR分析算法置 ip指向输入串 w的第一个符号令 S为栈顶状态
a是 ip指向的符号重复 begin
if ACTION[S,a]=Sj
then begin PUSH j(进栈 )
ip 前进 (指向下一输入符号 )
end
else if ACTION[S,a]=rj (第 j条产生式为 A)
ＬＲ分析 算法 (continue)
then begin
pop |?| 项令当前栈顶状态为 S’
push GOTO[S’,A]
end
else if ACTION[s,a]=acc
then return (成功）
else error
end.重复
ＬＲ 分析特征
栈顶状态为 S,当前输入符号是 a时做什麽 ---?有穷狀态自动机
规范推导进一步讨论ＬＲ分析特征
– G[S],(1)S?a A c B e
– (2)A?b
– (3)A?Ab
– (4)B?d
w=abbcde#
(带符号栈的）ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 文法符号
ACTION GOTO
LR分析表产生式表
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2
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
ＬＲ分析
特征,
–,规范的
–,符号栈中的符号是规范句型的前缀,且不含句柄以后的任何符号
–,分析决策依据 ―― 栈顶状态和现行输入符号,？ 识别规范句型特定前缀 (就到句柄为止 )的 DFA.
四种技术
– LR(0) SLR(1) LR(1) LALR(1)
文法 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
个产生式的 左部 非终结 符入栈。
6.2 LR(0) 分析
LR(0)文法能力最弱，理论上最重要
存在 DFA识别规范句型特定前缀 (就到句柄为止 ).
该 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)
则拓广文法 G‘=({S,S‘},{a},{S’?S,
S?Sa,S?a},S)
RR
*
DFA
启示,LR分析使用的信息之一是句柄左部的内容,
定义 (非终结符的左文 )
LC(A)={? | S’A?,V*,Vt*},
对拓广文法的开始符号 S’:
LC(S’)={?}
若有 BA? 则,LC(A)?LC(B).{?}因为,
S’BA
R
*
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).{?}
[S’]=?
[S]=?
[A]=a
[B]=aAc
则有,
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→d,
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填入信息的空白格均置上
,出错标志,。
LR(0)文法
按上述算法构造的含有 ACTION和 GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法 G
的一张 LR(0)表。具有 LR(0)表的文法 G称为一个 LR
（ 0） 文法。
LR(0)文法是无二义的。
例 文法 G:（ 0） S`→E (1) E→aA (2) E→bB
(3) A→cA (4) A→d (5) B→cB
(6) B→d
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→? 是 归约项目作用？
例 G[S]为,
S?a A c B e
A?b
A?Ab
B?d
1)构造识别活前缀的 DFA
2)构造它的 LR(0)分析表。
3)分别给出对输入 符号串 abbcde和
Abbbce的 LR(0)分析步骤。
G[S]拓广 为,
S’? S
S?a A c B e
A?b
A?Ab
B?d
I0,S’ S
S a A c B e
I1,S’? S? I2,S? a? A c B eA b
A Ab
I3,S? a A? c B e
A? A? b
I4,A? b?
I5,S? a A c? B e
B d I7,S? a A c B? e
I8,B? d? I9,S? a A c B e?
I6,A? A b?
S a
A
b b
c
B
ed
G[L]= ab+ cde
例 G[S]的 LR(0)分析表
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
Step states,Syms,The rest of input action goto
1 0 # abbcde# s2
2 02 #a bbcde# s4
3 024 #ab bcde# r2 3
4 023 #aA bcde# s6
5 0236 #aAb cde# r3 3
6 023 #aA cde# s5
7 0235 #aAc de# s8
8 02358 #aAcd e# r4 7
9 02357 #aAcB e# s9
10 023579 #aAcBe # r1 1
11 01 #S # acc
对输入串 abbcde#的分析过程
Step states,Syms,The rest of input action goto
1 0 # abbce# s2
2 02 #a bbce# s4
3 024 #ab bce# r2 3
4 023 #aA bce# s6
5 0236 #aAb ce# r3 3
6 023 #aA ce# s5
7 0235 #aAc e# 出错说明 abbce#不是 文法 G[S]的 句子对输入串 abbce#的分析过程构造识别活前缀的 NFA
文法 G’：
S’→E
E→aA ∣ bB
A→cA |d
B→cB | d
把文法的所有产生式的项目都列出，
每个项目都为 NFA
的一个状态。
该文法的项目有：
1 S’→ ·E 10 A→d.
2 S’→E · 11 E→ ·bB
3 E→ ·aA 12 E→b ·B
4 E→a ·A 13 E→bB ·
5 E→aA · 14 B→ ·cB
6 A→ ·cA 15 B→c ·B
7 A→c ·A 16 B→cB ·
8 A→cA · 17 B→ ·d
9 A→ ·d 18 B→d ·
构造识别活前缀的 NFA
由于 Sˊ 仅在第一个产生式的左部出现，因此规定项目 1
为初态，其余每个状态都为活前缀的识别态，圆点在最后的项目为句柄识别态，第一个产生式的句柄识别态为句子识别态。状态之间的转换关系确定方法为如下：
若 i项目为,X→X 1X2… Xi-1?Xi… Xn
j项目为,X→X→X 1X2… Xi-1 Xi? Xi+1 … Xn
i项目和 j项目出于同一个产生式。对应于 NAF为状态 j的圆点只落后于状态 I的圆点一个符号的位置，那么从状态
i到状态连一条标记为 Xi的箭弧。
如果 Xi为非终结符，则一定会有 Xi为左部的有关项目及其相应的状态，例如：
j项目,X→? A i项目,A→ k项目,A →则对于 A
的所有产生式圆点在最左边的项目相应的状态都做一条从 j状态到该状态（这里是 i和 k)的箭弧，其上标记为 ε
