形式語法

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

形式文法描述形式語言的基本想法是，從一個特殊的初始符合出發，不斷的應用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設字母表只包含 '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 中的產生式規則而得到。

例子

考慮如下的文法 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-系統可以用於模擬細胞的生長，所以又被稱為發展系統。

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

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

1型文法也叫上下文有關文法，此文法對應於線性有界自動機。它是在0型文法的基礎上每一個α→β,都有|β|>=|α|。這裡的|β|表示的是β的長度。

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

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

2型文法也叫上下文無關文法，它對應於下推自動機。2型文法是在1型文法的基礎上，再滿足：每一個α→β都有α是非終結符。如A->Ba,符合2型文法要求。

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

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型文法。

注意：上面例子中的大寫字母表示的是非終結符，而小寫字母表示的是終結符。