檢視形式文法的原始碼

{| class="wikitable" align="right"

|-

| style="background: #008080" align= center|  '''<big>形式文法</big> '''

|-

| 
[[File:0a00deffbd1644f7ba20f5185865c448.jpg|缩略图|居中|[http://5b0988e595225.cdn.sohucs.com/images/20181204/0a00deffbd1644f7ba20f5185865c448.jpeg 原图链接][http://www.sohu.com/a/279638828_273163 来自 搜狗 的图片]]]
	
|-	

| style="background: #008080" align= center|

|-

| align= light|

|} 
形式文法，计算机科学中的概念，在计算机科学中，形式语言是某个字母表上一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。

=='''目录'''==

'''形式文法举例'''

'''形式定义'''

'''例子'''

'''类别'''

'''0型文法'''

'''1型文法'''

'''2型文法'''

'''3型文法'''

=='''形式文法举例'''==

举例来说，假设字母表只包含 'a' 和 'b' 两个字符，初始符号是 'S' ，我们应用下述规则：

1. S -> aSb

2. S -> ba

于是我们可以通过把 "S" 重写为 "aSb"（规则1），我们还可以继续应用这条规则把 "aSb" 重写为 "aaSbb"。这个重写的过程不断重复，直到结果中只包含字母表中的字母为止。在例子中，我们可以得到 S -> aSb -> aaSbb -> aababb 这样的结果。由文法刻画的语言包含了所有可以这样产生的字串，比如 ba, abab, aababb, aaababbb 等等。

=='''形式定义'''==

一个形式文法 G 是下述元素构成的一个元组(N, Σ, P, S)：----有些书上也写成(V,T,S,P)

非终结符号集合 N。

终结符号集合 Σ ，Σ 与 N 无交。

取如下形式的一组产生式规则 P，

(Σ ∪ N)*中的字串 -> (Σ ∪ N)* 中的字串字串，并且产生式左侧的字串中必须至少包括一个非终结符号。

起始符号 S，S 属于 N。

一个由形式文法 G = (N, Σ, P, S) 产生的语言是所有如下形式字串的集合，这些字串全部由终结符号集 Σ 中符号构成，并且可以从初始符号 S 出发，不断应用 P 中的产生式规则而得到。

'''3例子'''

考虑如下的文法 G ，其中 N = {S, B}, Σ = {a, b, c}, P 包含下述规则

1. S -> aBSc

2. S -> abc

3. Ba -> aB

4. Bb -> bb

非终结符号 S 作为初始符号。下面给出字串推导的例子：（推导使用的产生规则用括号标出，替换的字串用黑体标出）

S -> (2) abc

S -> (1) aBSc -> (2) aBabcc -> (3) aaBbcc -> (4) aabbcc

S -> (1) aBSc -> (1) aBaBScc -> (2) aBaBabccc -> (3) aaBBabccc -> (3) aaBaBbccc -> (3) aaaBBbccc -> (4) aaaBbbccc -> (4) aaabbbccc

很清楚这个文法定义了语言 { anbncn| n > 0 } ，这里 an表示含有 n 个 a 的字串。

形式文法与 Lindenmayer 系统（L-系统）类似， 但有几点不同：L-系统不区分终结符号和非终结符号；L-系统限制规则的应用顺序；L-系统能不停地运行，产生一个无限长的字串行。通常情况下，每一个字串同空间中的一个点集联系起来，而L-系统的输出就是这个点集列的极限。L-系统可以用于模拟细胞的生长，所以又被称为发展系统。

'''4类别'''

某些类型的文法及其产生的语言得到了细致的研究并被[[单独命名]]。最常见的文法的分类系统是诺姆·乔姆斯基于1950年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四种类型：即0型、1型、2型和3型，又可以分别称为无限制文法、上下文相关文法、上下文无关文法和正规文法。任何语言都可以由无限制文法来表达，余下的三类文法对应的语言类分别是递归可枚举语言、上下文无关语言和[[正规语言]]。这四种文法类型依次拥有越来越严格的产生式规则，同时文法所能表达的语言也越来越少。尽管表达能力比无限制文法和上下文相关文法要弱，但由于能高效率的实现，四类文法中最重要的是上下文无关文法和正规文法。例如对上下文无关语言存在算法可以生成高效率的LL 分析器和LR 分析器。

'''50型文法'''

设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。

'''61型文法'''

1型文法也叫上下文有关文法，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。

'''72型文法'''<ref>[https://www.zhihu.com/question/427372939  形式文法],搜狗, 2016-05-13</ref> 

2型文法也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个[[非终结符]]。

'''83型文法'''

3型文法也叫正规文法，它对应于有限状态自动机。正规文法有多种等价的定义，我们可以用左线性文法或者右线性文法来等价地定义正规文法。左线性文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号後随一个终结符号。右线性文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个[[终结符号]]或者一个终结符号後随一个非终结符号。 它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。

如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个终结符+一个非终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时在一个语法中出现,只能完全满足其中的一个,才能算3型文法。

=='''参考资料'''==
{{Reflist}}

[[Category:540 社會學總論]]