求出文法的所有项目，按一定规则构造识别活前缀
的
NFA,
再确定化为
DFA
确定化的
工作量较大
，而且
容易出错
，
实际应用中并不使用
，这
里介绍的目的仅仅是为了
便于理解。具体见
识别活前缀的有限自动机构建方法_用编程写诗的博客-CSDN博客
因此这里为了减轻工作量介绍一种实用的方法：
通过
闭包函数
和
转换函数
，
直接求出
LR(0)
项目集规范族，再由转换函数建立
状态之间的连接关系得到识别活前缀的
DFA。
闭包函数：构造项目集
I
的
Closure(I)
I
的任何项目都属于
Closure
（
I
）
若
A→α
.Bβ
属于
Closure
（
I），则对
任何
关于
B
的规则
B→γ ，
项目
B→·γ
也属于
Closure
（
I
）
重复执行上述两步骤，直到
Closure
（
I
）不再增大为止
例：
状态转换函数 GO(I，X)
假定 I 是拓广文法 G′的任一项目集，X 为一
文法符号
，状态
转换函数 GO(I，X) 的定义如下：
GO(I，X) = Closure（J）
其中，J={ A→αX.β│A→α.Xβ∈
I }
新状态的初始项目即圆点移动后的项目称为核。
即 J 称为
核
识别文法所有活前缀的DFA
使用 GO 函数可以将拓广文法 G′的 LR(0)项目集规范族联结
成一个识别文法活前缀的DFA。具体步骤如下:
a)
置项目
S′→
·S
为初态集的
核心
项目，然后对其求闭包，
CLOSURE({S′→·S}
）
得到
初态的项目集
b)
对初态集或其它所构造的项目集应用转换函数
GO(I
，
X)=
Closure
（
J
）
c)
重复
b)
直到不出现新的项目为止
d)
状态转换函数
GO(I
，
X)
建立项目集之间的关系
例子：
LR(0)分析表的构造
设
LR(0)
项目集规范族为
C={I
0
,I
1
,…,I
n
} S’→.
S
称为初态
(1)
若
A→
α·aβ
∈
I
k
且
GO(
I
k
,a)=
I
j
,
若a
∈
V
T
，
置
Action
[k,x]=S
j
(
表示移进
)
若a
∈
V
N
，
置
Goto
[k,x]=j (
表示归约
)
(2)
若
A→
α·
∈
I
k
,
则
∀
a ∈V
T
(
包括
#)
，
ACTION[
k,a
]=
rj
（假定产生式
A→
α
是文法
G’
的第
j
个产生式）
(3)
若
S’箭头
S·
∈
I
k
,
则
ACTION[
k,#
]=
acc
(4)
若
GO(I
k
,A)=I
j
,
则
GOTO[k,A]=j
(5)
分析表中凡是不能用以上规则填入信息的空白格均置
上“报错标志”
根据这个构造方法我们可以得到上面文法的LR(0）分析表
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览48400 人正在系统学习中