基本介紹
- 中文名：形式語法
- 外文名：formal grammar
- 所屬學科：計算機科學
簡介,形式定義,文法分類,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 等等。
形式文法描述形式語言的基本想法是，從一個特殊的初始符合出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設字母表只包含 '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-系統可以用於模擬細胞的生長，所以又被稱為發展系統。
非終結符號集合 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 分析器。
0型文法
設G=（VN，VT，P，S），如果它的每個產生式α→β是這樣一種結構：α∈(VN∪VT)*且至少含有一個非終結符，而β∈(VN∪VT)*，則G是一個0型文法。0型文法也稱短語文法。一個非常重要的理論結果是：0型文法的能力相當於圖靈機(Turing)。或者說，任何0型文語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個0型語言。0型文法是這幾類文法中，限制最少的一個，所以我們在試題中見到的,至少是0型文法。
1型文法
1型文法也叫上下文有關文法，此文法對應於線性有界自動機。它是在0型文法的基礎上每一個α→β,都有|β|>=|α|。這裡的|β|表示的是β的長度。
注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。
如有A->Ba則|β|=2,|α|=1符合1型文法要求。反之,如aA->a，則不符合1型文法。
注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。
如有A->Ba則|β|=2,|α|=1符合1型文法要求。反之,如aA->a，則不符合1型文法。
2型文法
2型文法也叫上下文無關文法，它對應於下推自動機。2型文法是在1型文法的基礎上,再滿足：每一個α→β都有α是非終結符。如A->Ba,符合2型文法要求。
如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因為其α=Ab，而Ab不是一個非終結符。
如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因為其α=Ab，而Ab不是一個非終結符。
3型文法
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型文法。
注意：上面例子中的大寫字母表示的是非終結符,而小寫字母表示的是終結符。
如有：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型文法。
注意：上面例子中的大寫字母表示的是非終結符,而小寫字母表示的是終結符。
