CLOSURE与GOTO函数

在了解这两个函数之前需要先认识几个概念

• 项目
  右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目：A → α1·α2
• 项目集
  从字面上不难理解项目集就是项目的集合
• 项目集闭包
  一个文法中某个由所有等价项目所组成的集合

CLOSURE函数

CLOSURE函数定义如下：

CLOSURE(I) = I ∪ {B → ·γ | A → α·Bβ ∈ CLOSURE(I), B→γ ∈ P}

|后的部分可以看做是B应该满足的条件

乍一看这函数可能有点懵的感觉，因为CLOSURE(I)等式的右边还有一个CLOSURE(I)。你可能会想 这用CLOSURE(I)定义CLOSURE(I)这不是很奇怪吗？其实定义中等号右边的CLOSURE(I)并没有参与运算，只是用于判断出那些属于该项目集闭包的项目。

以下文法作为例子进行说明

S' → S
S → BB
B → aB
B → b

其对应的所有项目如下

S' → .S             S' → S.         S → BB.
S → .BB           S →.BB         B → aB.
B → .aB           B → a.B
B → .b             B → b.

首先我们需要了解清楚CLOSURE(I)函数的作用，CLOSURE(I)是为了求出项目集合I对应的项目集合闭包，亦即求出I所在文法中对应的所有等价项目组成的集合。

简单说就是利用CLOSURE函数以项目集合I为参数，求得另外一个项目集合,此项目集合包含跟集合I中项目等价的所有项目亦即集合I是项目集闭包的子集。

假设开始时有一项目集合I = {S' → .S}，为了求I对应的项目闭包我们可以调用CLOSURE函数。

1. 根据项目集闭包定义有S' → .S ∈ CLOSURE(I)，当然同时S' → .S ∈ I

2. 显然产生式 S → BB ∈ P

CLOSURE(I) =  I ∪ {B → ·γ | A → α·Bβ ∈ CLOSURE(I), B→γ ∈ P}

S → BB ∈ P对应上式中的B→γ ∈ P
S' → .S ∈ CLOSURE(I)对应上式中的A → α·Bβ ∈ CLOSURE(I)

可推出 I ∪ {S → .BB} ∈ CLOSURE(I)
可推出 {S' → .S, S → .BB} ∈ CLOSURE(I)
可推出 S → .BB ∈ CLOSURE(I)

3. 由B → aB, B → b ∈ P并且S → .BB ∈ CLOSURE(I)
   同理可推出
   {S' → .S, S → .BB, B → .aB, B → .b } ∈ CLOSURE(I)

算法的伪代码：

算法.png

GOTO函数

在弄清楚CLOSURE函数后，其实GOTO函数还挺好理解的。

GOTO( I, X )=CLOSURE({A→αX·β | A→α·Xβ ∈I })

算法.png

GOTO函数主要作用是从一个项目集闭包转移至另外一个项目集闭包。