【正文】 或 α β ?α稱(chēng)為規(guī)則的 左部 ， β稱(chēng)為規(guī)則的 右部 ， (::=)讀作 “ 定義為 ”，這是一條關(guān)于 α的規(guī)則（產(chǎn)生式） 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義 ： 文法 G定義為四元組（ VN， VT， P， S） ?VN ： 非終結(jié)符（語(yǔ)法實(shí)體、變量）集 ?VT ： 終結(jié)符集 ?P： 規(guī)則 （ α β）集合， α∈ (VN∪ VT)*且至少包含 一個(gè)非終結(jié)符， β ∈ (VN∪ VT)* ?VN、 VT、 P是非空有窮集 ?S： 開(kāi)始符 （識(shí)別符），它是一個(gè)非終結(jié)符，至少要在一 條規(guī)則中作為左部出現(xiàn) ?VN∩VT= 216。但可以為無(wú)二義性尋找一組充分條件 ?二義文法改造為無(wú)二義文法 例 ： G[E]： E T|E+T G[E]: E i T F|T*F E E+E F （ E） |i E E*E 規(guī)定優(yōu)先順序和結(jié)合律 E (E) 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 有關(guān)文法實(shí)用中的一些說(shuō)明 一 .有關(guān)文法的實(shí)用限制 ?有害規(guī)則：形如 U U的產(chǎn)生式 ?多余規(guī)則：文法中那些連一個(gè)句子的推導(dǎo)都 用不到 的規(guī)則 ?某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)（ 不可到達(dá)的 ） ?不能夠從這些非終結(jié)符推出終結(jié)符號(hào)串（ 不可終止的 ） 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 文法 G[S]： （ 1） S Be （ 2） B Ce （ 3） B Af （ 4） A Ae （ 5） A e （ 6） C Cf （ 7） D f 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?對(duì)文法 G=(VN,VT,S,P)來(lái)說(shuō)，為了保證其任一非終結(jié)符 A在 句子推導(dǎo)中出現(xiàn)，必須滿(mǎn)足如下兩個(gè)條件： ① A必須在某句型中出現(xiàn)。 ⑵ 給出語(yǔ)言描述，構(gòu)造文法。 要求： (1) 允許 0打頭； (2)不允許 0打頭。即 A t,其中 t∈ VT* * + 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .上下文無(wú)關(guān)文法中的 ε規(guī)則 ?ε規(guī)則：形如 A ε的產(chǎn)生式，其中 A∈ VN ?某些著作和講義中限制這種規(guī)則的出現(xiàn)。顯然這種方式代價(jià) 極高，效率很低 圖 cad的語(yǔ)法樹(shù) 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?在自下而上的分析中，對(duì)于例 ，在歸約的時(shí)候， 也存在選擇哪一條規(guī)則進(jìn)行歸約的問(wèn)題，因此需要精確定 義“可歸約串”。 文法的類(lèi)型 ?喬姆斯基 (Chomsky)于 1956年建立形式語(yǔ)言的描述 ?他把文法分成： 0型、 1型、 2型、 3型 ?四個(gè)文法類(lèi)的定義是逐漸增加限制的 0型 1型 2型 3型 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β是這樣一種結(jié)構(gòu)： α∈ (VN∪ VT)*且 α至少包 含一個(gè) 非終結(jié)符， β∈ (VN∪ VT)*，則 G是一個(gè) 0型文法 （ 短語(yǔ)文法、無(wú)限制文法 ） 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?思考：這樣定義可以嗎？ 設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β是這樣一種結(jié)構(gòu)： α∈ (VN∪ VT)+， β∈ (VN∪ VT)*， 則 G是一個(gè) 0型文法 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?重要的理論結(jié)果： ?0型文法的能力相當(dāng)于圖靈機(jī)（ Turing） ?或者說(shuō)，任何 0型語(yǔ)言都是遞歸可枚舉的 ?反之，遞歸可枚舉集必定是一個(gè) 0型語(yǔ)言 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β均滿(mǎn)足： |β| ≥ |α|，僅僅 S ε除外， 則 文法 G是 1型文法 （ 上下文有關(guān)文法 ） ?例 、 、 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例： 文法 G[S]： S CD Ab bA C aCA Ba aB C bCB Bb bB AD aD C ε BD bD D ε Aa bD L(G)={w|w∈ {a,b}*} 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有些定義中，將上下文有關(guān)文法的產(chǎn)生式的形式描述為 α1Aα2 α1βα2，其中 α α2和 β都在 V*中， β≠ε， A在 VN中 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 α β均滿(mǎn)足： α是 一個(gè) 非終結(jié)符， β∈ V*，則文法 G是 2型文法 （ 上下文無(wú)關(guān)文法 ） 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?有時(shí)將 2型文法的產(chǎn)生式表示為 A β的形式，其中 A∈ VN，也就是用 β取代非終結(jié)符 A時(shí)，與 A所在的上下 文無(wú)關(guān)，因此取名為 上下文無(wú)關(guān) ?例 、 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ： 文法 G[S]： S aB|bA A a|aS|bAA B b|bS|aBB 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?設(shè) G＝（ VN， VT， P， S），如果它的 每個(gè) 產(chǎn)生式 A αB或 A α，其中 A和 B都是非終結(jié)符， α∈ VT*，則文法 G是 3型文法 （ 正規(guī)文法 ） ?例 ：文法 G[S]： S 0A|1B|0 A 0A|1B|0S B 1B|1|0 你會(huì)忘記我嗎？ 盛威網(wǎng)：專(zhuān)業(yè)的計(jì)算機(jī)