闭包和上下文免费语法

我正在查看我的理论计算机科学课程的教学大纲,在Context Free Grammars的标题中,它列出了"闭包属性".我查看了关于这个主题的教科书,发现很少.它现在所拥有的一点点有点高于我的头脑(我还没有参加过这个课程),但我理解了一点.

我想知道在上下文无关语法中这种闭包的想法是否与函数式编程中闭包的概念相同或相关.据我所知,它谈到了语法和解决重叠的结合.书中有很多部分我还不了解,所以我不确定这些想法是否相同.

(更多上下文:我正在给教授写一封电子邮件,询问是否可以从Perl切换到Ruby或Python.如果这些概念是相关的,那么这可能是我们应该使用Ruby而不是Perl的另一个原因.)

在某种意义上,术语"闭合"以多种方式使用,主要追溯到数学完成概念.

如果将该运算符应用于集合中的值,则运算符将"关闭"一组值,始终从给定集合生成值.例如,在整数上关闭加法,但除法不是(4/2是整数,但不是5/2).因此,除非是除法,否则整数的加法在某种程度上是"完整的".

关系的"传递"闭包通过遵循(所有可能的)多个应用程序来"完成"关系.在日常生活中,"是一个后代"的概念是关系"是一个孩子"的传递性封闭.

通过例如指定如何解析自由变量来"完成"功能"闭包".在伪代码表达式中:

bump = function(x) (x + y)

x是的论点bump,但定义似乎留下"开放"的解决问题y.另一方面,如果我们定义:

bumper = function(y) (function(x) (x + y))

然后调用bumper返回一个函数,该函数将原始参数添加bumper到创建的函数的参数中,以便:

add3 = bumper(3)

相当于定义:

add3 = function(x) (x + 3)

嵌套定义在其定义点可用的变量"封闭"(或完成).

因此,实际上,"封闭"的使用首先具有不同的特定含义,乍一看似乎无关,但存在一种微妙的潜在关系.

闭包属性是这样的:如果L和M是无上下文的语言,那么L | M也是如此.函数闭包是实现一流函数的一种方式.所以不,他们几乎没有任何关系.

为什么同名呢？函数闭包是"关闭"它的自由变量:

def adder(n): return lambda m: n + m

这里n是lambda的自由变量.这个名字强调了这一点,因为Lisp最初没有关闭自由变量 - 当调用内部函数时,它们从堆栈中的任何绑定中获取它们的值.

数学中属性的闭包更明显一点:如果在一个操作下关闭一个集合,那么在该集合中应用该操作将不会让你失去它.如果你添加整数,你得到的仍然是一个整数.

大流士是正确的; "封闭属性"与"功能封闭"无关.只有这么多的话要去:-(

闭包属性的概念在整个计算机科学中得到应用,但它被应用于不同类别的语言.不同类别的语言很重要,因为您需要不同的技术来扫描或识别话语.例如,正则表达式可以告诉您是否有保留字,但是如果您有一个带有平衡括号的表达式,它们就无法告诉您 - 因为您需要一个无上下文语法.

人们通常感兴趣的是,如果你选择一个特定语言,并且你与另一种语言交叉或结合,或者只是补充语言,你是否在同一个班级中获得另一种语言.例如,是否可以编写一个与那些令牌完全匹配的正则表达式非保留字的？我们可以回答一个响亮的"是",因为常规语言在补语下是封闭的,也就是说,常规语言的补充本身就是一种常规语言.这是一个闭包属性的例子.通常证明是建设性的,也就是说,它不仅告诉你存在一个描述所有非保留字的标记的正则表达式,闭包属性的证明将告诉你如何查找 这样的正则表达.