主要内容
? 识别规约活前缀的 LRSM的构造
派生定理
? 开始符产生式的右部是归约活前缀 。
? 如果 ?A?是归约活前缀, 且 A→ ?是产生式,
则 ??也是归约活前缀 。
? 任何归约活前缀，都可按上述方式被派生。
?设文法开始符的产生式是,
S → ?1|?2|… |?n
RPSG={?1,…,?n}?{??|?A??RPSG,A→ ??P}
? 例有文法 G[s],
S → aAc [1]
A → Abb [2]
A → b [3]
可归前缀集：
aAc
aAbb
ab
? LR(0)项目,若 A→ ??是产生式，
则称 A→ ???为 LR(0)项目 (简称项目），也
写作 ???[p]形式。
? 项目集的投影,假设 IS是 LR(0)项目集，则
称下面 IS(X) 为 IS关于 X的投影集：
IS(X) = { A→ ?X?? | A→ ??X?? IS,
X? (VT ?VN ) }.
? 项目集的闭包,假设 IS是 LR(0)项目集，则
称下面 CLOSURE(IS)为 IS的闭包集：
CLOSURE(IS)= IS ?
{A→ ?? | Y→ ??A??CLOSURE(IS)
A→ ?是产生式 }
两个重要的性质
? 归约活前缀的性质：若 ?A?是归约活前
缀,A→ ?是产生式，则 ??也是归约活
前缀。
? 活前缀状态机性质：若有
??Prefix(ISi ),且 A→ ????ISi, 则
??是归约活前缀。
? 若有 ??Prefix(ISi ),Y→ ??A??ISi, 则
根据性质 2— (活前缀状态机的性质），
?A?是归约活前缀。再根据派生原理，若
A→ ?是 A的产生式，则 ??也是归约活前缀。
? 构造 LRSM的思想：
如果在状态项目集 ISi 中有项目 A→ ??B?，
且 B→ ?是 B的产生式，则在 ISi 中增加项目
B→ ??； 对于 ISi 这个过程继续到不可再扩
充为止。
构造 LR(0)活前缀状态机 LRSM的算法要点,
?构造初始状态 IS0,IS0=CLOSURE({Z→ ?S}),并给 IS0标
上 NO。
?从已构造的 LRSM部分图选择被标为 NO的任一状态 IS，
并做
[1] 对每个符号 X?VT?VN,做下面动作：
1) 令 ISj = CLOSURE( IS(X)),若非空 。
2) 若在 LRSM部分图中已有 ISk与 ISj有相同项目
集, 则令 m=k； 否则构造 ISj的状态点 ISj，
并给 ISj标上 NO,同时令 m=j。
3) 在 IS和 ISm之间画有向 X边,IS ISm 。
[2] 给 IS标上 OK。
?重复上一步骤, 直至没有被标记为 NO的状态结点为止 。
x
?例：构造 LR(0)状态机
S ? E ＃
E ? E + T
E ? T
T ? id
T? ( E )
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
? 文法定义如下：
Z → S
S → (S) S | ?
构造该文法的 LR(0)状态机，要求不含
有空输出边。
? 识别规约活前缀的 LRSM的构造
派生定理
? 开始符产生式的右部是归约活前缀 。
? 如果 ?A?是归约活前缀, 且 A→ ?是产生式,
则 ??也是归约活前缀 。
? 任何归约活前缀，都可按上述方式被派生。
?设文法开始符的产生式是,
S → ?1|?2|… |?n
RPSG={?1,…,?n}?{??|?A??RPSG,A→ ??P}
? 例有文法 G[s],
S → aAc [1]
A → Abb [2]
A → b [3]
可归前缀集：
aAc
aAbb
ab
? LR(0)项目,若 A→ ??是产生式，
则称 A→ ???为 LR(0)项目 (简称项目），也
写作 ???[p]形式。
? 项目集的投影,假设 IS是 LR(0)项目集，则
称下面 IS(X) 为 IS关于 X的投影集：
IS(X) = { A→ ?X?? | A→ ??X?? IS,
X? (VT ?VN ) }.
? 项目集的闭包,假设 IS是 LR(0)项目集，则
称下面 CLOSURE(IS)为 IS的闭包集：
CLOSURE(IS)= IS ?
{A→ ?? | Y→ ??A??CLOSURE(IS)
A→ ?是产生式 }
两个重要的性质
? 归约活前缀的性质：若 ?A?是归约活前
缀,A→ ?是产生式，则 ??也是归约活
前缀。
? 活前缀状态机性质：若有
??Prefix(ISi ),且 A→ ????ISi, 则
??是归约活前缀。
? 若有 ??Prefix(ISi ),Y→ ??A??ISi, 则
根据性质 2— (活前缀状态机的性质），
?A?是归约活前缀。再根据派生原理，若
A→ ?是 A的产生式，则 ??也是归约活前缀。
? 构造 LRSM的思想：
如果在状态项目集 ISi 中有项目 A→ ??B?，
且 B→ ?是 B的产生式，则在 ISi 中增加项目
B→ ??； 对于 ISi 这个过程继续到不可再扩
充为止。
构造 LR(0)活前缀状态机 LRSM的算法要点,
?构造初始状态 IS0,IS0=CLOSURE({Z→ ?S}),并给 IS0标
上 NO。
?从已构造的 LRSM部分图选择被标为 NO的任一状态 IS，
并做
[1] 对每个符号 X?VT?VN,做下面动作：
1) 令 ISj = CLOSURE( IS(X)),若非空 。
2) 若在 LRSM部分图中已有 ISk与 ISj有相同项目
集, 则令 m=k； 否则构造 ISj的状态点 ISj，
并给 ISj标上 NO,同时令 m=j。
3) 在 IS和 ISm之间画有向 X边,IS ISm 。
[2] 给 IS标上 OK。
?重复上一步骤, 直至没有被标记为 NO的状态结点为止 。
x
?例：构造 LR(0)状态机
S ? E ＃
E ? E + T
E ? T
T ? id
T? ( E )
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
? 文法定义如下：
Z → S
S → (S) S | ?
构造该文法的 LR(0)状态机，要求不含
有空输出边。
