《西安電子科技大學(xué)編譯原理復(fù)習(xí).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《西安電子科技大學(xué)編譯原理復(fù)習(xí).ppt（54頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、編譯原理復(fù)習(xí),西安電子科技大學(xué) 軟件工程研究所 劉 堅(jiān),2,課程內(nèi)容,要求（希望） 牢固掌握基本概念 靈活使用基本方法 歸納總結(jié)所學(xué)內(nèi)容,一、引言 二、詞法分析 三、語(yǔ)法分析 四、語(yǔ)義分析語(yǔ)法制導(dǎo)翻譯生成中間代碼,學(xué)習(xí)不能走捷徑，付出多少勞動(dòng)就有多少收獲 掌握正確的學(xué)習(xí)方法，提高自學(xué)能力,3,第一章 引言, 語(yǔ)言的翻譯,不同的翻譯形式：匯編、編譯、轉(zhuǎn)換（預(yù)編譯）、逆向翻譯 翻譯方法：,,4, 編譯器的基本組成,,5, 編譯器的分析綜合模式,, 編譯器的掃描遍數(shù)與編譯器的編寫(xiě),6,第二章 詞法分析,構(gòu)詞規(guī)則與詞法分析： 首先規(guī)定單詞形成的規(guī)則，稱(chēng)為構(gòu)詞規(guī)則；然后根據(jù)構(gòu)詞規(guī)則識(shí)別輸入序列，稱(chēng)為詞
2、法分析。,主要內(nèi)容： 記號(hào)、模式與單詞 記號(hào)的說(shuō)明模式的形式化描述（正規(guī)式與正規(guī)集） 記號(hào)的識(shí)別有限自動(dòng)機(jī) 從正規(guī)式到詞法分析器,詞法分析器的作用： 濾掉源程序中的無(wú)用成分； 處理與具體操作系統(tǒng)或機(jī)器有關(guān)的輸入； 識(shí)別記號(hào)并交給語(yǔ)法分析器； 調(diào)用符號(hào)表管理器和出錯(cuò)處理器進(jìn)行相關(guān)處理。,7, 記號(hào)、模式與單詞,模式（pattern）：規(guī)定單詞識(shí)別的規(guī)則 記號(hào)（token）：按照某模式識(shí)別出的一類(lèi)單詞（記號(hào)種類(lèi)） 單詞（lexeme）：被識(shí)別出的字符串本身 詞法分析器的輸出：記號(hào)=記號(hào)種類(lèi)+記號(hào)屬性, 記號(hào)的說(shuō)明模式的形式化描述,正規(guī)式與正規(guī)集 正規(guī)式與正規(guī)集的定義(基本正規(guī)式、三個(gè)運(yùn)算) 正規(guī)式
3、的等價(jià)(描述相同的集合) 利用正規(guī)式的等價(jià)對(duì)正規(guī)式進(jìn)行化簡(jiǎn)(正規(guī)式的代數(shù)性質(zhì)) 用正規(guī)式形式化描述模式 如何用正規(guī)式描述程序設(shè)計(jì)語(yǔ)言中常見(jiàn)的記號(hào)，如標(biāo)識(shí)符、數(shù)字、運(yùn)算符和分隔符等 正規(guī)式的簡(jiǎn)化形式以及輔助定義與規(guī)則,8, 記號(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的不確定性： 有狀態(tài)轉(zhuǎn)移； 當(dāng)前狀態(tài)下，對(duì)同一字符有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移； 用NFA識(shí)別輸入序列的弱點(diǎn)：嘗試所有路徑才能確定一個(gè)輸入不被接收、回溯帶來(lái)的問(wèn)題； 模擬DFA的算法（算法
4、2.1 ）：用DFA識(shí)別記號(hào)。,, 從正規(guī)式到詞法分析器,構(gòu)造NFA的Thompson算法(算法2.2)：與正規(guī)式的對(duì)應(yīng)關(guān)系； 模擬NFA的“并行”算法（算法2.3）； 從NFA構(gòu)造DFA子集法（算法2.5）： smove(S, a)與-閉包(T)的計(jì)算； DFA的最小化可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個(gè)狀態(tài)（算法2.6）； 靈活運(yùn)用各種方法構(gòu)造DFA(正規(guī)式化簡(jiǎn)、狀態(tài)轉(zhuǎn)換圖等)，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別（考慮(a|b)*abb的NFA）。,10,第三章 語(yǔ)法分析,語(yǔ)法分析是編譯器中的重要階段之一，可以認(rèn)為是語(yǔ)法制導(dǎo)翻譯模式編譯器的核心。語(yǔ)法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語(yǔ)
5、言的各種結(jié)構(gòu)，即語(yǔ)法規(guī)則；根據(jù)語(yǔ)法規(guī)則識(shí)別輸入序列（記號(hào)流）中的語(yǔ)言結(jié)構(gòu)，即語(yǔ)法分析。,語(yǔ)法分析的分析對(duì)象是組成語(yǔ)言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹(shù)，從而使得對(duì)語(yǔ)法的分析就有了從根到葉子和從葉子到根兩種分析方法。,主要內(nèi)容 程序設(shè)計(jì)語(yǔ)言與文法 有關(guān)推導(dǎo)的基本概念 自上而下分析 自下而上分析,11, 程序設(shè)計(jì)語(yǔ)言與文法,正規(guī)式與正規(guī)文法：正規(guī)式與正規(guī)文法用于描述線(xiàn)性結(jié)構(gòu)，如構(gòu)成句子的記號(hào)(終結(jié)符)；識(shí)別正規(guī)語(yǔ)言的自動(dòng)機(jī)是有限自動(dòng)機(jī)，它們的特征是沒(méi)有記憶能力； 上下文無(wú)關(guān)文法(CFG=(N, T, S, P))：CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識(shí)別CFL的自動(dòng)機(jī)是
6、下推自動(dòng)機(jī)，它是在有限自動(dòng)機(jī)的基礎(chǔ)上增加了一個(gè)下推棧，從而有了簡(jiǎn)單的記憶能力；,文法的分類(lèi)：0型、1型、2型和3型文法 詞法分析器與語(yǔ)法分析器：FA與PDA,12, 有關(guān)推導(dǎo)的基本概念,CFG產(chǎn)生語(yǔ)言的基本方法推導(dǎo)：從文法的開(kāi)始符號(hào)開(kāi)始，反復(fù)地用產(chǎn)生式的右部替換句型中的非終結(jié)符。 推導(dǎo)的基本概念：句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）；（定義3.2、3.3、3.4） 分析樹(shù)與語(yǔ)法樹(shù)：分析樹(shù)和語(yǔ)法樹(shù)都反映了語(yǔ)言結(jié)構(gòu)；分析樹(shù)還記錄了分析的過(guò)程(含有非終結(jié)符)；(定義3.5、3.6) 文法的二義性：二義性的本質(zhì)是在文法中缺少對(duì)文法符號(hào)優(yōu)先級(jí)和結(jié)合性的限制，從而使得一個(gè)句子可以推導(dǎo)出多于
7、一棵分析樹(shù)。(定義3.7) 二義性的消除： 改寫(xiě)二義文法為非二義文法；（兩個(gè)關(guān)鍵步驟） 對(duì)文法符號(hào)施加優(yōu)先級(jí)與結(jié)合性的限制，使得分析的每一步有唯一選擇。,13, 自上而下分析,分析方法：推導(dǎo)，從上到下構(gòu)造分析樹(shù)，是一種預(yù)測(cè)的、試探的方法； 對(duì)文法的要求：沒(méi)有公共左因子和左遞歸 左遞歸與直接左遞歸（定義3.9） 消除直接左遞歸與左遞歸（算法3.1、3.2） 提取公共左因子（類(lèi)似于提取公因式） 遞歸下降子程序方法：匹配終結(jié)符，展開(kāi)非終結(jié)符（子程序調(diào)用）, 自上而下分析（續(xù)）,預(yù)測(cè)分析表方法: 工作方式與過(guò)程：PDA（DPDA） 格局：（棧內(nèi)容，當(dāng)前剩余輸入，改變格局的動(dòng)作） 改變格局的動(dòng)作：匹配終
8、結(jié)符、展開(kāi)非終結(jié)符、接受、報(bào)錯(cuò) 驅(qū)動(dòng)器（算法3.4） 預(yù)測(cè)分析表和分析表的構(gòu)造： 分析表的構(gòu)成與意思：MA, a FIRST集合與FOLLOW集合（定義3.10、3.11） FIRST與FOLLOW的計(jì)算（算法3.5、3.6） 分析表的構(gòu)造（算法3.7） LL(1)文法及其判別：預(yù)測(cè)分析表中沒(méi)有多重定義條目（定義3.12、推論3.2）。,15, 自下而上分析,分析方法：歸約(推導(dǎo)的逆過(guò)程)，從葉子到根構(gòu)造分析樹(shù)； 基本概念： 短語(yǔ)、直接短語(yǔ)、句柄（定義3.13） 最左歸約（定義3.14）、歸約、規(guī)范歸約 采用的方法: 剪句柄 實(shí)現(xiàn)方法：移進(jìn)-歸約（格局中的兩個(gè)關(guān)鍵動(dòng)作） 關(guān)鍵問(wèn)題：是如何確定棧
9、頂已經(jīng)形成句柄，當(dāng)句柄形成時(shí)，如何判定采用哪個(gè)產(chǎn)生式進(jìn)行規(guī)約； 移進(jìn)-歸約分析器的工作模式（與預(yù)測(cè)分析表方法對(duì)著看） 移進(jìn)（匹配終結(jié)符） 歸約（展開(kāi)非終結(jié)符） 驅(qū)動(dòng)器（算法3.8）, 自下而上分析（續(xù)1）,移進(jìn)-歸約分析表：動(dòng)作表（action）和轉(zhuǎn)移表（goto） LR(k)文法（定義3.15） 核心：識(shí)別活前綴的DFA：活前綴與LR(0)項(xiàng)目(NFA狀態(tài))（定義3.16、3.17 ）,一個(gè)產(chǎn)生式是一個(gè)識(shí)別活前綴的NFA 一個(gè)LR(0)項(xiàng)目是NFA的一個(gè)狀態(tài),拓廣文法與子集法構(gòu)造DFA closure(I)、goto(I，X)(定義3.18、3.19 ) 核心項(xiàng)目與非核心項(xiàng)目（定義3.20）
10、 構(gòu)造算法（算法3.9）核心是：closure(goto(I，x)),17, 自下而上分析（續(xù)2）,DFA如何分析輸入序列 有效項(xiàng)目（定義3.21）、可移進(jìn)項(xiàng)目、可規(guī)約項(xiàng)目 移進(jìn)/歸約沖突、歸約/歸約沖突； 解決沖突的方法SLR(1)：簡(jiǎn)單向前看一個(gè)終結(jié)符（計(jì)算歸約項(xiàng)非終結(jié)符的FOLLOW，與可移進(jìn)終結(jié)符比較）；,移進(jìn)-歸約分析表的構(gòu)造：（算法3.10）； LR文法與LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。,18,第四章 語(yǔ)法制導(dǎo)翻譯生成中間代碼,討論程序設(shè)計(jì)語(yǔ)言的靜態(tài)語(yǔ)義分析，并且在語(yǔ)法分析的基礎(chǔ)上生成中間代碼，采用的基本方法是語(yǔ)法制導(dǎo)翻譯。 與前兩章詞法分析和語(yǔ)法
11、分析不同的是，詞法分析和語(yǔ)法分析的討論側(cè)重于理論，而本章則側(cè)重于結(jié)合程序設(shè)計(jì)語(yǔ)言的實(shí)際例子討論語(yǔ)言結(jié)構(gòu)的具體翻譯方法和一些實(shí)用的技術(shù)。,主要內(nèi)容 語(yǔ)法制導(dǎo)翻譯：概念與基本方法 中間代碼 符號(hào)表的組織 聲明語(yǔ)句的翻譯 可執(zhí)行語(yǔ)句的翻譯, 語(yǔ)法制導(dǎo)翻譯的基本概念,語(yǔ)法與語(yǔ)義 語(yǔ)法：語(yǔ)言的結(jié)構(gòu)；語(yǔ)義：附在結(jié)構(gòu)上的實(shí)際意思 屬性與屬性的計(jì)算 屬性：附在文法符號(hào)上的意思，如：val、place等 語(yǔ)義規(guī)則：實(shí)現(xiàn)屬性的計(jì)算 語(yǔ)義規(guī)則的兩種表現(xiàn)形式 語(yǔ)法制導(dǎo)定義：抽象的屬性和計(jì)算表示的語(yǔ)義規(guī)則 翻譯方案：具體的屬性和計(jì)算表示的語(yǔ)義規(guī)則, 基本設(shè)計(jì)方法,與語(yǔ)法分析的關(guān)系：自下而上語(yǔ)法分析（LR分析的兩點(diǎn)擴(kuò)充）
12、，自上而下語(yǔ)法分析（遞歸下降子程序方法） 語(yǔ)義規(guī)則的設(shè)計(jì)：設(shè)計(jì)屬性、基本操作（函數(shù)或過(guò)程）、語(yǔ)義規(guī)則； 聲明性語(yǔ)句：需要保存什么信息，這些信息有哪些特征，設(shè)計(jì)什么樣的數(shù)據(jù)結(jié)構(gòu)存放這些信息，以便于對(duì)它們的處理； 可執(zhí)行語(yǔ)句：語(yǔ)句的結(jié)構(gòu)應(yīng)生成什么樣的中間代碼序列，根據(jù)中間代碼序列設(shè)計(jì)語(yǔ)法制導(dǎo)定義，根據(jù)序列的特點(diǎn)設(shè)計(jì)翻譯方案。, 中間代碼,為什么生成中間代碼：中間代碼是編譯器分析綜合模式前端與后端的分水嶺； 中間代碼的特征：形式接近目標(biāo)機(jī)器代碼，但又與具體機(jī)器無(wú)關(guān)，便于編譯器的開(kāi)發(fā)移植和代碼的優(yōu)化； 常用的中間代碼形式：后綴式、樹(shù)（圖）、三地址碼； 三地址碼的實(shí)現(xiàn)：三元式、四元式 中間代碼之間的關(guān)系
13、： 樹(shù)與后綴式的關(guān)系 樹(shù)與三元式和四元式的關(guān)系, 符號(hào)表的組織,符號(hào)表的作用：連接聲明與引用的橋梁 符號(hào)表的條目與信息的存儲(chǔ)：直接存儲(chǔ)與間接存儲(chǔ) 作用域信息的保存 靜態(tài)作用域+最近嵌套原則 線(xiàn)性表：棧結(jié)構(gòu)，表上的操作 散列表：每個(gè)子表是棧結(jié)構(gòu)，提高表上操作的效率, 聲明語(yǔ)句的翻譯,定義與聲明：類(lèi)型定義與變量聲明，過(guò)程定義與過(guò)程聲明 變量聲明：符號(hào)表信息的填寫(xiě)（簡(jiǎn)單變量和數(shù)組變量）； 過(guò)程聲明： 左值與右值； 參數(shù)傳遞：參數(shù)傳遞的不同形式，各種參數(shù)傳遞形式的處理方式； 名字的作用域：滿(mǎn)足靜態(tài)作用域與最近嵌套原則； 聲明中作用域信息的保存。, 可執(zhí)行語(yǔ)句的翻譯,簡(jiǎn)單算術(shù)表達(dá)式和賦值句的翻譯：語(yǔ)法制
14、導(dǎo)翻譯的設(shè)計(jì)，類(lèi)型轉(zhuǎn)換； 數(shù)組元素的引用： 多維數(shù)組到一維存儲(chǔ)空間的映射； 數(shù)組元素地址計(jì)算的遞推公式； 數(shù)組元素地址計(jì)算的語(yǔ)法制導(dǎo)翻譯； 布爾表達(dá)式短路計(jì)算的翻譯： 為什么需要短路計(jì)算和短路計(jì)算的控制流； 真出口與假出口； 拉鏈/回填技術(shù)：真值鏈與假值鏈 控制語(yǔ)句的翻譯：控制語(yǔ)句的分類(lèi)，轉(zhuǎn)移與條件轉(zhuǎn)移。,結(jié) 束（2010年5月25日）,試題與習(xí)題,認(rèn)真復(fù)習(xí)，重點(diǎn)是掌握基本概念?；靖拍钫莆樟?，相當(dāng)一部分試題的解就有了。 習(xí)題與試題的目的區(qū)別：習(xí)題的目的是通過(guò)反復(fù)的練習(xí)理解、掌握所學(xué)知識(shí)，會(huì)有不少繁、難、大量步驟的題；試題的目的是考察對(duì)本課程綜合掌握的情況，特點(diǎn)是短時(shí)間內(nèi)覆蓋大量?jī)?nèi)容。太繁瑣步
15、驟或太難等需要耗費(fèi)大量時(shí)間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會(huì)有一些綜合性的題目。 自己要會(huì)辨別什么是主要的什么是次要的，抓什么丟什么?！盎靖拍钜獓?yán)謹(jǐn)（清楚），基本方法要靈活”。 總之一句話(huà)，學(xué)習(xí)方法的掌握是個(gè)人努力的結(jié)果，單純靠別人教是學(xué)不會(huì)的。,27,關(guān)于考試,題目類(lèi)型：填空題(30分)、簡(jiǎn)答題(20分)、計(jì)算題(50分) 考試范圍：14章講過(guò)的內(nèi)容 側(cè)重考察：基本概念與基本方法的掌握,易犯的錯(cuò)誤 不認(rèn)真審題（對(duì)題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。關(guān)鍵問(wèn)題是基本概念不清楚） 所答非所問(wèn)(例如：沒(méi)有要求LL分析卻將文法改為L(zhǎng)L的) 畫(huà)蛇添足(例如：僅問(wèn)有無(wú)沖
16、突卻將分析表先構(gòu)造出來(lái)) 偷工減料(例如：有若干問(wèn)，僅回答部分或問(wèn)題僅答一半),警示 千萬(wàn)不要作弊！命運(yùn)掌握在自己的手中！,實(shí)際試題舉例一、簡(jiǎn)答題,1（2分）有哪些方法可以去除文法的二義性。 2（2分）寫(xiě)出 -((a+b)*c)+d 的后綴式。 3（4分）試證明正規(guī)式(ab)*a與a(ba)*是等價(jià)的。,1 （1）改寫(xiě)文法 （2）規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性 2 ab+c*d+（或ab+c*-d+） 3 證明： 考慮L((ab)*a)中的任意一個(gè)串a(chǎn)babab...aba， 由串連接的結(jié)合性可得：a(ba)(ba)(b...a)(ba)，它恰好是L(a(ba)*)，即L((ab)*a)=
17、L(a(ba)*)。 也可以用歸納法證明（提示：以ab重復(fù)0次、1次作為歸納基礎(chǔ)，假設(shè)ab重復(fù)n次成立，證明ab重復(fù)n+1次也成立）。,二、填空題（30分）,1（6分）編譯程序的基本組成有：詞法分析、 、 、中間代碼生成、 、 、 和 。 2（1分）正規(guī)式r和s等價(jià)說(shuō)明 相同。 3（2分）不含子串baa的所有a、b符號(hào)串的正規(guī)式是 。 4（4分） 已知文法G定義如下： SeT|RT TDR| RdR| Da|bd 則FIRST(S)= ，F(xiàn)IRST(D)= ，F(xiàn)IRST(T)= ，F(xiàn)IRST(R)= 。,1 語(yǔ)法分析、語(yǔ)義分析、代碼優(yōu)化、目標(biāo)代碼生成、符號(hào)表管理和出錯(cuò)
18、處理 2 r和s表示的正規(guī)集 3 a*(b|ba)* 4 FIRST(S)= e，d，，a，b ，F(xiàn)IRST(D)= a，b ，F(xiàn)IRST(T)= ，a，b ，F(xiàn)IRST(R)= d， 。,三、計(jì)算題（1）,1（13分）已知一個(gè)NFA如圖。 (a)(4分) 用自然語(yǔ)言簡(jiǎn)要敘述該自動(dòng)機(jī)所識(shí)別的語(yǔ)言 的特點(diǎn)，列舉兩個(gè)它可識(shí)別的串。 (b)（3分）寫(xiě)出與該自動(dòng)機(jī)等價(jià)的正規(guī)式r。 (c)（6分）用子集法構(gòu)造識(shí)別r的最小DFA。,解：,含有至少兩個(gè)連續(xù)b的a、b串，例如bb、bbb等。 r=(a|b)*bb(a|b)*。 直接用狀態(tài)轉(zhuǎn)換矩陣構(gòu)造： 初態(tài)：0 子集法得：（2是終態(tài)）,令： 0=
19、A，0,1=B，0,1,2=C，0,2=D 得：,最小化DFA得：（C和D不可區(qū)分）,三、計(jì)算題（2）,2（15分）有文法G和G的語(yǔ)法制導(dǎo)翻譯如下： EE1*T E.place=newtemp; emit(*,E1.place,T.place,E.place; | T E.place=T.place; TT1+F T.place=newtemp; emit(+,T1.place,F.place,T.place; | F T.place=F.place; F(E) F.place=E.place; | id F.place=id.name; (a)（4分）求句型(T+F)*id 的短語(yǔ)、直接短語(yǔ)
20、以及句柄； (b)（4分）根據(jù)語(yǔ)法制導(dǎo)翻譯寫(xiě)出句子a*b+c*d的中間代碼； (c)（3分）若a=3，b=5，c=7，d=8，請(qǐng)給出中間代碼計(jì)算結(jié)果； (d)（4分）將文法G簡(jiǎn)化為：EE*T|T，TT+F|F，F(xiàn)id。給出它的識(shí)別活前綴的DFA。,解：,(a) 短語(yǔ)：(T+F)*id、(T+F)、T+F、id 直接短語(yǔ)：T+F、id 句柄：T+F (b) a*b+c*d的中間代碼：(1) (+, b, c, t1) (2) (*, a, t1, t2) (3) (*, t2, d, t3) (c) 計(jì)算結(jié)果：t3=288 (d) 識(shí)別活前綴的DFA：,,34,部分習(xí)題解答,習(xí)題2.4,寫(xiě)出下
21、述語(yǔ)言的正規(guī)式描述 （1）由偶數(shù)個(gè)0和奇數(shù)個(gè)1構(gòu)成的所有01串 （2）所有不含子串011的01串 （3）每個(gè)a后面至少緊隨兩個(gè)b的ab串 （4）C的形如/**/ 的注釋。其中代表不含*/的字符串,思路：分析題意，從最簡(jiǎn)單的例子考慮，然后找出統(tǒng)一規(guī)律 （1）的解題步驟： 1. 最簡(jiǎn)單的符合要求的串：1、010（還有100、001、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的形
22、如/**/ 的注釋。其中代表不含*/的字符串,思路：注釋中若遇到*：若后邊是/則結(jié)束注釋否則仍然是注釋 步驟： 1. 注釋串是空； 2. 考慮沒(méi)有*的注釋?zhuān)?3. 考慮含*的注釋 結(jié)果：(4) /* (*|*/)* */,（2）所有不含子串011的01串：1*(01|0)* （3）每個(gè)a后面至少緊隨兩個(gè)b的ab串：(b|abb)*,習(xí)題2.9,用自然語(yǔ)言給出下述正規(guī)式所描述的語(yǔ)言，并構(gòu)造他們的最小DFA：10*1(0|1)*011(0|1)*,說(shuō)明：所謂用自然語(yǔ)言描述就是解釋字符串的性質(zhì)，一般情況下是已經(jīng)有了形式化描述。 解：10*1：首尾是1中間有零或若干個(gè)0的01串。 (0|1)*011(
23、0|1)* ：至少含一個(gè)011的01串。 注意： *是0或若干次的重復(fù)；+是至少一次的重復(fù) 絕對(duì)不允許用正規(guī)式表示，因?yàn)檎?guī)式是已知條件 DFA（略）(0|1)*011(0|1)* 的DFA構(gòu)造與考試題中計(jì)算題相似,習(xí)題2.10,有一NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中S為初態(tài)，D為終態(tài),求出它的最小DFA 用正規(guī)式描述DFA所接受的語(yǔ)言,問(wèn)題：根據(jù)DFA寫(xiě)出對(duì)應(yīng)的正規(guī)式，通常的考慮和步驟是什么？,再重復(fù)一遍： 正規(guī)式、DFA是從兩個(gè)不同的側(cè)面表示一個(gè)集合(即正規(guī)集)。所以，根本的方法是把正規(guī)集作為橋梁，先分析清楚DFA識(shí)別出的是一個(gè)什么集合，然后再設(shè)計(jì)此集合的正規(guī)式。反之亦然。,習(xí)題2.10（2）
24、的解,,該DFA從初態(tài)到終態(tài)有三條路徑：b|c|a(a|c)*b，而且是這三條路徑的至少一次重復(fù)，故正規(guī)式為：(b|c|a(a|c)*b)+,習(xí)題3.7,設(shè)計(jì)一文法G，使得L(G)=|是不以0開(kāi)始的正奇數(shù) 思路：首先根據(jù)集合的描述設(shè)計(jì)幾個(gè)句子，然后從句子中找出規(guī)律（或共性），把它們的性質(zhì)用產(chǎn)生式表示出來(lái)。 解：正規(guī)式： 個(gè)位：13579 個(gè)位以上：0-9* 最高位：1-9 三段連起來(lái)：1-90-9*13579 兩種情況： 1-90-9*13579 | 13579 產(chǎn)生式： SACB|B A1|2|3|4|5|6|7|8|9 B1|3|5|7|9 C|0C|AC,習(xí)題3.14,下述四個(gè)文法，無(wú)需
25、構(gòu)造預(yù)測(cè)分析表，指出哪一個(gè)是LL(1)文法，并指出其他文法為什么不是LL(1)文法。,解： (1) 不是LL(1)文法，因?yàn)樗亲筮f歸的：S=Ra=Sba。 (2) 是LL(1)文法。 (3) 不是LL(1)文法，因?yàn)閷?duì)于S的兩個(gè)候選項(xiàng)Aa和Aa，F(xiàn)IRST(aA)FIRST(Aa)=a不滿(mǎn)足推論3.2的條件。 (4) 不是LL(1)文法，因?yàn)镾的前兩個(gè)候選項(xiàng)中含有左公因子iCtS，不滿(mǎn)足推論3.2的條件。,習(xí)題3.11+3.18,文法G如下: SaABeAb|Abc Bd (1) 改寫(xiě)G為等價(jià)的LL(1)文法； (2) 求每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合； (1) 構(gòu)造識(shí)別活
26、前綴的DFA； (2) 指出DFA中的沖突(如果有的話(huà))；,解：(3.11) (1) 改寫(xiě)后的文法： SaABe AbA AbcA| Bd (2) FIRST(S) = a, FOLLOW(S)=# FIRST(A) = b, FOLLOW(A)=d FIRST(A) = b,, FOLLOW(A)=d FIRST(B) = d, FOLLOW(B)=e,習(xí)題3.11+3.18（續(xù)）,解：(3.18) (1) SaABeAb|Abc Bd 的DFA如下。 (2) 無(wú)沖突。,44,To know how to do something well is to enjoy it.戰(zhàn)略上藐
27、視敵人，戰(zhàn)術(shù)上重視敵人。 The trees that are slow to grow bear the best fruit.,認(rèn)真復(fù)習(xí)、迎接考試 （結(jié) 束 2010年5月27日）,習(xí)題 3.17,對(duì)于文法G3.4和它所產(chǎn)生的句子-id+id*id 和 -(id+id)*id E E+T|T T T*F|F (G3.4) F (E) |-F|id （1）構(gòu)造基于LR(0)項(xiàng)目集的識(shí)別活前綴的DFA （2）指出DFA中所有含有沖突的項(xiàng)目集，并說(shuō)明這些沖突可以用SLR(1)方法解決； （3）構(gòu)造文法G3.4的SLR(1)分析表 （4）用分析表對(duì)句子-id+id*id 和 -(id+id)*
28、id進(jìn)行分析（以格局變化的方式） （5）根據(jù)（4）的分析給出-id+id*id的分析樹(shù)和剪句柄的過(guò)程 解：,習(xí)題 3.17（解）,（1）構(gòu)造基于LR(0)項(xiàng)目集的識(shí)別活前綴的DFA （2）指出DFA中所有含有沖突的項(xiàng)目集，并說(shuō)明這些沖突可以用SLR(1)方法解決；,沖突的項(xiàng)目集:I2，I11 計(jì)算FOLLOW(E)，看*是否在其中（略）,構(gòu)造SLR（1）分析表的方法：,1可移進(jìn)項(xiàng)直接從DFA上看： actionI,a:=sjgotoI,A:=k 2可歸約項(xiàng)分兩步走：若在I狀態(tài)中有A.， 首先計(jì)算：FOLLOW(A), 然后填寫(xiě)：actionI,b:=Ri 其中：bFOLLOW(A)且A是第i
29、個(gè)產(chǎn)生式。,,習(xí)題3.6,設(shè)字母表=0,1,設(shè)計(jì)下述語(yǔ)言的文法。對(duì)于正規(guī)語(yǔ)言， 可用正規(guī)式表示。 （1）每個(gè)0后面至少跟隨一個(gè)1的字符串 （2）0和1個(gè)數(shù)相等的字符串 （3）0和1個(gè)數(shù)不相等的字符串 （4）不以011作為子串的字符串,解：（1）(01|1)* （2）S0S1S|1S0S| （3）SA0A|B1B A0A1A|1A0A|0A|（0不少于1） B0B1B|1B0B|1B|（1不少于0） （4）1*(0|01)*,習(xí)題3.22,構(gòu)造SLR(1)分析表的算法3.9基于的假設(shè)是LR(0)項(xiàng)目集中可能有 沖突。如果基于的假設(shè)是LR(0)項(xiàng)目集中沒(méi)有沖突，則構(gòu)造方法 可以簡(jiǎn)化（無(wú)需計(jì)算F
30、OLLOW集合），得到的是LR(0)分析表。試 修改算法3.9成為構(gòu)造LR(0)分析表的算法。,1.if DFA中有不能解決的移進(jìn)/歸約和歸約/歸約沖突 then error; else for 每個(gè)狀態(tài)轉(zhuǎn)移Dtrani,x=j loop if xT then actioni,x:=Sj; else gotoi,x:=j; end if; end loop; for 狀態(tài)i的每個(gè)可歸約項(xiàng)A. loop if S S. then actioni, #:=acc; else for 每個(gè)aFOLLOW(A) loop actioni,a:=Rk; en
31、d loop; end if; end loop; end if;,每個(gè)終結(jié)符a,,,A.,狀態(tài)i：,B.,,,,x,,,習(xí)題 4.4,假定下述程序分別采用值調(diào)用，引用調(diào)用，復(fù)寫(xiě)-恢復(fù)和換名調(diào)用，請(qǐng)給出它們的打印結(jié)果。 program main(input output); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end; 兩種解題的思路： 1. 把自己當(dāng)作計(jì)算機(jī)，按照參數(shù)傳遞的實(shí)現(xiàn)方式“運(yùn)行”一遍程序，得出結(jié)果； 2. 找臺(tái)機(jī)子把程序敲進(jìn)去試試（輔
32、助手段） 困惑的是：表達(dá)式a+b如何作為引用調(diào)用和復(fù)寫(xiě)-恢復(fù)的實(shí)參？ 解決方案：忽略返回值問(wèn)題。其實(shí)這一思想可以推廣到任何不支持某種方式的情況（放心，考試中不會(huì)有這種很困惑的問(wèn)題） 具體結(jié)果（略）,習(xí)題4.9,設(shè)整型數(shù)組聲明的形式為int Ad1,d2,,d3，并且假設(shè)每個(gè)整型 數(shù)占據(jù)4個(gè)字節(jié)。 （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)情向量的 所有信息。,解： （1）n=1時(shí)，addr(Ai1)=a+(i1-1)*4 n=2時(shí)，addr(Ai1,i2)=a+(i2-1)*
33、d1*4+(i1-1)*4 addr(Ai1,i2,,in)=???,n維數(shù)組元素的地址計(jì)算,addr(Ai1，i2，...，in) =a+((in-1)*dn-1*dn-2*...*d1+(in-1-1)*dn-2*dn-3*...*d1+...+ (i1-1))*w =a-(dn-1*dn-2*...*d1+dn-2*dn-3*...*d1+...+d1+1)*w +(in*dn-1*dn-2*...*d1+in-1*dn-2*dn-3*...*d1+...+i2*d1+i1)*w =ac*w+v*w 其中：,c=dn-1*dn-2*dn-3*d1+dn-2*dn-3*dn-4*d1+*d
34、n-3*dn-4*dn-5*d1+d1+1 =(dn-1+1)*dn-2*...*d1+dn-3*dn-4...*d1+...+d1+1 =((dn-1+1)*dn-2+1)*dn-3*dn-4...*d1+...+d1+1 ...... =(...((dn-1+1)*dn-2+1)*dn-3...+1)*d1+1,同理： v = (...((in*dn-1+in-1)*dn-2+in-2)*dn-3...+i2)*d1+i1,n維數(shù)組元素的地址計(jì)算（續(xù)1）,c=(...((dn-1+1)*dn-2+1)*dn-3...+1)*d1+1 v=(...((in*dn-1+in-1)*dn-2+
35、in-2)*dn-3...+i2)*d1+i1,令： v0 = in 則： v1 = in*dn-1+in-1 = v0*dn-1+in-1 v2 = (v0*dn-1+in-1)*dn-2+in-2 = v1*dn-2+in-2 ...... 于是有： v0 = in vj = vj-1*dn-j+in-j (j=1，2，..., n-1) 同理可得： c0 = 1 cj = cj-1*dn-j+1 (j=1，2，..., n-1),（2）要適合LR分析，應(yīng)該將文法改成右遞歸的。,修改文法以適應(yīng)遞推公式的同步計(jì)算： A V := E(1) V id(2) | N EL(3) N id(4) EL E (5) | E , EL(6) E E + E(7) | ( E )(8) | V(9),習(xí)題4.10,教材中的語(yǔ)法制導(dǎo)翻譯將表達(dá)式Eid1
西安電子科技大學(xué)編譯原理復(fù)習(xí).ppt
