【正文】 除： ? 改寫二義文法為非二義文法； ? 對文法符號施加優(yōu)先級與結(jié)合性的限制，使得分析的每一步有唯一選擇。 主要內(nèi)容： 1 記號、模式與單詞 2 記號的說明－模式的形式化描述（正規(guī)式與正規(guī)集） 3 記號的識別－有限自動機 4 從正規(guī)式到詞法分析器 詞法分析器的作用： ? 濾掉源程序中的無用成分； ? 處理與具體操作系統(tǒng)或機器有關(guān)的輸入； ? 識別記號并交給語法分析器； ? 調(diào)用符號表管理器和出錯處理器進(jìn)行相關(guān)處理。 7 1 記號、模式與單詞 ? 模式 （ pattern） ：規(guī)定單詞識別的規(guī)則 ? 記號 （ token） ：按照某模式識別出的一類單詞 （ 記號種類 ） ? 單詞 （ lexeme） ：被識別出的字符串本身 ? 詞法分析器的輸出：記號 =記號種類 +記號屬性 2 記號的說明－模式的形式化描述 1. 正規(guī)式與正規(guī)集： ? 正規(guī)式與正規(guī)集的定義 (基本正規(guī)式、三個運算 ) ? 正規(guī)式的等價 (描述相同的集合 ) ? 利用正規(guī)式的等價對正規(guī)式進(jìn)行化簡 (正規(guī)式的代數(shù)性質(zhì) ) 2. 用正規(guī)式形式化描述模式： ? 如何用正規(guī)式描述程序設(shè)計語言中常見的記號，如標(biāo)識符、數(shù)字、運算符和分隔符等 ? 正規(guī)式的簡化形式以及輔助定義與規(guī)則 8 3 記號的識別－有限自動機（ 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)下，對同一字符可能有多于一個的下一狀態(tài)轉(zhuǎn)移）； ? 用 NFA識別輸入序列的弱點：嘗試所有路徑才能確定一個輸入不被接收、回溯帶來的問題； ? 模擬 DFA的算法：用 DFA識別記號。 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的計算； ? LL(1)文法及其判別： 預(yù)測分析表中沒有多重定義條目（推論 ）。太繁瑣步驟或太難等需要耗費大量時間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會有一些綜合性的題目。 1 （ 1） 改寫文法 （ 2） 規(guī)定文法符號的優(yōu)先級和結(jié)合性 2 ab+c*d+（ 或 ab+c*d+） 3 證明： 考慮 L((ab)*a)中的任意一個串 ababab...aba， 由串連接的結(jié)合性可得： a(ba)(ba)(b...a)(ba)，它恰好是 L(a(ba)*)，即 L((ab)*a)= L(a(ba)*)。 (a)(4分 ) 用自然語言簡要敘述該自動機所識別的語言 的特點 ， 列舉兩個它可識別的串 。 } T→T 1+F { =newtemp。 其中 …代表不含 */的字符串 思路： 分析題意 ， 從最簡單的例子考慮 ， 然后找出統(tǒng)一規(guī)律 （ 1） 的解題步驟： 1. 最簡單的符合要求的串： 010（ 還有 100、 00 111等 ） 2. 所有 01均為偶數(shù)的串： A=((00|11)|(01|10)(00|11)*(10|01))* 3. 符合要求的所有串： A1A、 A0A1A0A（ 為什么沒有后三個 ？ ） 結(jié)果： A1A | A0A1A0A 思考： 識別它的 DFA又應(yīng)該如何構(gòu)造 ？ （ 4） C的形如 /*…*/ 的注釋。 → . E E → . E + T E → . T T → . T * F T → . F F → . ( E ) F → . F F → . i d E 39。 b:=3。 注意： 絕對不允許用正規(guī)式表示 ， 因為正規(guī)式是已知條件 習(xí)題 設(shè)字母表 Σ ={0,1},設(shè)計下述語言的文法 。 end if。 end if。 46 附件 1：教材與習(xí)題答案中的錯誤 教材 23頁：例 ：將 “ M[si,sj]‖改為 “ M[si,ch]‖ 將 “ ...是從狀態(tài) si到狀態(tài) sj的邊上的標(biāo)記 ch(或 ε )。 ” 24頁：倒 11行：將 “ M[si,sj]‖改為 “ M[si,ch]‖ 25頁：圖 “ 000‖應(yīng)改為 “ 012‖ 34頁：算法 ④ 3行：將 “ 從 si出發(fā) ” 改為 “ 從 si39。 （ 1） 試導(dǎo)出以列為主存儲時計算 c和 v的遞推公式； （ 2） *設(shè)計數(shù)組聲明的語法制導(dǎo)翻譯 （ 包括語法和語義 ） ， 以使得 在對數(shù)組聲明從左到右分析的同時 ， 正確填寫符號表和內(nèi)情向量的 所有信息 。 for 狀態(tài) i的每個可歸約項 A→ α . loop if S39。 （ 1） 每個 0后面至少跟隨一個 1的字符串 （ 2） 0和 1個數(shù)相等的字符串 （ 3） 0和 1個數(shù)不相等的字符串 （ 4） 不以 011作為子串的字符串 解： （ 1） (01|1)* （ 2） S→ 0S1S|1S0S|ε （ 3） S→A 0A|B1B A→ 0A1A|1A0A|0A|ε B→ 0B1B|1B0B|1B|ε （ 4） 1*(0|01)* 習(xí)題 構(gòu)造 SLR(1)分析表的算法 LR(0)項目集中可能有 沖突 。 print a end。 IJKaA習(xí)題 假定下述程序分別采用值調(diào)用 ， 引用調(diào)用 ， 復(fù)寫 恢復(fù)和換名調(diào)用 ， 請給出它們的打印結(jié)果 。 所以 ， 根本的方法是把正規(guī)集作為橋梁 ， 先分析清楚 DFA識別出的是一個什么集合 ， 然后再設(shè)計此集合的正規(guī)式 。 } | F { =。 (c)（ 6分 ） 用子集法構(gòu)造識別 r的最小 DFA。 二、填空題（ 30分） 1（ 6分 ） 編譯程序的基本組成有：詞法分析 、 、 、中間代碼生成 、 、 、 和 ?！?基本概念要嚴(yán)謹(jǐn)（