主要内容
? LR(0)分析
0
S→ ? E ＃
E→ ? E+T
E→ ? T
T→ ? id
T→ ? (E )
1
S→E ? ＃
E→E ? +T
5
T→id ?
3
E→E+ ? T
T→ ? id
T→ ? (E)
4
E→E+T ?
9
E→T ?
6
T→( ? E)
E→ ? E+T
E→ ? T
T→ ? id
T→ ? (E )
7
T→(E ? )
E→E ? +T
8
T→(E) ?
T T
(
id
E
T
id
)
E
+
id
(
(
GE的 LRSM
+
2
S→E ＃ ?
＃
? LRSM给出了所有的可归活前缀
? LRSM中的每个状态将对应一个饱和项目集：
（ 1）其中一部分是由先驱状态分出来
(称为基本项目 )；
（ 2）一部分则是由基本项目扩展出来的
(称为扩展项目或派生项目 )。派生部
分项目的特点是其中的, ?” 出现在
产
生式右部的最左侧。
? 形如 A→ ??[P]的项目称为 归约型项目
? 形如 A→ ???[P]的项目称为移入型项目
? 移入－归约冲突
? 归约－归约冲突
? LRSM不能直接用于 LR分析
? LRSM提供的信息：
（ 1）合法性检查信息 [A→ ??a?]
（ 2）移入 /归约信息 [A→ ??a?]；
[A→ ??]
（ 3）移入 /归约后的转向状态信息
# X1 X2 … Xk … Xt
Si0 Si1 Si2 … Sik … Sit aiai+1…a n #
移入动作：设 Sit的 ai输入边所指向的状态为 S*
# X1 X2 … Xk … Xt
Si0 Si1 Si2 … Sik … Sit
ai
S*
归约动作：设按 A→X k+1Xk+2… Xt进行归约，则首先归约为 A
Sik的 A输出边所指向的状态设为 S*,则格局变为：
# X1 X2 … Xk
Si0 Si1 Si2 … Sik
A
S*
设当前格局是：
# X1 X2 … Xk
Si0 Si1 Si2 … Sik
A
LR分析模型
Output
Stack
#an…ai…a1
LR分析驱动器
gotoaction
Input
St Xt
… …
LR分析表
? Action矩阵：行代表状态，列代表输入
符，而矩阵元素则表示相应的分析动作：
Shift / Reduce? / Accept / Error
? GoTo矩阵：行代表状态，而列则代表语
法符号（非终极符，终极符），而矩阵
元素则表示归约后的转向状态。
LR(0)投影函数 ?0
? 动作集 ?,{Shift,Reduce1,Reduce2,..,}
? 投影函数 ?0,StateSet→2 ?
?0(S)={Reduce j|B→ ???S,且 B→ ?是产生式 j}
∪(if (存在 X→ ??a??S 且 a?VT )
then {Shift} )
LR(0)文法
? 如果其 LRSM0的每个状态 S都有 |?0(S)|=1，
即 ?0(S)只包含一个元素，我们称文法 G
是 LR(0)文法。
? 若 ?0(S)={ Shift },则表示 S只含移入
项目
? 若 ?0(S)={ Reduce j },则表示 S只含一
个 [j]归约项目。
?每个状态的移入 /归约动作的确定没有冲
突，而且不依赖于输入符号。
Action表的构造
? Action( S)= Shift,......当 ?0 (S)=Shift
? Action( S)= Reduce j,..当 ?0 (S)=Reduce j
（ j不是拓广产生式号）
? Action( S)= Accept,...当 ?0 (S)=Reduce j
（ j是拓广产生式号）
? Action( S)= Error,..……… 当 ?0 (S)=?
? Action(?)= Error,……… 是特别引进的
错误状态标记
GOTO表的构造
? GoTo( S,X) = S ?, 当 LRSM0中有 S S?
? GoTo( S,X) = ?, 否则
X
? LR(0)分析例
文法如下：
S →E #
E →E+T | T
T →id | (E)
# + id ( ) E T
S0 S5 S6 S1 S9
S1 S2 S3
S2
S3 S5 S6 S4
S4
S5
S6 S5 S6 S7 S9
S7 S3 S8
S8
S9
GoTo表
Shift
Shift
Accept
Shift
Reduce2
Reduce4
Shift
Shift
Reduce5
Reduce3
Action
LR(0)驱动程序
? 1,Push(S0) ；
? 2,Scan(a)；
? 3,S,= TopOf( StateStack)；
? 4,case Action( S ) of
? Error ? ErrorProcess；
? Accept ? Finish；
? Shift ? { Push(GoTo(S,a) )； goto 2}
? Reduce j? { Pop(JJ)；
Push(GoTo(S-JJ,Lj))； goto3}
end
LR(0)分析实例
状态栈 符号栈 输入串 Action Goto
0 id+id# shift 5
05 id +id# reduce4 9
09 T +id# reduce3 1
01 E +id# shift 3
013 E+ id# shift 5
0135 E+id # reduce4 4
0134 E+T # reduce2 1
01 E # shift 2
012 E# accept
id+id#
? 文法 G：
Z →aAc[1]
A →bB [2] | ba[3]
B →dB [4] | e [5]
构造文法的 LR(0)状态机,Action表和
goto表，并给出符号串 abdec的 LR(0)
分析过程。
? LR(0)分析
0
S→ ? E ＃
E→ ? E+T
E→ ? T
T→ ? id
T→ ? (E )
1
S→E ? ＃
E→E ? +T
5
T→id ?
3
E→E+ ? T
T→ ? id
T→ ? (E)
4
E→E+T ?
9
E→T ?
6
T→( ? E)
E→ ? E+T
E→ ? T
T→ ? id
T→ ? (E )
7
T→(E ? )
E→E ? +T
8
T→(E) ?
T T
(
id
E
T
id
)
E
+
id
(
(
GE的 LRSM
+
2
S→E ＃ ?
＃
? LRSM给出了所有的可归活前缀
? LRSM中的每个状态将对应一个饱和项目集：
（ 1）其中一部分是由先驱状态分出来
(称为基本项目 )；
（ 2）一部分则是由基本项目扩展出来的
(称为扩展项目或派生项目 )。派生部
分项目的特点是其中的, ?” 出现在
产
生式右部的最左侧。
? 形如 A→ ??[P]的项目称为 归约型项目
? 形如 A→ ???[P]的项目称为移入型项目
? 移入－归约冲突
? 归约－归约冲突
? LRSM不能直接用于 LR分析
? LRSM提供的信息：
（ 1）合法性检查信息 [A→ ??a?]
（ 2）移入 /归约信息 [A→ ??a?]；
[A→ ??]
（ 3）移入 /归约后的转向状态信息
# X1 X2 … Xk … Xt
Si0 Si1 Si2 … Sik … Sit aiai+1…a n #
移入动作：设 Sit的 ai输入边所指向的状态为 S*
# X1 X2 … Xk … Xt
Si0 Si1 Si2 … Sik … Sit
ai
S*
归约动作：设按 A→X k+1Xk+2… Xt进行归约，则首先归约为 A
Sik的 A输出边所指向的状态设为 S*,则格局变为：
# X1 X2 … Xk
Si0 Si1 Si2 … Sik
A
S*
设当前格局是：
# X1 X2 … Xk
Si0 Si1 Si2 … Sik
A
LR分析模型
Output
Stack
#an…ai…a1
LR分析驱动器
gotoaction
Input
St Xt
… …
LR分析表
? Action矩阵：行代表状态，列代表输入
符，而矩阵元素则表示相应的分析动作：
Shift / Reduce? / Accept / Error
? GoTo矩阵：行代表状态，而列则代表语
法符号（非终极符，终极符），而矩阵
元素则表示归约后的转向状态。
LR(0)投影函数 ?0
? 动作集 ?,{Shift,Reduce1,Reduce2,..,}
? 投影函数 ?0,StateSet→2 ?
?0(S)={Reduce j|B→ ???S,且 B→ ?是产生式 j}
∪(if (存在 X→ ??a??S 且 a?VT )
then {Shift} )
LR(0)文法
? 如果其 LRSM0的每个状态 S都有 |?0(S)|=1，
即 ?0(S)只包含一个元素，我们称文法 G
是 LR(0)文法。
? 若 ?0(S)={ Shift },则表示 S只含移入
项目
? 若 ?0(S)={ Reduce j },则表示 S只含一
个 [j]归约项目。
?每个状态的移入 /归约动作的确定没有冲
突，而且不依赖于输入符号。
Action表的构造
? Action( S)= Shift,......当 ?0 (S)=Shift
? Action( S)= Reduce j,..当 ?0 (S)=Reduce j
（ j不是拓广产生式号）
? Action( S)= Accept,...当 ?0 (S)=Reduce j
（ j是拓广产生式号）
? Action( S)= Error,..……… 当 ?0 (S)=?
? Action(?)= Error,……… 是特别引进的
错误状态标记
GOTO表的构造
? GoTo( S,X) = S ?, 当 LRSM0中有 S S?
? GoTo( S,X) = ?, 否则
X
? LR(0)分析例
文法如下：
S →E #
E →E+T | T
T →id | (E)
# + id ( ) E T
S0 S5 S6 S1 S9
S1 S2 S3
S2
S3 S5 S6 S4
S4
S5
S6 S5 S6 S7 S9
S7 S3 S8
S8
S9
GoTo表
Shift
Shift
Accept
Shift
Reduce2
Reduce4
Shift
Shift
Reduce5
Reduce3
Action
LR(0)驱动程序
? 1,Push(S0) ；
? 2,Scan(a)；
? 3,S,= TopOf( StateStack)；
? 4,case Action( S ) of
? Error ? ErrorProcess；
? Accept ? Finish；
? Shift ? { Push(GoTo(S,a) )； goto 2}
? Reduce j? { Pop(JJ)；
Push(GoTo(S-JJ,Lj))； goto3}
end
LR(0)分析实例
状态栈 符号栈 输入串 Action Goto
0 id+id# shift 5
05 id +id# reduce4 9
09 T +id# reduce3 1
01 E +id# shift 3
013 E+ id# shift 5
0135 E+id # reduce4 4
0134 E+T # reduce2 1
01 E # shift 2
012 E# accept
id+id#
? 文法 G：
Z →aAc[1]
A →bB [2] | ba[3]
B →dB [4] | e [5]
构造文法的 LR(0)状态机,Action表和
goto表，并给出符号串 abdec的 LR(0)
分析过程。
