[理學(xué)]編譯原理復(fù)習(xí)-文庫吧資料
2025-02-24 21:57本頁面
【正文】 (00|11)|(01|10)(00|11)*(10|01))* 3. 符合要求的所有串： A1A、 A0A1A0A（ 為什么沒有后三個(gè) ？ ） 結(jié)果： A1A | A0A1A0A 思考： 識別它的 DFA又應(yīng)該如何構(gòu)造 ？ （ 4） C的形如 /*…*/ 的注釋。給出它的識別活前綴的 DFA。 } | id { =。 } | F { =。 } T→T 1+F { =newtemp。 emit(*,。 2. r=(a|b)*bb(a|b)*。 (c)（ 6分 ） 用子集法構(gòu)造識別 r的最小 DFA。 (a)(4分 ) 用自然語言簡要敘述該自動機(jī)所識別的語言 的特點(diǎn) ， 列舉兩個(gè)它可識別的串 。 1 語法分析 、 語義分析 、 代碼優(yōu)化 、 目標(biāo)代碼生成 、 符號表管理 和 出錯(cuò)處理 2 r和 s表示的正規(guī)集 3 a*(b|ba)* 4 FIRST(S)= {e， d， ε ， a， b} ， FIRST(D)= {a， b} ，F(xiàn)IRST(T)= {ε ， a， b} ， FIRST(R)= {d， ε} 。 3（ 2分 ） 不含子串 baa的所有 a、 b符號串的正規(guī)式是 。 二、填空題（ 30分） 1（ 6分 ） 編譯程序的基本組成有：詞法分析 、 、 、中間代碼生成 、 、 、 和 。 1 （ 1） 改寫文法 （ 2） 規(guī)定文法符號的優(yōu)先級和結(jié)合性 2 ab+c*d+（ 或 ab+c*d+） 3 證明： 考慮 L((ab)*a)中的任意一個(gè)串 ababab...aba， 由串連接的結(jié)合性可得： a(ba)(ba)(b...a)(ba)，它恰好是 L(a(ba)*)，即 L((ab)*a)= L(a(ba)*)。 2（ 2分 ） 寫出 ((a+b)*c)+d 的后綴式 。 21 關(guān)于考試 ? 題目類型： 簡答題 (25分 )、 填空題 (25分 )、 計(jì)算題 (50分 ) ? 考試范圍： 1－ 4章講過的內(nèi)容 ? 側(cè)重考察： 基本概念與基本方法的掌握 易犯的錯(cuò)誤 1. 不認(rèn)真審題（對題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。“ 基本概念要嚴(yán)謹(jǐn)（清楚），基本方法要靈活 ” 。太繁瑣步驟或太難等需要耗費(fèi)大量時(shí)間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會有一些綜合性的題目?；靖拍钫莆樟耍喈?dāng)一部分試題的解就有了。 主要內(nèi)容 1 語法制導(dǎo)翻譯與中間代碼 2 符號表的組織 3 聲明語句的翻譯 4 可執(zhí)行語句的翻譯 17 1 語法制導(dǎo)翻譯與中間代碼 1. 語法與語義：語法和語義描述語言的不同方面、二者之間沒有嚴(yán)格界線、語義形式化描述的困難性； 2. 屬性：用屬性表示語義特征（語義值），屬性的計(jì)算和屬性之間的依賴關(guān)系； 3. 語法制導(dǎo)翻譯：為產(chǎn)生式配上 “ 語義規(guī)則 ” 并在適當(dāng)?shù)臅r(shí)刻執(zhí)行；語義規(guī)則的兩種形式； 4. 分析方法與翻譯方案：以語法分析為基礎(chǔ)，分析樹的作用； 5. 中間代碼：為什么生成中間代碼，中間代碼的特征，各種形式的中間代碼及它們之間的關(guān)系，最常用中間代碼形式。 A → β1. β2B → β1. α β1習(xí)題與試題 （ 略過語法制導(dǎo)翻譯 ） 16 第四章 語法制導(dǎo)翻譯生成中間代碼 本章討論程序設(shè)計(jì)語言的靜態(tài)語義分析 ， 并且在語法分析的基礎(chǔ)上生成中間代碼 ， 采用的基本方法是語法制導(dǎo)翻譯 。 13 3 自上而下分析 1. 分析方法： 推導(dǎo)，從上到下構(gòu)造分析樹，是一種預(yù)測的、試探的方法； 2. 對文法的要求： 沒有公共左因子和左遞歸； 3. 遞歸下降子程序方法： 匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用） 4. 預(yù)測分析表方法 : ? 工作方式與過程： PDA（ DPDA） 、格局與改變格局的動作； ? 預(yù)測分析表的構(gòu)造： FIRST集合與 FOLLOW集合， FIRST與 FOLLOW的計(jì)算； ? LL(1)文法及其判別： 預(yù)測分析表中沒有多重定義條目（推論 ）。 2. 推導(dǎo)的基本概念： 句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）； 3. 分析樹與語法樹： 分析樹和語法樹都反映了語言結(jié)構(gòu)；分析樹還記錄了分析的過程（含有非終結(jié)符）； 4. 文法的二義性： 二義性的本質(zhì)是在文法中缺少對文法符號優(yōu)先級和結(jié)合性的限制，從而使得一個(gè)句子可以推導(dǎo)出多于一棵分析樹。 語法分析的分析對象是組成語言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對語法的分析就有了從根到葉子和從葉子到根兩種分析方法。 10 第三章 語法分析 語法分析是編譯器中的重要階段之一，可以認(rèn)為是語法制導(dǎo)翻譯模式編譯器的核心。 7 1 記號、模式與單詞 ? 模式 （ pattern） ：規(guī)定單詞識別的規(guī)則 ? 記號 （ token） ：按照某模式識別出的一類單詞 （ 記號種類 ） ? 單詞 （ lexeme） ：被識別出的字符串本身 ? 詞法分析器的輸出：記號 =記號種類 +記號屬性 2 記號的說明－模式的形式化描述 1. 正規(guī)式與正規(guī)集： ? 正規(guī)式與正規(guī)集的定義 (基本正規(guī)式、三個(gè)運(yùn)算 ) ? 正規(guī)式的等價(jià) (描述相同的集合 ) ? 利用正規(guī)式的等價(jià)對正規(guī)式進(jìn)行化簡 (正規(guī)式的代數(shù)性質(zhì) ) 2. 用正規(guī)式形式化描述模式： ? 如何用正規(guī)式描述程序設(shè)計(jì)語言中常見的記號，如標(biāo)識符、數(shù)字、運(yùn)算符和分隔符等 ? 正規(guī)式的簡化形式以及輔助定義與規(guī)則 8 3 記號的識別－有限自動機(jī)（ FA） ? NFA與 DFA的定義： FA = (S, Σ, move, s0, F) ； ? NFA與 DFA的表示：定義表示、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣； ? NFA與 DFA的關(guān)鍵區(qū)別： NFA的不確定性（當(dāng)前狀態(tài)下，對同一字符可能有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移）； ? 用 NFA識別輸入序列的弱點(diǎn)：嘗試所有路徑才能確定一個(gè)輸入不被接收、回溯帶來的問題； ? 模擬 DFA的算法：用 DFA識別記號。 3 第一章 引言 1 語言的翻譯 不同的翻譯形式： 匯編 、 編譯 、 轉(zhuǎn)換 （ 預(yù)編譯 ） 、 逆向翻譯 翻譯方法： 編 譯
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1