形式文法
在計(jì)算機(jī)科學(xué)中，形式語(yǔ)言是某個(gè)字母表上一些有限長(zhǎng)字串的集合，而形式文法是描述這個(gè)集合的一種方法。形式文法之所以這樣命名，是因?yàn)樗c人類自然語(yǔ)言中的文法相似的緣故。
形式文法描述形式語(yǔ)言的基本想法是，從一個(gè)特殊的初始符合出發(fā)，不斷的應(yīng)用一些產(chǎn)生式規(guī)則，從而生成出一個(gè)字串的集合。產(chǎn)生式規(guī)則指定了某些符號(hào)組合如何被另外一些符號(hào)組合替換。舉例來(lái)說(shuō)，假設(shè)字母表只包含 'a' 和 'b' 兩個(gè)字符，初始符號(hào)是 'S' ，我們應(yīng)用下述規(guī)則：
1. S -> aSb
2. S -> ba
于是我們可以通過(guò)把 "S" 重寫為 "aSb"（規(guī)則1），我們還可以繼續(xù)應(yīng)用這條規(guī)則把 "aSb" 重寫為 "aaSbb"。這個(gè)重寫的過(guò)程不斷重復(fù)，直到結(jié)果中只包含字母表中的字母為止。在例子中，我們可以得到 S -> aSb -> aaSbb -> aababb 這樣的結(jié)果。由文法刻畫(huà)的語(yǔ)言包含了所有可以這樣產(chǎn)生的字串，比如 ba, abab, aababb, aaababbb 等等。
形式定義
一個(gè)形式文法 G 是下述元素構(gòu)成的一個(gè)元組(N, Σ, P, S)：----有些書(shū)上也寫成(V,T,S,P)
非終結(jié)符號(hào)集合 N。
終結(jié)符號(hào)集合 Σ ，Σ 與 N 無(wú)交。
取如下形式的一組產(chǎn)生式規(guī)則 P，
(Σ ∪ N)*中的字串 -> (Σ ∪ N)* 中的字串字串，并且產(chǎn)生式左側(cè)的字串中必須至少包括一個(gè)非終結(jié)符號(hào)。
起始符號(hào) S，S 屬于 N。
一個(gè)由形式文法 G = (N, Σ, P, S) 產(chǎn)生的語(yǔ)言是所有如下形式字串的集合，這些字串全部由終結(jié)符號(hào)集 Σ 中符號(hào)構(gòu)成，并且可以從初始符號(hào) 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é)符號(hào) S 作為初始符號(hào)。下面給出字串推導(dǎo)的例子：（推導(dǎo)使用的產(chǎn)生規(guī)則用括號(hào)標(biāo)出，替換的字串用黑體標(biāo)出）
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
很清楚這個(gè)文法定義了語(yǔ)言 { anbncn | n > 0 } ，這里 an 表示含有 n 個(gè) a 的字串。
形式文法與 Lindenmayer 系統(tǒng)（L-系統(tǒng)）類似， 但有幾點(diǎn)不同：L-系統(tǒng)不區(qū)分終結(jié)符號(hào)和非終結(jié)符號(hào)；L-系統(tǒng)限制規(guī)則的應(yīng)用順序；L-系統(tǒng)能不停地運(yùn)行，產(chǎn)生一個(gè)無(wú)限長(zhǎng)的字串行。通常情況下，每一個(gè)字串同空間中的一個(gè)點(diǎn)集聯(lián)系起來(lái)，而L-系統(tǒng)的輸出就是這個(gè)點(diǎn)集列的極限。L-系統(tǒng)可以用于模擬細(xì)胞的生長(zhǎng)，所以又被稱為發(fā)展系統(tǒng)。
[編輯本段]
文法的分類 某些類型的文法及其產(chǎn)生的語(yǔ)言得到了細(xì)致的研究并被單獨(dú)命名。最常見(jiàn)的文法的分類系統(tǒng)是諾姆·喬姆斯基于1950年發(fā)展的喬姆斯基譜系，這個(gè)分類譜系把所有的文法分成四種類型：即0型、1型、2型和3型，又可以分別稱為無(wú)限制文法、上下文相關(guān)文法、上下文無(wú)關(guān)文法和正規(guī)文法。任何語(yǔ)言都可以由無(wú)限制文法來(lái)表達(dá)，馀下的三類文法對(duì)應(yīng)的語(yǔ)言類分別是遞歸可枚舉語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言。這四種文法類型依次擁有越來(lái)越嚴(yán)格的產(chǎn)生式規(guī)則，同時(shí)文法所能表達(dá)的語(yǔ)言也越來(lái)越少。盡管表達(dá)能力比無(wú)限制文法和上下文相關(guān)文法要弱，但由于能高效率的實(shí)現(xiàn)，四類文法中最重要的是上下文無(wú)關(guān)文法和正規(guī)文法。例如對(duì)上下文無(wú)關(guān)語(yǔ)言存在算法可以生成高效率的LL 分析器和LR 分析器。
0型文法
設(shè)G=（VN，VT，P，S），如果它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu)：α∈(VN∪VT)*且至少含有一個(gè)非終結(jié)符，而β∈(VN∪VT)*，則G是一個(gè)0型文法。0型文法也稱短語(yǔ)文法。一個(gè)非常重要的理論結(jié)果是：0型文法的能力相當(dāng)于圖靈機(jī)(Turing)。或者說(shuō)，任何0型文語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。0型文法是這幾類文法中，限制最少的一個(gè)，所以我們?cè)谠囶}中見(jiàn)到的,至少是0型文法。
1型文法
1型文法也叫上下文有關(guān)文法，此文法對(duì)應(yīng)于線性有界自動(dòng)機(jī)。它是在0型文法的基礎(chǔ)上每一個(gè)α→β,都有|β|>=|α|。這里的|β|表示的是β的長(zhǎng)度。
注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。
如有A->Ba則|β|=2,|α|=1符合1型文法要求。反之,如aA->a，則不符合1型文法。
2型文法
2型文法也叫上下文無(wú)關(guān)文法，它對(duì)應(yīng)于下推自動(dòng)機(jī)。2型文法是在1型文法的基礎(chǔ)上,再滿足：每一個(gè)α→β都有α是非終結(jié)符。如A->Ba,符合2型文法要求。
如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因?yàn)槠洇?Ab，而Ab不是一個(gè)非終結(jié)符。
3型文法
3型文法也叫正規(guī)文法，它對(duì)應(yīng)于有限狀態(tài)自動(dòng)機(jī)。正規(guī)文法有多種等價(jià)的定義，我們可以用左線性文法或者右線性文法來(lái)等價(jià)地定義正規(guī)文法。左線性文法要求產(chǎn)生式的左側(cè)只能包含一個(gè)非終結(jié)符號(hào)，產(chǎn)生式的右側(cè)只能是空串、一個(gè)終結(jié)符號(hào)或者一個(gè)非終結(jié)符號(hào)後隨一個(gè)終結(jié)符號(hào)。右線性文法要求產(chǎn)生式的左側(cè)只能包含一個(gè)非終結(jié)符號(hào)，產(chǎn)生式的右側(cè)只能是空串、一個(gè)終結(jié)符號(hào)或者一個(gè)終結(jié)符號(hào)後隨一個(gè)非終結(jié)符號(hào)。 它是在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型方法的要求了。具體的說(shuō)，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定義,如果把后面的ab,改成“一個(gè)非終結(jié)符＋一個(gè)終結(jié)符”的形式（即為aB）就對(duì)了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改為B->Bc的形式就對(duì)了,因?yàn)锳→α|αB（右線性）和A→α|Bα（左線性）兩套規(guī)則不能同時(shí)出現(xiàn)在一個(gè)語(yǔ)法中,只能完全滿足其中的一個(gè),才能算3型文法。
注意：上面例子中的大寫字母表示的是非終結(jié)符,而小寫字母表示的是終結(jié)符。