形式文法

形式文法,計算機科學中的概念,在計算機科學中,形式語言是某個字母表上一些有限長字串的集合,而形式文法是描述這個集合的一種方法。形式文法之所以這樣命名,是因為它與人類自然語言中的文法相似的緣故。形式文法描述形式語言的基本想法是,從一個特殊的初始符號出發,不斷的套用一些產生式規則,從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。

基本介紹

  • 中文名:形式文法
  • 類屬:計算機科學
  • 描述:集合
  • 相似:人類自然語言中的文法
形式文法舉例,形式定義,例子,類別,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 中的產生式規則而得到。

例子

考慮如下的文法 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型文法。

2型文法

2型文法也叫上下文無關文法,它對應於下推自動機。2型文法是在1型文法的基礎上,再滿足:每一個α→β都有α是非終結符。如A->Ba,符合2型文法要求。
如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型文法。
注意:上面例子中的大寫字母表示的是非終結符,而小寫字母表示的是終結符。

相關詞條

熱門詞條

聯絡我們