什么是上下文无关语法？

有人能给我解释一下什么是上下文无关语法吗？在看了维基百科条目和维基百科正式语法条目之后，我彻底迷惑了。有人能解释一下这些是什么吗？

我对此感到疑惑，因为我希望研究解析以及正则表达式引擎的局限性。

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

33651 次浏览
小开

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

A regular expression is a way of describing a regular language. A regular language is a language which can be decided by a deterministic finite automaton.

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

And Regular languages: Http://en.wikipedia.org/wiki/regular_language

所有正则语言都是上下文无关语言，但是也有不正则的上下文无关语言。上下文无关语言是一个上下文无关语法器或下推自动机(Pushdown Automata)接受的所有字符串的集合，后者是一个有限状态机，只有一个栈: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

还有更复杂的语言需要一个图灵机(任何可能的程序，你可以写在你的计算机上)来决定一个字符串是否在语言中。

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

My Introduction to Computer Science third year text book was pretty good at explaining this stuff: Introduction to the Theory of Computation. By Michael Sipser. But, it cost me like $160 to buy it new and it's not very big. Maybe you can find a used copy or find a copy at a library or something it might help you.

编辑:

正则表达式和高级语言类的局限性在过去50年左右的时间里得到了大量的研究。您可能对常规语言的泵引理感兴趣。这是一种证明某种语言不规则的手段:

Http://en.wikipedia.org/wiki/pumping_lemma_for_regular_languages

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

一种语言甚至可以是不可判断的，这意味着即使是图灵机(可能是您的计算机可以运行的程序)也不能通过编程来决定一个字符串是否应该像语言中那样被接受或者被拒绝。

我认为你最感兴趣的部分是有限状态机(确定性和确定性) ，看看正则表达式可以决定哪些语言，抽取引理来证明哪些语言不是正则的。

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

使用至少包含三个 b 的字母 a 和 b 的所有字符串的语言都是常规语言: a爸ba爸

使用字母 a 和 b 的所有字符串的语言中，b 比 a 包含更多的字符串是不规则的。

你也不应该认为所有的有限语言都是规则的，例如:

所有长度小于50个字符的字符串，如果使用字母 a 和 b，其中 b 多于 a，这种语言是正则的，因为它是有限的，我们知道它可以被描述为(b | abb | bab | bba | aabbb | ababb | ...)等等，直到所有可能的组合被列出。

小开
最佳答案

A context free grammar is a grammar which satisfies certain properties. In computer science, grammars describe languages; specifically, they describe formal languages.

形式语言只是字符串(符号序列... 非常类似于“字符串”的编程用法)的集合(对象集合的数学术语)。形式语言的一个简单示例是长度为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

Are not context free since they contain rules like AB -> 1 that have more than one non-terminal symbol on the left.


提交答案