上下文無關文法

形式語言理論中一種重要的變換文法,用來描述上下文無關語言,在喬姆斯基分層中稱為2型文法。由於程式設計語言的語法基本上都是上下文無關文法,因此套用十分廣泛。

簡介

上下文無關文法(Context-Free Grammar, CFG)

在計算機科學中,若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式:V -> w,則稱之為上下文無關的,其中 V∈N ,w∈(N∪Σ)* 。上下文無關文法取名為"上下文無關"的原因就是因為字元 V 總可以被字串 w 自由替換,而無需考慮字元 V 出現的上下文。一個形式語言是上下文無關的,如果它是由上下文無關文法生成的﹙條目上下文無關語言﹚。

上下文無關文法上下文無關文法

上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程式設計語言的語法;實際上,幾乎所有程式設計語言都是通過上下文無關文法來定義的。另一方面,上下文無關文法又足夠簡單,使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見 LR 分析器和 LL 分析器。

上下文無關文法上下文無關文法

BNF ﹙巴克斯-諾爾範式﹚經常用來表達上下文無關文法。

文法規則使用相似的表示法。名字用斜體表示(但它是一種不同的字型,所以可與正則表達式相區分)。豎線仍表示作為選擇的元符號。並置也用作一種標準運算。但是這裡沒有重複的元符號(如正則表達式中的星號*),稍後還會再講到它。表示法中的另一個差別是現在用箭頭符號"→"代替了等號來表示名字的定義。這是由於現在的名字不能簡單地由其定義取代,而需要更為複雜的定義過程來表示,這是由定義的遞歸本質決定的。

上下文無關文法上下文無關文法

正則表達式類似,文法規則是定義在一個字母表或符號集之上。在正則表達式中,這些符號通常就是字元,而在文法規則中,符號通常是表示字元串的記號。我們利用C中的枚舉類型定義了在掃描程式中的記號;為了避免涉及到特定實現語言(例如C)中表示記號的細節,就使用了正則表達式本身來表示記號。此時的記號就是一個固定的符號,如同在保留字 while 中或諸如+或: =這樣的特殊符號一樣,對於作為表示多於一個串的標識符和數的記號來說,代碼字型為斜體,這就同假設這個記號是正則表達式的名字(這是它經常的表示)一樣。

上下文無關文法的卻利用了與正則表達式中極為類似的命名慣例和運算,二者的主要區別在於上下文無關文法的規則是遞歸的(recursive)。

例子

例子 1

一個簡單的上下文無關文法的例子是:S -> aSb | ε。這個文法產生了語言 {anbn : n ≥ 0} 。不難證明這個語言不是正規的。

例子 2

這個例子可以產生變數 x,y,z 的算術表達式:

S -> T + S | T - S | T

T -> T * T | T / T | ( S ) | x | y | z

例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用這個文法來產生。

例子 3

字母表 {a,b} 上 a 和 b 數目不相等的所有字串可以由下述文法產生:

上下文無關文法上下文無關文法

S -> U | V

U -> TaU | TaT

V -> TbV | TbT

T -> aTbT | bTaT | ε

這裡 T 可以產生 a 和 b 數目相等的所有字串,U 可以產生 a 的數目多於 b 的數目的所有字串, V 可以產生 a 的數目少於 b 的數目的所有字串。

範式

每一個不生成空串的上下文無關文法都可以轉化為等價的 Chomsky 範式或 Greibach 範式。這裡兩個文法等價的含義指它們生成相同的語言。

上下文無關文法上下文無關文法

由於 Chomsky範式在形式上非常簡單,所以它在理論和實踐上都有套用。比如,對每一個上下文無關語言,我們可以利用 Chomsky範式構造一個多項式算法,用它來判斷一個給定字串是否屬於這個語言﹙CYK 算法﹚。

同態映射

對任意正整數n,令…,an},Σ'n={a'1,…,a'n},定義喬姆斯基變換文法G=(ΣVSP)為(Σn∪Σ'n,S,S,P={S→,SSaiSa'iS|1≤in})。這個文法生成的語言稱為代克集。如果把ai看作開括弧,把a'i看作相應的閉括弧,則n維代克集Dn就是由幾種不同的括弧對組成的配對序列之集合。例如,a1a2a2a'2a2a'1和a1a'1a2a'2a1a'1都屬於D2,用括弧表示時可以寫成(〔( )〕)和( )〔 〕( )。

上下文無關文法上下文無關文法

代克集是把正則語言族擴大成上下文無關語言族的工具。對任一上下文無關語言L,必存在兩個同態映射h1和h2,以及一個正則語言R,使L=h2【h1(D2)∩R】,其中D2是二維代克集,反之亦然。

更進一步,上下文無關語言族是包含D2,且在同態、逆同態和與正則語言相交三種代數運算下封閉的最小語言族。加上乘積和乘冪閉包兩種運算後,此結論仍真。

文法形式

文法形式

在兩種符號置換的意義下(終結符和非終結符分別替換), 許多文法之間有著相似性。把一組彼此相似的文法抽象成一個更高級的形式體系,就叫作文法形式。迄今,文法形式的研究主要集中在上下文無關文法上。

文法形式的具體定義是:給定無限的終結符表Σ∞和無限的非終結符表V∞。任取Σ∞和V∞的非空子集ΣV,按構造普通文法的方法定義一個四元組G=(ΣVSP)。在G確定以後,任取映射函式ψ,把Σ中每一元素a映為Σ∞中一有限子集ψ(a),把V中每一元素A映為V∞中一個有限子集ψ(A),且當AB時有ψ(A)∩ψ(B)=φψ就是所需的置換。通過它得到一個具體文法ψ(G)=【ψ(Σ),ψ(V),ψ(S),ψ(P)】,其中ψ(P)是把P中所有產生式中的符號作ψ置換後得到的一組新產生式,ψ(Σ),ψ(V)和ψ(S)分別是ψ(P)中出現的終結符集,非終結符集和出發符號。

文法的相似性

這樣的G稱為文法形式,ψ稱為G的一個解釋,ψ(G)是G的一個解釋文法,被認為是相似於G。令ψ遍歷各種可能的解釋,得到的ψ(G)集合稱為G的文法性語言族,由此生成的語言集合(ψ(G))稱為G的文法性語言族。例如,文法形式{SaSSa}的文法性語言族是正則語言集;{SSSSa}的文法性語言族是上下文無關語言集。

若文法形式G作為普通文法時生成的語言(G)是無限集,則稱G為非平凡的。此時文法性語言族(G)是一個滿主半AFL,反之不然。如滿主半AFL({abn≥1}),不是一個文法性語言族。

以G1·G2表文法性語言族G1和G2的乘積,1∩2表兩者之並,它們仍是文法性語言族。當吇G1G2時,必有G吇G1或G吇G2成立,則稱G是素的。正則語言集和線性語言集都是素文法性語言族。任一文法性語言族G必可唯一地分解為它的素因子乘積和:G=(11…1n1)∪…∪(m1…mnm)。其中每個Gij都是素因子。這個分解在乘積運算∪可交換的意義下是唯一的。

文法的二義性

從文法生成語言,可有多種推導公式。例如文法{SABAa,Bb}可有兩種推導:SABaBabSABAbab。若每次都取最左邊的非終結符進行推導,如上例中的前一種方式那樣,則稱為左推導。如果有兩種不同的左推導推出同一結果,則稱此文法是二義性的,反之是無二義文法。對有些二義性文法,可找到一個等價的無二義文法,生成同一個語言。不具有無二義文法的語言稱為本質二義性語言。例如,{SA,Sa,Aa}是二義性文法。

上下文無關文法上下文無關文法

是本質二義性語言。

子文法類

可以根據不同的觀點取上下文無關文法的子文法。一種觀點是根據文法的外形和它們生成的語言族在代數運算下的封閉性。例如,若文法G的產生式只具有下列三種形式之一:AαBβCγSδ,其中ABCVαβγΣδ∈(ΣV),且δ中至多含k個非終結符,S是出發符號,則稱Gk線性文法。1線性文法又稱線性文法。全體k線性文法之集合稱為元線性文法。元線性語言族在聯合和乘積運算下是封閉的,但在求交,求補,乘冪閉包和置換等運算下都不封閉。從包含關係說,正則語言族真包含於線性語言族。對任一k≥1,k線性語言族真包含於k1線性語言族,元線性語言族真包含於上下文無關語言族。

由於上下文無關文法被廣泛地套用於描述計算機語言的語法,因此更重要的是從機械執行語法分解的角度取上下文無關文法的子文法,最重要的一類就是無二義的上下文無關文法,因為無二義性對於計算機語言的語法分解至為重要。在無二義的上下文無關文法中最重要的子類是LR(k)文法,它只要求向前看k個符號即能作正確的自左至右語法分解。LR(k)文法能描述所有的確定型上下文無關語言。

其它詞條