什么是上下文无关语法？
有人可以向我解释一个上下文无关的语法是什么？ 看过维基百科条目，然后看维基百科的正式语法条目之后，我完全置之不理。 有人会这么好解释这些东西是什么？
我想知道这一点，因为我希望调查parsing，并在一边，正则expression式引擎的限制。
我不确定这些术语是直接编程相关的，还是与语言学有关。 如果是这样的话，我很抱歉，如果是这样的话，也许这可能会被移动？
上下文无关语法是满足某些特性的语法。 在计算机科学中，语法描述语言; 具体来说，他们描述的是正式语言
forms语言只是一个string（符号序列）的集合（对象集合的math术语），与string的编程用法非常相似）。 forms语言的一个简单例子是长度为3的所有二进制string{000,001,010,011,100,101,110,111}的集合。
文法通过定义转换来工作，用语法描述的语言来构造一个string。 文法将会说如何将开始符号（通常是S）转换成一些符号串。 以前给出的语言的语法是：
S -> BBB B -> 0 B -> 1
解释这个的方法是说S可以用B代替，B可以用0代替，B可以用1代替。所以构造string010可以做S→BBB→0BB→ 01B – > 010。
上下文无关的语法只是一个语法，你正在replace的东西（箭头的左边）是一个单一的“非终结符号”。 非终结符号是您在语法中使用的任何符号，不能出现在最终的string中。 在上面的语法中，“S”和“B”是非terminal符号，“0”和“1”是“terminal”符号。 文法就像
S -> AB AB -> 1 A -> AA B -> 0
不规则，因为它们包含像“AB – > 1”这样的规则。
语言理论与计算理论有关。 哪一个是计算机科学更哲学的一面，关于决定哪些程序是可能的，哪些程序是可能写的，以及写出algorithm要解决什么types的问题是不可能的。
正则expression式是描述正规语言的一种方式。 常规语言是一种可以由确定性有限自动机决定的语言。
您应该阅读有限状态机上的文章： http ： //en.wikipedia.org/wiki/Finite_state_machine
和常规语言： http : //en.wikipedia.org/wiki/Regular_language
所有正则语言都是上下文无关语言，但是有上下文无关语言是不正规的。 上下文无关语言是由上下文无关语法或下推自动机接受的所有string的集合，它是一个具有单个堆栈的有限状态机： http : //en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages
还有更复杂的语言需要一个图灵机（任何可能的程序，你可以写在你的计算机上）来决定一个string是否在语言中。
语言理论也与P与NP问题以及其他一些有趣的东西非常相关。
“计算机科学导论”第三年的教材很好的解释了这个东西：计算理论导论。 由迈克尔Sipser。 但是，花了我160美元买新的，它不是很大。 也许你可以find一个使用的副本或在图书馆find一份副本或者它可能会帮助你。
编辑：
过去50多年来，正则expression式和高级语言课程的局限性已经被研究了很多。 你可能会对正规语言的抽象引理感兴趣。 这是certificate某种语言不规则的一种手段：
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
如果一个语言不规则，它可能是上下文无关的，这意味着它可以用上下文无关语法来描述，或者它甚至可以在更高级的语言类中，你可以certificate它不是上下文无关的上下文引理与正则expression式类似的语言。
一种语言甚至可能是不可判定的，这意味着即使是一个图灵机（你的计算机可以运行的程序）也不能被编程来判断一个string是应该被接受的语言还是被拒绝的。
我认为你最感兴趣的部分是有限状态机（既有确定性也有确定性），看看正则expression式可以决定什么语言，用抽象的引理来certificate哪些语言不规则。
基本上，一种语言如果需要某种内存或者数量的话，是不经常的。 匹配括号的语言是不规则的，例如，因为机器需要记住它是否打开了括号来知道是否必须closures它。
使用包含至less三个b的字母a和b的所有string的语言是常规语言：a ba ba ba
所有使用字母a和b的string包含的b比a更多的语言是不规则的。
你也不应该说所有有限的语言都是有规律的，例如：
使用包含更多b的字母a和b的所有string的长度小于50个字符的语言是规则的，因为它是有限的，我们知道它可以被描述为（b | abb | bab | bba | aabbb | ababb |。 ..）等，直到列出所有可能的组合。
