第三章文法和語言-資料下載頁
2025-08-01 12:51本頁面
【正文】 F （ E） |i 句型 i*i+i ?短語： i i2 、 i3 、 i1*i2 、 i1*i2+i3 ?直接短語： i1 、 i2 、 i3 ?句柄： i1 E T F * i3 + E T T F F i1 i2 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 有關(guān)文法實用中的一些說明 一 .有關(guān)文法的實用限制 ?有害規(guī)則：形如 U U的產(chǎn)生式 ?多余規(guī)則：文法中那些連一個句子的推導都 用不到 的規(guī)則 ?某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)（ 不可到達的 ） ?不能夠從這些非終結(jié)符推出終結(jié)符號串（ 不可終止的 ） 盛威網(wǎng)：專業(yè)的計算機學習網(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)：專業(yè)的計算機學習網(wǎng)站 ?對文法 G=(VN,VT,S,P)來說，為了保證其任一非終結(jié)符 A在 句子推導中出現(xiàn)，必須滿足如下兩個條件： ① A必須在某句型中出現(xiàn)。即 S αAβ,其中 α,β屬于 V* ② 必須能夠從 A推出終結(jié)符號串 t。即 A t,其中 t∈ VT* * + 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 二 .上下文無關(guān)文法中的 ε規(guī)則 ?ε規(guī)則：形如 A ε的產(chǎn)生式，其中 A∈ VN ?某些著作和講義中限制這種規(guī)則的出現(xiàn)。因為 ε規(guī)則會使 有關(guān)文法的一些討論和證明變得復雜 ?兩種定義的唯一差別是 ε句子在不在語言中 ?如果語言 L有一個有窮的描述，則 L∪ {ε}也同樣有一個有 窮描述。并且可以證明，若 L是上下文有關(guān)語言、上下文 無關(guān)語言或正規(guī)語言，則 L∪ {ε}和 L{ε}分別是上下文有 關(guān)語言、上下文無關(guān)語言和正規(guī)語言 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?定理 若 L是由文法 G=(VN,VT,P,S)產(chǎn)生的語言， P中的 每一個產(chǎn)生式的形式均為 A α,其中 A∈ VN， α∈ V*， 則 L能 由 這樣 的 一種文法產(chǎn)生， 即每一個 產(chǎn)生式 或者為 A β形式，其中 A∈ VN， β ∈ V+,或者 S ε形式， 且 S不出現(xiàn)在任何產(chǎn)生式右邊 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 ?定理 如果 G是上下文有關(guān)文法，則存在另一個上下文 有關(guān)文法 G1， L(G)=L(G1)，且 G1的開始符號不出現(xiàn)在 G1 的任何產(chǎn)生式的右邊 ?又如果 G是一個上下文無關(guān)文法，也能找到這樣一個上下 文無關(guān)文法 G1 ?如果 G是是一個正規(guī)文法，則也能找到這樣一個正規(guī)文法 G1 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 167。 典型例題及解答 G=({E,O},{(,),+,*,v,d},P,E)是二義的 E EOE|(E)|v|d O +|* L1={anb2ncm|n,m=0} L2={anbmc2m|n,m=0} 通過分別給出上述語言的文法來證明這些語言都是上 下文無關(guān)的 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 【 本章小結(jié) 】 ① 本章出現(xiàn)的概念較多 ,應重點理解文法 ,推導 ,句型句子及語 言的定義等概念 .語法分析有關(guān)內(nèi)容在后面章節(jié)會詳細討論 . ② 文法作為程序語言的語法的描述工具 ,它用規(guī)則只能陳述 的是 :語言的所有句子以什麼樣的符號串能出現(xiàn) .請記住文 法和語言的形式定義中的 “形式”的含義 只涉及語言的語 法不涉及語言的語義 . ③ 本章內(nèi)容是形式語言理論的一部分 .形式語言理論是對符 號串集合的表示法、結(jié)構(gòu)及其特性的研究。是程序設(shè)計語 言語法分析研究的基礎(chǔ)。 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 考察本章知識點最典型的題目是： ⑴ 已知文法 G[A]，寫出它定義的語言描述 G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案 :G[A]定義的語言由 0、 1符號串組成，串中 0和 1的個數(shù)相同。 ⑵ 給出語言描述，構(gòu)造文法。 構(gòu)造一文法 ,其定義的語言是由算符 +, *, (,)和運算對象 a構(gòu)成的算術(shù)表達式的集合 . 答案 1: G[E] E→E+T|T T→T* F|F F→(E)|a 答案 2: G[E] E→E+E|E* E|(E)|a 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 編譯原理第 3章習題 第 1題： 寫一文法，使其語言是偶正整數(shù)的集合。 要求： (1) 允許 0打頭； (2)不允許 0打頭。 第 2題： 證明下述文法 G[〈 表達式 〉 ]是二義的。 〈 表達式 〉 ∷ =a|(〈 表達式 〉 )|〈 表達式 〉 〈 運算符 〉〈 表達式 〉 〈 運算符 〉 ∷ =+||*|/ 第 3題： 令文法 G[E]為： E→T|E+T|E T T→F|T*F|T/F F→(E)|i 證明 E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 4題： 給出生成下述語言的上下文無關(guān)文法： （ 1） { anbnambm| n， m=0} （ 2） { 1n0m 1m0n| n， m=0} 第 5題： 給出生成下述語言的三型文法： (1) { anbm|n,m=1 } (2){anbmck|n,m,k=0 } 第 6題： 給出下述文法所對應的正規(guī)式： S→0A|1B A→1S|1 B→0S|0 盛威網(wǎng)：專業(yè)的計算機學習網(wǎng)站 第 3章 作業(yè)題 P47： 1. 6.(5)(6) 8. 9. 13. 14.
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1