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