美文网首页
CLOSURE与GOTO函数

CLOSURE与GOTO函数

作者: 衣忌破 | 来源:发表于2019-11-21 21:19 被阅读0次

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

  • 项目
    右部某位置标有圆点的产生式称为相应文法的一个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)

  1. 由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函数主要作用是从一个项目集闭包转移至另外一个项目集闭包。

相关文章

  • CLOSURE与GOTO函数

    在了解这两个函数之前需要先认识几个概念 项目右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目:A → α...

  • 十二月第三周

    1.swift中closure与OC中block的区别?1>、closure是匿名函数、block是一个结构体对象...

  • 尝试理解Swift中的@escaping

    要理解@escaping,首先需要理解closure, 要理解closure,首先理解匿名函数。 先理解匿名函数 ...

  • Swift中的@escaping

    要理解@escaping,首先需要理解closure, 要理解closure,首先理解匿名函数。先理解匿名函数要在...

  • : start

    类似与c语言的main函数是程序的入口 start cmd //新建cmd窗口 goto 是转到....

  • 关于闭包

    闭包的英文是closure,又称词法闭包(Lexical Closure)和函数闭包(Function Closu...

  • Go 控制流

    if goto for switch 函数 func defer 你可以在函数中添加多个defer语句。当函数执行...

  • 闭包 | 匿名函数

    Closure::__construct 用于禁止实例化的构造函数Closure::bind 复制一个闭包,绑定指...

  • 闭包

    MDN:函数与对其状态即词法环境(lexical environment)的引用共同构成闭包(closure)。也...

  • 嵌入式day05

    循环结构 goto语句 当函数有很多个出口,使用goto把这些出口集中到一处是很方便的,特别是函数中有许多重复的清...

网友评论

      本文标题:CLOSURE与GOTO函数

      本文链接:https://www.haomeiwen.com/subject/kxbtwctx.html