什么是上下文无关语法？

Question

有人能给我解释一下上下文无关文法是什么吗？看了维基百科的词条，然后又看了维基百科关于形式语法的词条，我完全被搞糊涂了。有人能解释一下这些东西是什么吗？

我之所以想知道这一点，是因为我希望研究解析，同时也研究正则表达式引擎的局限性。

我不确定这些术语是直接与编程相关，还是更多地与语言学相关。如果是这样的话，我很抱歉，如果是这样的话，也许可以移动一下？

Answer 1

上下文无关文法是满足某些属性的文法。在计算机科学中，语法描述语言；具体地说，它们描述形式语言。

形式语言只是一组字符串(符号序列……与单词“字符串”的编程用法非常相似)。形式语言的一个简单示例是长度为3，{000,001,010,011,100,101,110,111}的所有二进制字符串的集合。

语法通过定义转换来工作，您可以使用语法描述的语言构造字符串。文法将告诉我们如何将一个开始符号(通常是S)转换成一些符号字符串。前面给出的语言的语法是：

S -> BBB
B -> 0
B -> 1

解释这一点的方法是，S可以被BBB替换，B可以被0替换，B可以被1替换，所以要构造字符串010，我们可以做S -> BBB -> 0BB -> 01B -> 010。

上下文无关文法就是这样一种文法:你要替换的东西(箭头的左边)是一个“非终结符”。非末尾符号是您在语法中使用的、不能出现在最终字符串中的任何符号。在上面的语法中，"S“和"B”是非终止符号，而"0“和"1”是“终止”符号。语法，如

S -> AB
AB -> 1
A -> AA
B -> 0

不是上下文无关的，因为它们包含像AB -> 1这样的规则，这些规则在左边有多个非终结符。

Answer 2

语言理论与计算理论是相关的。这是计算机科学更哲学的一面，关于决定哪些程序是可能的，或者哪些将永远可能编写，以及什么类型的问题是不可能编写一个算法来解决的。

正则表达式是描述正则语言的一种方式。正则语言是一种可以由确定性有限自动机决定的语言。

您应该阅读有关有限状态机的文章：http://en.wikipedia.org/wiki/Finite_state_machine

和常规语言：http://en.wikipedia.org/wiki/Regular_language

所有的常规语言都是上下文无关的语言，但是有一些上下文无关的语言不是常规的。上下文无关语言是上下文无关文法或下推自动机接受的所有字符串的集合，它是具有单个堆栈的有限状态机：http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

还有更复杂的语言需要图灵机(您可以在计算机上编写的任何可能的程序)来确定字符串是否包含在该语言中。

语言理论也与P与NP问题以及其他一些有趣的问题密切相关。

我第三年的“计算机科学导论”课本很好地解释了这些东西:计算理论导论。作者: Michael Sipser。但是，我花了160美元买了一台新的，而且它不是很大。也许你可以找到一份二手的副本，或者在图书馆找到一份副本，或者其他可能对你有帮助的东西。

编辑：

在过去50年左右的时间里，人们对正则表达式和高级语言类的局限性进行了大量研究。您可能会对常规语言的pumping引理感兴趣。它是一种证明某种语言不是正规语言的手段：

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

如果一种语言不是正则的，它可能是上下文无关的，这意味着它可以由上下文无关文法来描述，或者它甚至可以在更高的语言类中，你可以通过上下文无关语言的pumping引理来证明它不是上下文无关的，这与正则表达式的引理类似。

一种语言甚至可能是不可决定的，这意味着即使是图灵机(可以编程你的计算机可以运行)也不能被编程来决定一个字符串是应该像语言一样被接受还是被拒绝。

我认为您最感兴趣的部分是有限状态机(包括确定性和确定性)，用于查看正则表达式可以决定哪些语言，以及泵引理来证明哪些语言不是正则语言。

基本上，如果一种语言需要某种类型的内存或计数能力，那么它就不是正规的。例如，匹配括号的语言是不规则的，因为机器需要记住它是否打开了一个括号，以便知道它是否必须关闭一个括号。

使用字母a和b且至少包含三个b的所有字符串的语言是一种常规语言: aba_ba_ba

所有使用字母a和b的字符串的语言都不是规则的。

此外，您不应该认为所有的有限语言都是正规的，例如：

所有长度小于50个字符的字符串使用字母a和b的语言是规则的，因为它是有限的，我们知道它可以描述为(b|abb|bab|bba|aabbb|abb|...)ect，直到列出所有可能的组合。