【文章內(nèi)容簡介】 ck | i=j 或 j=k 且 i, j, k≥1} 便是這種語言。 文法和語言的分類 著名的語言學(xué)家 喬姆斯基 (Chomsky) 將文法和語言分為四大類，即 0型、 1型、 2型、 3型。劃分的依據(jù)是對文法中的規(guī)則施加不同的限制。 文法和語言的分類 ?0型文法（無限制文法） 若文法 G=(VN,VT, P, S)中的每條規(guī)則 α?β 是這樣一種結(jié)構(gòu)： 而且 α中至少含一個非終結(jié)符 , 則稱 G 是 0型文法 。 α?(VN∪ VT)+ , β?(VN∪ VT)* 0型文法描述的語言是0型語言。 0型文法沒有加任何限制條件，又稱為 無限制性文法，相應(yīng)的語言稱為 無限制 性語言 。 0型語言由圖靈機(jī)識別。 文法和語言的分類 例如，有 0型文法 G=(VN,VT, P, S) 其中： VN={A,B,S} , VT={0,1} 其描述的 0 型語言為 L0(G[S])={ } P: S ? 0AB 1B ? 0 B ? SA | 01 A1 ? SB1 A0 ? S0B STOP 文法和語言的分類 ?1型文法（上下文有關(guān)文法） 1型文法也稱為上下文有關(guān)文法， 相應(yīng) 的語言又稱為 上下文有關(guān)語言 。 若文法 G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 αAβ ?αμβ , 其中： α, β?(VN∪ VT)* , A?VN , 則稱 G是 1型文法 。 1型文法描述的語言是 1型語言。 1型語言由線性界限自動機(jī)識別。 μ?(VN∪ VT)+ 文法和語言的分類 例如，有 1型文法 G=(VN,VT, P, S) 其中： VN={S,A,B} , VT={a,b,c} P: S? aSAB | abB BA ? BA39。 BA39。 ? AA39。 AA39。 ? AB bA ? bb bB ? bc cB ? cc 其描述的 1型語言為 L1(G[S])={anbn | n≥1} 文法和語言的分類 ?2型文法（上下文無關(guān)文法） 2型文法又稱上下文無關(guān)文法，其產(chǎn)生的 語言又稱為 上下文無關(guān)的語言 。 若文法 G=(VN,VT, P, S)中的每一條規(guī)則的 形式為 A ?β , 其中： A?VN , β?(VN∪ VT)* 則稱 G是 2型文法 。 2型文法描述的語言是 2型語言。 2型語言由下推自動機(jī)識別。 例如前面描述算術(shù)表達(dá)式的文法 G[E]: E?E+E | E*E | (E) | i 文法和語言的分類 其描述的語言為 L2(G[S])={x | x ? {a, b}+ 且 x中 a和 b的個數(shù)相同 } 例如，有 2型文法 G=(VN,VT, P, S) 其中： VN={S, A, B} , VT={a, b} P={ S? aB | bA A? a | aS | bAA B? b | bS | aBB } 文法和語言的分類 文法和語言的分類 ?3型文法（正規(guī)文法） 右線性文法和左線性文法都稱為 3型文法 。 若文法 G=(VN,VT, P, S)中的每一條規(guī)則的形式 為 A ?aB 或 A ?a , 其中： A , B?VN, a ?VT*, 則稱 G是 右線性文法 。 若文法 G=(VN,VT, P, S)中的每一條規(guī)則的形式 為 A ?Ba 或 A ?a , 其中： A , B?VN , a ?VT*, 則稱 G是 左線性文法 。 3型文法描述的語言是 3型語言。 3型語言由有窮自動機(jī)識別。 3型文法也稱 正規(guī)文法 。正規(guī)文法產(chǎn)生的語言 稱為 正規(guī)語言 。 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義標(biāo)識符 文法和語言的分類 用 I代表標(biāo)識符 。 l代表任意一個字母 。 d代表任意一個數(shù)字 。 則定義標(biāo)識符的文法為： 左線性文法 : P: I→ l | Il | Id 右線性文法 : P: I→ l | lT T→l | d | lT| dT 例如，用左線性正規(guī)文法和右線性正規(guī)文法定義無符號整數(shù) 文法和語言的分類 用 N代表無符號整數(shù) 。 d代表任意一個數(shù)字；則定義的無符號整數(shù)文法為： 左線性文法 : P: N→ Nd | d 右線性文法 : P: N→ dN | d 文法和語言的分類 由上述四類文法的定義可知 , 從 0型文法到 3型文法 , 是逐漸增加對規(guī)則的限制條件而得到的，因此 每一種正規(guī)文法都是上下文無關(guān)的文法， 每一種上下文無關(guān)的文法都是上下文有關(guān)的文法，而每一種上下文有關(guān)的文法都是 0型文法 , 而由它們所定義的語言類是依次縮小的， 有 L0 ? L1 ? L2 ? L3 。 有關(guān)文法的實(shí)用限制和變換 文法是用來描述程序設(shè)計語言的，在 實(shí)際應(yīng)用中需要對文法加一些限制條件。 1. 文法中不能含有形如 A →A 的規(guī)則。這種規(guī)則我們稱之為 有害規(guī)則 。 對文法的實(shí)用限制有以下兩點(diǎn)： 有關(guān)文法的實(shí)用限制和變換 2. 文法中不能有 多余規(guī)則 。所謂多余規(guī)則是指文法中出現(xiàn)以下兩種規(guī)則： (1) 某條規(guī)則 A ?α 的左部符號 A不在所屬文法的任何其他