什么是无语语法？

Question

有人可以向我解释一下上下文无关语法是什么吗？在查看维基百科条目,然后查看关于正式语法的维基百科条目后,我完全被遗忘了.有人会这么好解释这些东西是什么吗？

我想知道这一点,因为我希望调查解析,以及一方面,正则表达式引擎的限制.

我不确定这些术语是否与编程直接相关,或者它们是否与语言学有关.如果是这样的话,我道歉,如果是这样的话可能会被移动？

Answer 1

无上下文语法是满足某些属性的语法.在计算机科学中,语法描述语言; 具体来说,他们描述了正式语言

形式语言只是字符串的集合(对象集合的数学术语)(符号序列......非常类似于单词"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"和"B"是非终端符号,"0"和"1"是"终端"符号.语法就像

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

不规则,因为它们包含"AB - > 1"之类的规则.

通过'不定期',你的意思是'不上下文'？(因为CFG可表示的语言是正则表达式可表示的语言的超集) (11认同)
应该"S可以被B替换"读"S可以被BBB取代"？ (3认同)
好主人,这是我在SO上看到的最好的解释答案之一. (3认同)
@AntiEarth第二个例子不是常规语法，因为它具有从单个非终结符生成两个非终结符的规则，这在常规语法中是不允许的（而且，正如OP指出的，它具有多个非终结符的规则）左边）。https://en.wikipedia.org/wiki/Regular_grammar (2认同)

Answer 2

语言理论与计算理论有关.这是计算机科学中更具哲学性的一面,关于决定哪些程序是可能的,哪些程序是可能的,以及哪种类型的问题是不可能编写算法来解决的.

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

所有常规语言都是上下文自由语言,但有不常规的上下文自由语言.上下文无关语言是所有行的集合由上下文无关格拉默或下推自动这是一个有限状态机与单栈接受:http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

有更复杂的语言需要图灵机(您可以在计算机上编写任何可能的程序)来决定字符串是否使用该语言.

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

我的计算机科学入门三年级教科书很擅长解释这些东西:计算理论导论.迈克尔西普尔.但是,购买新产品需要花费160美元,而且价格不是很高.也许你可以找到一个旧的副本或在图书馆找到一个副本或它可能对你有所帮助.

编辑:

在过去50年左右的时间里,正规表达式和高级语言课程的局限性已经被研究了很多.您可能对常规语言的泵浦引理感兴趣.这是一种证明某种语言不规律的方法:

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

一种语言甚至可能是不可判定的,这意味着即使是图灵机(可能使您的计算机可以运行)也无法编程来决定是否应该接受字符串或被拒绝.

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

基本上,如果语言需要某种记忆或计数能力,那么它就不常见.匹配括号的语言不是常规的,例如因为机器需要记住它是否已打开括号以知道它是否必须关闭一个括号.

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

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

此外,你不应该认为所有有限语言都是常规的,例如:

所有字符串的语言少于50个字符使用含有较多的B的比的是有规律的,因为它是有限的,我们知道它可以被描述为(B字母a和b | ABB | BAB | BBA | aabbb | ababb |. ..)等,直到列出所有可能的组合.