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