【正文】 例 設文法 G[S] ： ?E?E+T|T ?T?T*F|F ?F?(E)|i ?證明符號串 E+(E+T)*i是文法的句型。 ? （ 4）如果結點 n的直接子孫，從左到右的次序是結點 n1,n2,n3….n k，其標記分別為 A1， A2， A3， …A K。 ? （ 2）根的標記是 S。 句子 主語 系詞 表語 代詞 They are 名詞 student 連接詞 and 名詞 teacher 定語 前置詞 冠詞 名詞 of the Physics 名詞 Department 圖 23句子結構 ?在自然語言中，可以通過樹型表示直觀地分析句子的結構；在形式語言中，我們提到了句型、推導的概念，在證明某個符號串是否是某個文法的句型時，采用從文法開始符號推導的方法，這個推導過程可以用語法樹直觀的表示出來。如下面的句子： ?They are students and teachers of the Physics Department。 ?③該文法產(chǎn)生的語言是程序設計語言中的算術運算式，其中包括加、乘和括號運算。 ?【 證明 】 ?① 由于E?E+T?E+T*F?E+T*i?E+F*i?E+(E)*i ?E+(E+T)*i ?所以 E+(E+T)*i是文法的句型。 ?例 2型文法 G=(VN， VT， P， S) ?其中， VN={S} ?VT={0,1} ?P={S→0S1,S→01} ?該文法產(chǎn)生的語言是 L(G)={0n1n,其中 n≥1} ?例 文法 G[S]定義如下 ?S?if E then S| if E then S else S|while E do S|begin L end|A ?該文法產(chǎn)生的語言就是程序設計語言中的單分支、雙分支、循環(huán)語句和順序語句，其中每個非終結符的意義是： S代表語句，L代表語句串、 A代表賦值語句， E代表布爾表達式。 ? 實質(zhì)上，句子是句型的特殊情況，句子是由終結符組成，而句型是有終結符和非終結符組成。 ? 【 解 】 ? （ 1）用最右推導，每次用產(chǎn)生式的規(guī)則替換最右邊的非終結符，推導過程如下： ? 無正負號整數(shù) ?數(shù)字序列 ?數(shù)字序列 數(shù)字 ?數(shù)字序列 4 ? ?數(shù)字序列 數(shù)字 4?數(shù)字序列 34?數(shù)字序列 數(shù)字 34 ? ?數(shù)字序列 634?2634 ? （ 2）用最左推導，每次直接推導都替換最左邊的非終結符，推導過程如下： ? 無正負號整數(shù) ?數(shù)字序列 ?數(shù)字序列 數(shù)字?數(shù)字序列 數(shù)字 數(shù)字 ? ?數(shù)字序列 數(shù)字 數(shù)字 數(shù)字 ?數(shù)字 數(shù)字數(shù)字 數(shù)字 ? ?2數(shù)字 數(shù)字 數(shù)字 ? ?26數(shù)字 數(shù)字 ? ?263數(shù)字 ? ?2634 、句子和語言 ? 定義 句型：設 G[S]是一個文法，如果符號串 x是從開始符號 S推導得到的，即有 S=+x， x?V+，則稱符號串 x是該文法 G的一個句型。 ?定義 ，最右推導常稱為規(guī)范推導，由規(guī)范推導所得的句型稱為規(guī)范句型。 ?定義 ???，其中 ?、 ?是句型，都是對 ?中的最左非終結符進行替換，則稱這種推導為最左推導 。 ?定義 ???，其中 ?、 ?是句型，都是對 ?中的最右非終結符進行替換，則稱這種推導為最右推導 。每一步推導都是直接推導。 ? 給出數(shù)據(jù) 2634的推導。 ? 例 根據(jù)文法，考慮以 C語言中的無正負號整數(shù)作為識別符號的文法。 ?定義 推導長度大于 0的推導 ： 如果 對于符號串 v 與 w存在一個直接推導序列 ?u0 ? u1?u2?u3?…u n (n0) ?其中 u0=v與 un =w,則稱符號串 v推導出 w或稱 w歸約到 v，記作 v ? *w，稱這個直接推導序列是長度為 n的推導，且稱符號串 w是相對于符號串 v的一個字。推導分為三大類：直接推導 、 ?，長度為n(n≥1) n（ n≥0 ? 定義 如 α→β是文法 G=(VN,VT,P,S)的規(guī)則（或說是 P中的一產(chǎn)生式）， γ,δ∈ (VN∪ VT)*，則稱符號串 γβδ為符號串 γαδ應用產(chǎn)生式 α→β所得到的直接推導。右線性文法可由一種有窮狀態(tài)自動機識別。如果從文法出發(fā)找不到這個推導序列，則該串就是非法的。同時我們還要有能力判定一個串是否合法。從一個文法能推導出多個終結符的句子?？s寫為 FA?？s寫為 PDA。 3． 2型語言與下推自動機 ?2型語言或上下文無關語言對應的自動機稱為下推自動機。 ?上下文有關文法所對應的自動機稱為線性界限自動機。圖靈機的基本模型如圖 21所示。 1． 0型語言與圖靈機 ?圖靈機是識別 0型文法的識別裝置。自動機能夠識別的句子的集合稱為語言。將算法對程序的合法與否的檢查轉化為數(shù)學模型對程序中的句子的識別過程。合法就回答“正確”，不合法就回答“不正確”，并且將錯誤報出。因此對程序的編譯事實上就是對句子進行檢查。因此，四類文法產(chǎn)生的語言就會有如下關系： ? 3型語言 ?2型語言 ?1型語言 ?0型語言 ?語言是句子的集合，而句子又是由字母表上的符號串組成的。 ? 根據(jù)以上我們對文法的定義我們不難發(fā)現(xiàn) 3型文法類是 2型文法類的特殊情況， 2型文法類是 1型文法類的特殊情況。 ? 例題 G=（ VN， VT， P， S）其中 VN={S， A，B， G， H}， VT={d， ? 3型文法（右線性文法或正規(guī)文法） ? 對 2型文法的產(chǎn)生式做進一步的限制，限制產(chǎn)生式右部是單一終結符或單一終結符跟著單一非終結符，即： A→a ? A→aB ? 則稱該文法為 3型文法 ，又稱為 右線性文法或正規(guī)文法 ，其中 A、 B∈ VN， a∈ VT. ? 例題 ? 3型文法 G=（ VN， VT， P， S） ? 其中， VN={S， A， B} ? VT={0， 1} ? P={S→0∣ 1∣ 1A∣ 0B， A→ 1A∣ 0B， B→0∣ 1∣ 0B} ? 該文法產(chǎn)生的是二進制整數(shù)。上下文無關文法有足夠的能力描述現(xiàn)今的程序設計語言。有時將 2型文法的產(chǎn)生式表示為形如：A→β，其中 A∈ VN 。 ? 所謂上下文有關文法即： α=γ1Aγ2， β=γ1δγ2，符號串 γ1 和 γ2可以認為是上下文， A只有出現(xiàn)在上下文之間中，才可以被符號串 δ替代，成為 α=γ1Aγ2?β=γ1δγ2因此， 1型文法又稱為上下文有關文法。 0型文法又稱短語文法，它的能力相當于一個圖靈機。 ? 上面的產(chǎn)生式規(guī)則可以改寫為： ? P為產(chǎn)生式的規(guī)則： ? {N→L|NL|ND ? L→a|b| c ? D→1|2|3 ? } ? 自從喬姆斯基（ Chomsky）于 1956年建立形式語言的描述以來，把文法分成四種類型，即 0型、 1型、 2型和 3型文法。命名規(guī)則為： ?標識符 →字母 ?標識符 →標識符 字母 ?標識符 →標識符 數(shù)字 ?字母 →a ?字母 →b ?字母 →c ?數(shù)字 →1 ?數(shù)字 →2 ?數(shù)字 →3 ? 我們一般用大寫字母代表左邊的非終結符，設 N 代表 標識符 ， D代表 數(shù)字， L代表 字母 ，則定義標識符的文法是： ? G=(VN， VT， P， N) ? 其中， VN={N， L， D} ? VT={a,b,c,1,2,3} ? P為產(chǎn)生式的規(guī)則： ? {N→L， N→NL ， N→ND ， L→a ， L→b ， L→c ， D→1 ， D→2， D→3} ? S 是開始符號 ,為 N. ? 關于產(chǎn)生式的規(guī)則說明一點，即若 A→α， A→β， A→γ可寫成 A→α|β|γ 。 ? 2．文法 ? 定義 文法 G是一個四元組， G=（ VN， VT， P， S），其中， VN、 VT分別是非空有限的非終結符號集和終結符號集， VN∩VT=?， P是產(chǎn)生式的集合，S∈ V