什么是上下文无关文法？(What is a Context Free Grammar?)

能向我解释的人上下文无关文法是什么？看维基百科条目，然后在正式语法的维基百科条目后，我离开了彻底和完全糊涂。会有人这么好心来解释这些东西是什么？

我想知道这是因为我希望研究分析，并就在旁边，正则表达式引擎的局限性。

我不知道，如果这些条款是直接相关的编程，或者如果他们更多地涉及普通语言学。如果是这样的话，我很抱歉，这也许可以移动，如果这样的吗？

Answer 1:

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

正式的语言只是字符串（符号序列......非常相似的单词“串”的编程使用）的集（对象的集合数学术语）。形式语言的一个简单的例子是一组长度为三，所有二进制串{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问题，以及其他一些有趣的东西非常相关。

我的计算机科学导论高三的课本是在解释这个东西不错：介绍计算理论。由迈克尔·西蓬瑟。但是，它花了我像$ 160买新的，它不是非常大。也许你可以找到一个用于复制或在图书馆找到一个副本或东西它可能会帮助你。

编辑：

正则表达式和较高的语言课程的局限性进行了研究一吨，在过去50年左右。你可能会感兴趣的抽水引理正规语言。这是证明某种语言是不正规的手段：

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

如果语言是不经常也可能是上下文无关，这意味着它可以通过上下文无关格拉默描述，或者它可能是，即使在较高的语文课上，你能证明它不是上下文无关由泵引理上下文无关语言是一个类似于正则表达式。

语言甚至可以是不可判定的，这意味着即使是图灵机（可以编程您的计算机可以运行）不能进行编程，以决定是否字符串应该接受的语言或拒绝。

我觉得你最感兴趣的部分是有限状态机（无论确定性和确定性）看到一个正则表达式可以决定哪些语言和汲取引理来证明其语言都是不正规的。

基本上，如果它需要某种形式的内存或计算能力的语言不是正规。因为机器需要记住，如果它已经开了一个括号知道它是否有关闭一个括号匹配的语言不是正规的例子。

使用字母A和B至少包含三个B的所有字符串的语言是正规语言： 学士学位 捌

使用字母a和b的所有字符串包含多个B的比的语言是不正规。