有人可以向我解释一下上下文无关语法是什么吗？在查看维基百科条目，然后查看关于正式语法的维基百科条目后，我完全被遗忘了 . 有人会这么好解释这些东西是什么吗？
我想知道这一点，因为我希望调查解析，以及一方面，正则表达式引擎的限制 .
我不确定这些术语是否与编程直接相关，或者它们是否与语言学有关 . 如果是这样的话，我道歉，如果是这样的话可能会被移动？
无上下文语法是满足某些属性的语法 . 在计算机科学中，语法描述语言;具体来说，他们描述了正式语言
形式语言只是字符串的集合（对象集合的数学术语）（符号序列......非常类似于单词“string”的编程用法） . 形式语言的简单示例是长度为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
BBB
B
S -> BBB -> 0BB -> 01B -> 010
无上下文语法只是一种语法，你要替换的东西（箭头的左边）是一个单一的“非终端”符号 . 非终端符号是您在语法中使用的任何符号，不能出现在最终字符串中 . 在上面的语法中，“S”和“B”是非终端符号，“0”和“1”是“终端”符号 . 语法就像
S -> AB AB -> 1 A -> AA B -> 0
不规则，因为它们包含“AB - > 1”之类的规则 .
语言理论与计算理论有关 . 这是计算机科学中更具哲学性的一面，关于决定哪些程序是可能的，哪些程序是可能的，以及哪种类型的问题是不可能编写算法来解决的 .
正则表达式是一种描述常规语言的方式 . 常规语言是可以由确定性有限自动机决定的语言 .
你应该阅读有限状态机上的文章：http://en.wikipedia.org/wiki/Finite_state_machine
和常规语言：http://en.wikipedia.org/wiki/Regular_language
所有常规语言都是上下文自由语言，但有不常规的上下文自由语言 . 上下文无关语言是由Context Free Grammer或Pushdown Automata接受的所有字符串的集合，它是具有单个堆栈的有限状态机：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
如果一种语言不规则，它可能是Context Free，这意味着它可以由Context Free Grammer描述，或者它甚至可能在更高的语言类中，你可以通过Context Free的泵浦引理证明它不是Context Free语言类似于正则表达式的语言 .
一种语言甚至可能是不可判定的，这意味着即使是图灵机（可能使您的计算机可以运行）也无法编程来决定是否应该接受字符串或被拒绝 .
我认为您最感兴趣的部分是有限状态机（确定性和确定性），以查看正则表达式可以决定的语言，以及用于证明哪些语言不规则的抽象引理 .
基本上，如果语言需要某种记忆或计数能力，那么它就不常见 . 的语言匹配括号不是常规的，例如因为机器需要记住它是否已打开括号以知道它是否必须关闭一个括号 .
使用包含至少三个b的字母a和b的所有字符串的语言是常规语言：abababa
使用包含比a更多b的字母a和b的所有字符串的语言不规则 .
此外，你不应该认为所有有限语言都是常规的，例如：
使用包含比a更多b的字母a和b的所有字符串长度小于50个字符的语言是常规的，因为它是有限的我们知道它可以被描述为（b | abb | bab | bba | aabbb | ababb | . ..）等，直到列出所有可能的组合 .
2 回答
无上下文语法是满足某些属性的语法 . 在计算机科学中，语法描述语言;具体来说，他们描述了正式语言
形式语言只是字符串的集合（对象集合的数学术语）（符号序列......非常类似于单词“string”的编程用法） . 形式语言的简单示例是长度为3的所有二进制字符串的集合，{000,001,010,011,100,101,110,111} .
语法通过定义可以用语法描述的语言构造字符串的转换来工作 . 语法将说明如何将起始符号（通常为S）转换为某些符号串 . 以前给出的语言的语法是：
解释这个的方法是说
S可以被BBB替换，B可以替换为0，B可以替换为1.所以要构造字符串010，我们可以做S -> BBB -> 0BB -> 01B -> 010.无上下文语法只是一种语法，你要替换的东西（箭头的左边）是一个单一的“非终端”符号 . 非终端符号是您在语法中使用的任何符号，不能出现在最终字符串中 . 在上面的语法中，“S”和“B”是非终端符号，“0”和“1”是“终端”符号 . 语法就像
不规则，因为它们包含“AB - > 1”之类的规则 .
语言理论与计算理论有关 . 这是计算机科学中更具哲学性的一面，关于决定哪些程序是可能的，哪些程序是可能的，以及哪种类型的问题是不可能编写算法来解决的 .
正则表达式是一种描述常规语言的方式 . 常规语言是可以由确定性有限自动机决定的语言 .
你应该阅读有限状态机上的文章：http://en.wikipedia.org/wiki/Finite_state_machine
和常规语言：http://en.wikipedia.org/wiki/Regular_language
所有常规语言都是上下文自由语言，但有不常规的上下文自由语言 . 上下文无关语言是由Context Free Grammer或Pushdown Automata接受的所有字符串的集合，它是具有单个堆栈的有限状态机：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
如果一种语言不规则，它可能是Context Free，这意味着它可以由Context Free Grammer描述，或者它甚至可能在更高的语言类中，你可以通过Context Free的泵浦引理证明它不是Context Free语言类似于正则表达式的语言 .
一种语言甚至可能是不可判定的，这意味着即使是图灵机（可能使您的计算机可以运行）也无法编程来决定是否应该接受字符串或被拒绝 .
我认为您最感兴趣的部分是有限状态机（确定性和确定性），以查看正则表达式可以决定的语言，以及用于证明哪些语言不规则的抽象引理 .
基本上，如果语言需要某种记忆或计数能力，那么它就不常见 . 的语言匹配括号不是常规的，例如因为机器需要记住它是否已打开括号以知道它是否必须关闭一个括号 .
使用包含至少三个b的字母a和b的所有字符串的语言是常规语言：abababa
使用包含比a更多b的字母a和b的所有字符串的语言不规则 .
此外，你不应该认为所有有限语言都是常规的，例如：
使用包含比a更多b的字母a和b的所有字符串长度小于50个字符的语言是常规的，因为它是有限的我们知道它可以被描述为（b | abb | bab | bba | aabbb | ababb | . ..）等，直到列出所有可能的组合 .