編譯原理復(fù)習(xí)(文件)
【正文】 設(shè)字母表 ∑ =(0,1)， 設(shè)計下述語言的文法 。 解： S→aEbE|E E→bTaT|T T→ε 此解無法描述 G所產(chǎn)生的語言（看 (2)），原因是不遞歸的文法無法產(chǎn)生長度無限的串，另外此文法也不能正確產(chǎn)生簡單的串 aabb。而 A的短語在 α 右邊（即先歸約了右邊的短語），與規(guī)范歸約矛盾。 謝 謝！ The trees that are slow to grow bear the best fruit. 33 95年夜大試題 試證明： 若正規(guī)集中任何字符串的長度是有限的 , 則識別該正規(guī)集的 DFA中無環(huán) 。 當(dāng) k→∞ 時， |T|+k*|S|→∞ ，與任何串長度有限矛盾。 考察任何一個 D所識別的、經(jīng)過 ni的串 T=T1T2，其中 T1是從初態(tài)到 ni的路徑標(biāo)記， T2是從 ni到終態(tài)的路徑標(biāo)記。 請進(jìn)一步思考： 為什么假設(shè)文法是非二義的？ 31 關(guān)于考試 題目類型：簡答題 （ 20分 ） 、 填空題 （ 30分 ） 、 計算題 （ 50分 ） 考試范圍： 1－ 5章講過的內(nèi)容 側(cè)重考察：基本概念與基本方法的掌握 ? 不認(rèn)真審題（題目的要求理解錯誤：意思理解錯、難題想容易、容易題想難。 解： （解題思路：用反證的方法，假設(shè)在規(guī)范歸約中句柄右邊有非終結(jié)符，則推出矛盾） 假設(shè)在規(guī)范歸約中有句型 “ ...α ...A...”，其中 α 是句柄，A非終結(jié)符。 (3) 0和 1個數(shù)不相等的字符串； 解： (2) S→ 0S1S|1S0S|ε (2) (01|10|00(01|10)*11|11(01|10)*00)* 考慮 “ 111110001000”， 采用 S→ 0S1S|1S0S|ε 可得分析樹如下： S1 S 0 S1 S 0 S ε1 S 0 S ε1 S 0 S ε1 S 0 S 0 S 1 Sε ε ε ε再考慮：(01|10|00(01|10)*11|11(01|10)*00)* 用 11(01|10)*00匹配得 11(11100010)00 剩余的 11100010沒有可用的正規(guī)式。 年 .月 .日 ， 如 日 月 年 ， 如 12 08 1992 月 /日 /年 ， 如 08/12/1992 解： digit=[09] year =(digit)(digit)(digit)(digit) month=0[19]|1[02] day =0[19]|[12][09]|3[01] date1= date2=day month year date3=month/day/year date =date1|date2|date3 ? 正規(guī)式描述的是語法，至于語義是否正確，此階段可以不考慮。 ” 改為“ ...是從狀態(tài) si經(jīng) ch(或 ε )到達(dá)的下一狀態(tài) sj。 ? 從泛泛的內(nèi)容中歸納出核心和需要牢固掌握的重點不是老師的責(zé)任。 17 3 聲明語句的翻譯 ? 定義與聲明：類型定義與變量聲明，過程定義與過程聲明 ? 變量聲明：符號表信息的填寫 ? 過程聲明： a. 左值與右值 b. 參數(shù)傳遞：參數(shù)傳遞的不同形式 c. 名字的作用域：靜態(tài)作用域與最近嵌套原則 d. 聲明中作用域信息的保存 18 4 可執(zhí)行語句的翻譯 ? 簡單算術(shù)表達(dá)式和賦值句的翻譯：語法制導(dǎo)翻譯的設(shè)計，類型轉(zhuǎn)換； ? 數(shù)組元素的引用： 數(shù)組元素地址計算的遞推公式 ，地址的可變部分與不變部分，可變部分計算的語法制導(dǎo)翻譯； ? 布爾表達(dá)式短路計算的翻譯：為什么需要短路計算， 短路計算的控制流 ，真出口與假出口，真值鏈與假值鏈； ? 控制語句的翻譯：控制語句的分類，無條件轉(zhuǎn)移與條件轉(zhuǎn)移，拉鏈 /回填技術(shù)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1