形式文法

　　在計算機科學(xué)中，形式語言是某個字母表上一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名，是因為它與人類自然語言中的文法相似的緣故。

　　形式文法描述形式語言的基本想法是，從一個特殊的初始符合出發(fā)，不斷的應(yīng)用一些產(chǎn)生式規(guī)則，從而生成出一個字串的集合。產(chǎn)生式規(guī)則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設(shè)字母表只包含 'a' 和 'b' 兩個字符，初始符號是 'S' ，我們應(yīng)用下述規(guī)則：

　　1. S -> aSb

　　2. S -> ba

　　于是我們可以通過把 "S" 重寫為 "aSb"（規(guī)則1），我們還可以繼續(xù)應(yīng)用這條規(guī)則把 "aSb" 重寫為 "aaSbb"。這個重寫的過程不斷重復(fù)，直到結(jié)果中只包含字母表中的字母為止。在例子中，我們可以得到 S -> aSb -> aaSbb -> aababb 這樣的結(jié)果。由文法刻畫的語言包含了所有可以這樣產(chǎn)生的字串，比如 ba, abab, aababb, aaababbb 等等。

形式定義

　　一個形式文法 G 是下述元素構(gòu)成的一個元組(N, Σ, P, S)：----有些書上也寫成(V,T,S,P)

　　非終結(jié)符號集合 N。

　　終結(jié)符號集合 Σ ，Σ 與 N 無交。

　　取如下形式的一組產(chǎn)生式規(guī)則 P，

　　(Σ ∪ N)*中的字串 -> (Σ ∪ N)* 中的字串字串，并且產(chǎn)生式左側(cè)的字串中必須至少包括一個非終結(jié)符號。

　　起始符號 S，S 屬于 N。

　　一個由形式文法 G = (N, Σ, P, S) 產(chǎn)生的語言是所有如下形式字串的集合，這些字串全部由終結(jié)符號集 Σ 中符號構(gòu)成，并且可以從初始符號 S 出發(fā)，不斷應(yīng)用 P 中的產(chǎn)生式規(guī)則而得到。

例子

　　考慮如下的文法 G ，其中 N = {S, B}, Σ = {a, b, c}, P 包含下述規(guī)則

　　1. S -> aBSc

　　2. S -> abc

　　3. Ba -> aB

　　4. Bb -> bb

　　非終結(jié)符號 S 作為初始符號。下面給出字串推導(dǎo)的例子：（推導(dǎo)使用的產(chǎn)生規(guī)則用括號標出，替換的字串用黑體標出）

　　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 系統(tǒng)（L-系統(tǒng)）類似， 但有幾點不同：L-系統(tǒng)不區(qū)分終結(jié)符號和非終結(jié)符號；L-系統(tǒng)限制規(guī)則的應(yīng)用順序；L-系統(tǒng)能不停地運行，產(chǎn)生一個無限長的字串行。通常情況下，每一個字串同空間中的一個點集聯(lián)系起來，而L-系統(tǒng)的輸出就是這個點集列的極限。L-系統(tǒng)可以用于模擬細胞的生長，所以又被稱為發(fā)展系統(tǒng)。

[編輯本段]

文法的分類

　　某些類型的文法及其產(chǎn)生的語言得到了細致的研究并被單獨命名。最常見的文法的分類系統(tǒng)是諾姆·喬姆斯基于1950年發(fā)展的喬姆斯基譜系，這個分類譜系把所有的文法分成四種類型：即0型、1型、2型和3型，又可以分別稱為無限制文法、上下文相關(guān)文法、上下文無關(guān)文法和正規(guī)文法。任何語言都可以由無限制文法來表達，馀下的三類文法對應(yīng)的語言類分別是遞歸可枚舉語言、上下文無關(guān)語言和正規(guī)語言。這四種文法類型依次擁有越來越嚴格的產(chǎn)生式規(guī)則，同時文法所能表達的語言也越來越少。盡管表達能力比無限制文法和上下文相關(guān)文法要弱，但由于能高效率的實現(xiàn)，四類文法中最重要的是上下文無關(guān)文法和正規(guī)文法。例如對上下文無關(guān)語言存在算法可以生成高效率的LL 分析器和LR 分析器。

0型文法

　　設(shè)G=（VN，VT，P，S），如果它的每個產(chǎn)生式α→β是這樣一種結(jié)構(gòu)：α∈(VN∪VT)*且至少含有一個非終結(jié)符，而β∈(VN∪VT)*，則G是一個0型文法。0型文法也稱短語文法。一個非常重要的理論結(jié)果是：0型文法的能力相當于圖靈機(Turing)。或者說，任何0型文語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。0型文法是這幾類文法中，限制最少的一個，所以我們在試題中見到的,至少是0型文法。

1型文法

　　1型文法也叫上下文有關(guān)文法，此文法對應(yīng)于線性有界自動機。它是在0型文法的基礎(chǔ)上每一個α→β,都有|β|>=|α|。這里的|β|表示的是β的長度。

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

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

2型文法

2型文法也叫上下文無關(guān)文法，它對應(yīng)于下推自動機。2型文法是在1型文法的基礎(chǔ)上,再滿足：每一個α→β都有α是非終結(jié)符。如A->Ba,符合2型文法要求。

　　如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因為其α=Ab，而Ab不是一個非終結(jié)符。

3型文法

3型文法也叫正規(guī)文法，它對應(yīng)于有限狀態(tài)自動機。正規(guī)文法有多種等價的定義，我們可以用左線性文法或者右線性文法來等價地定義正規(guī)文法。左線性文法要求產(chǎn)生式的左側(cè)只能包含一個非終結(jié)符號，產(chǎn)生式的右側(cè)只能是空串、一個終結(jié)符號或者一個非終結(jié)符號後隨一個終結(jié)符號。右線性文法要求產(chǎn)生式的左側(cè)只能包含一個非終結(jié)符號，產(chǎn)生式的右側(cè)只能是空串、一個終結(jié)符號或者一個終結(jié)符號後隨一個非終結(jié)符號。 它是在2型文法的基礎(chǔ)上滿足:A→α|αB（右線性）或A→α|Bα（左線性）。

　　如有：A->a,A->aB,B->a,B->cB，則符合3型文法的要求。但如果推導(dǎo)為:A->ab,A->aB,B->a,B->cB或推導(dǎo)為:A->a,A->Ba,B->a,B->cB則不符合3型方法的要求了。具體的說，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定義,如果把后面的ab,改成“一個非終結(jié)符＋一個終結(jié)符”的形式（即為aB）就對了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改為B->Bc的形式就對了,因為A→α|αB（右線性）和A→α|Bα（左線性）兩套規(guī)則不能同時出現(xiàn)在一個語法中,只能完全滿足其中的一個,才能算3型文法。

　　注意：上面例子中的大寫字母表示的是非終結(jié)符,而小寫字母表示的是終結(jié)符。