西安電子科技大學(xué)編譯原理復(fù)習PPT課件

1、1課程內(nèi)容課程內(nèi)容要求（希望）1. 牢固掌握基本概念2. 靈活使用基本方法3. 歸納總結(jié)所學(xué)內(nèi)容一、引言二、詞法分析三、語法分析四、語義分析語法制導(dǎo)翻譯生成中間代碼學(xué)習不能走捷徑，付出多少勞動就有多少收獲掌握正確的學(xué)習方法，提高自學(xué)能力第1頁/共54頁2第一章第一章 引言引言 語言的翻譯 不同的翻譯形式：匯編、編譯、轉(zhuǎn)換（預(yù)編譯）、逆向翻譯翻譯方法： 第2頁/共54頁3 編譯器的基本組成編譯器的基本組成 第3頁/共54頁4 編譯器的分析綜合模式編譯器的分析綜合模式 編譯器的掃描遍數(shù)與編譯器的編寫 第4頁/共54頁5第二章第二章 詞法分析詞法分析 構(gòu)詞規(guī)則與詞法分析： 首先規(guī)定單詞形成的規(guī)則，稱

2、為構(gòu)詞規(guī)則；然后根據(jù)構(gòu)詞規(guī)則識別輸入序列，稱為詞法分析。 主要內(nèi)容： 記號、模式與單詞 記號的說明模式的形式化描述（正規(guī)式與正規(guī)集） 記號的識別有限自動機 從正規(guī)式到詞法分析器 詞法分析器的作用：濾掉源程序中的無用成分；處理與具體操作系統(tǒng)或機器有關(guān)的輸入；識別記號并交給語法分析器；調(diào)用符號表管理器和出錯處理器進行相關(guān)處理。 第5頁/共54頁6 記號、模式與單詞記號、模式與單詞 模式（pattern）：規(guī)定單詞識別的規(guī)則記號（token）：按照某模式識別出的一類單詞（記號種類）單詞（lexeme）：被識別出的字符串本身詞法分析器的輸出：記號=記號種類+記號屬性 記號的說明模式的形式化描述 1.正

3、規(guī)式與正規(guī)集正規(guī)式與正規(guī)集的定義(基本正規(guī)式、三個運算)正規(guī)式的等價(描述相同的集合)利用正規(guī)式的等價對正規(guī)式進行化簡(正規(guī)式的代數(shù)性質(zhì))2.用正規(guī)式形式化描述模式如何用正規(guī)式描述程序設(shè)計語言中常見的記號，如標識符、數(shù)字、運算符和分隔符等正規(guī)式的簡化形式以及輔助定義與規(guī)則第6頁/共54頁7 記號的識別有限自動機（記號的識別有限自動機（FAFA） 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)移；當前狀態(tài)下，對同一字符有多于一個的下一狀態(tài)轉(zhuǎn)移；用NFA識別輸入序列

4、的弱點：嘗試所有路徑才能確定一個輸入不被接收、回溯帶來的問題；模擬DFA的算法（算法2.1 ）：用DFA識別記號。 第7頁/共54頁 從正規(guī)式到詞法分析器從正規(guī)式到詞法分析器 構(gòu)造NFA的Thompson算法(算法2.2)：與正規(guī)式的對應(yīng)關(guān)系； 模擬NFA的“并行”算法（算法2.3）； 從NFA構(gòu)造DFA子集法（算法2.5）：smove(S, a)與-閉包(T)的計算； DFA的最小化可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個狀態(tài)（算法2.6）； 靈活運用各種方法構(gòu)造DFA(正規(guī)式化簡、狀態(tài)轉(zhuǎn)換圖等)，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別（考慮(a|b)*abb的NFA）。第8頁/共54頁9第三章第

5、三章 語法分析語法分析 語法分析是編譯器中的重要階段之一，可以認為是語法制導(dǎo)翻譯模式編譯器的核心。語法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語言的各種結(jié)構(gòu)，即語法規(guī)則；根據(jù)語法規(guī)則識別輸入序列（記號流）中的語言結(jié)構(gòu)，即語法分析。 語法分析的分析對象是組成語言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對語法的分析就有了從根到葉子和從葉子到根兩種分析方法。 主要內(nèi)容 程序設(shè)計語言與文法 有關(guān)推導(dǎo)的基本概念 自上而下分析 自下而上分析 第9頁/共54頁10 程序設(shè)計語言與文法程序設(shè)計語言與文法 正規(guī)式與正規(guī)文法：正規(guī)式與正規(guī)文法用于描述線性結(jié)構(gòu)，如構(gòu)成句子的記號(終結(jié)符)；識別

6、正規(guī)語言的自動機是有限自動機，它們的特征是沒有記憶能力； 上下文無關(guān)文法(CFG=(N, T, S, P)：CFG用于描述層次結(jié)構(gòu)，如構(gòu)成程序的句子；識別CFL的自動機是下推自動機，它是在有限自動機的基礎(chǔ)上增加了一個下推棧，從而有了簡單的記憶能力； 文法的分類：0型、1型、2型和3型文法 詞法分析器與語法分析器：FA與PDA第10頁/共54頁11 有關(guān)推導(dǎo)的基本概念有關(guān)推導(dǎo)的基本概念 1.CFG產(chǎn)生語言的基本方法推導(dǎo)：從文法的開始符號開始，反復(fù)地用產(chǎn)生式的右部替換句型中的非終結(jié)符。 2.推導(dǎo)的基本概念：句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）；（定義3.2、3.3、3.4） 3.分

7、析樹與語法樹：分析樹和語法樹都反映了語言結(jié)構(gòu)；分析樹還記錄了分析的過程(含有非終結(jié)符)；(定義3.5、3.6) 4.文法的二義性：二義性的本質(zhì)是在文法中缺少對文法符號優(yōu)先級和結(jié)合性的限制，從而使得一個句子可以推導(dǎo)出多于一棵分析樹。(定義3.7) 5.二義性的消除：改寫二義文法為非二義文法；（兩個關(guān)鍵步驟） 對文法符號施加優(yōu)先級與結(jié)合性的限制，使得分析的每一步有唯一選擇。 第11頁/共54頁12 自上而下分析自上而下分析 1.分析方法：推導(dǎo)，從上到下構(gòu)造分析樹，是一種預(yù)測的、試探的方法； 2.對文法的要求：沒有公共左因子和左遞歸左遞歸與直接左遞歸（定義3.9）消除直接左遞歸與左遞歸（算法3.1、

8、3.2）提取公共左因子（類似于提取公因式）3.遞歸下降子程序方法：匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用） 第12頁/共54頁 自上而下分析（續(xù)）自上而下分析（續(xù)）4.預(yù)測分析表方法: 工作方式與過程：PDA（DPDA）格局：（棧內(nèi)容，當前剩余輸入，改變格局的動作）改變格局的動作：匹配終結(jié)符、展開非終結(jié)符、接受、報錯驅(qū)動器（算法3.4）預(yù)測分析表和分析表的構(gòu)造：分析表的構(gòu)成與意思：MA, aFIRST集合與FOLLOW集合（定義3.10、3.11）FIRST與FOLLOW的計算（算法3.5、3.6） 分析表的構(gòu)造（算法3.7） LL(1)文法及其判別：預(yù)測分析表中沒有多重定義條目（定義3.12、

9、推論3.2）。第13頁/共54頁14 自下而上分析自下而上分析 1.分析方法：歸約(推導(dǎo)的逆過程)，從葉子到根構(gòu)造分析樹；2.基本概念：短語、直接短語、句柄（定義3.13）最左歸約（定義3.14）、歸約、規(guī)范歸約3.采用的方法: 剪句柄實現(xiàn)方法：移進-歸約（格局中的兩個關(guān)鍵動作）4.關(guān)鍵問題：是如何確定棧頂已經(jīng)形成句柄，當句柄形成時，如何判定采用哪個產(chǎn)生式進行規(guī)約；5.移進-歸約分析器的工作模式（與預(yù)測分析表方法對著看）移進（匹配終結(jié)符）歸約（展開非終結(jié)符）驅(qū)動器（算法3.8）第14頁/共54頁 自下而上分析（續(xù)自下而上分析（續(xù)1 1）6.移進-歸約分析表：動作表（action）和轉(zhuǎn)移表（go

10、to）7.LR(k)文法（定義3.15）8.核心：識別活前綴的DFA：活前綴與LR(0)項目(NFA狀態(tài))（定義3.16、3.17 ）一個產(chǎn)生式是一個識別活前綴的NFA一個LR(0)項目是NFA的一個狀態(tài)9.拓廣文法與子集法構(gòu)造DFAclosure(I)、goto(I，X)(定義3.18、3.19 )核心項目與非核心項目（定義3.20）構(gòu)造算法（算法3.9）核心是：closure(goto(I，x)第15頁/共54頁16 自下而上分析（續(xù)自下而上分析（續(xù)2 2）10. DFA如何分析輸入序列有效項目（定義3.21）、可移進項目、可規(guī)約項目移進/歸約沖突、歸約/歸約沖突；解決沖突的方法SLR(1

11、)：簡單向前看一個終結(jié)符（計算歸約項非終結(jié)符的FOLLOW，與可移進終結(jié)符比較）； 11. 移進-歸約分析表的構(gòu)造：（算法3.10）； 12. LR文法與LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。第16頁/共54頁17第四章第四章 語法制導(dǎo)翻譯生成中間代碼語法制導(dǎo)翻譯生成中間代碼 討論程序設(shè)計語言的靜態(tài)語義分析，并且在語法分析的基礎(chǔ)上生成中間代碼，采用的基本方法是語法制導(dǎo)翻譯。 與前兩章詞法分析和語法分析不同的是，詞法分析和語法分析的討論側(cè)重于理論，而本章則側(cè)重于結(jié)合程序設(shè)計語言的實際例子討論語言結(jié)構(gòu)的具體翻譯方法和一些實用的技術(shù)。主要內(nèi)容 語法制導(dǎo)翻譯：概念與基本方法

12、中間代碼 符號表的組織 聲明語句的翻譯 可執(zhí)行語句的翻譯 第17頁/共54頁 語法制導(dǎo)翻譯的基本概念語法制導(dǎo)翻譯的基本概念1.語法與語義語法：語言的結(jié)構(gòu)；語義：附在結(jié)構(gòu)上的實際意思2.屬性與屬性的計算屬性：附在文法符號上的意思，如：val、place等語義規(guī)則：實現(xiàn)屬性的計算3.語義規(guī)則的兩種表現(xiàn)形式語法制導(dǎo)定義：抽象的屬性和計算表示的語義規(guī)則翻譯方案：具體的屬性和計算表示的語義規(guī)則第18頁/共54頁 基本設(shè)計方法基本設(shè)計方法1.與語法分析的關(guān)系：自下而上語法分析（LR分析的兩點擴充），自上而下語法分析（遞歸下降子程序方法）2.語義規(guī)則的設(shè)計：設(shè)計屬性、基本操作（函數(shù)或過程）、語義規(guī)則；3.聲

13、明性語句：需要保存什么信息，這些信息有哪些特征，設(shè)計什么樣的數(shù)據(jù)結(jié)構(gòu)存放這些信息，以便于對它們的處理；4.可執(zhí)行語句：語句的結(jié)構(gòu)應(yīng)生成什么樣的中間代碼序列，根據(jù)中間代碼序列設(shè)計語法制導(dǎo)定義，根據(jù)序列的特點設(shè)計翻譯方案。 第19頁/共54頁 中間代碼中間代碼1.為什么生成中間代碼：中間代碼是編譯器分析綜合模式前端與后端的分水嶺；2.中間代碼的特征：形式接近目標機器代碼，但又與具體機器無關(guān)，便于編譯器的開發(fā)移植和代碼的優(yōu)化；3.常用的中間代碼形式：后綴式、樹（圖）、三地址碼；4.三地址碼的實現(xiàn)：三元式、四元式5.中間代碼之間的關(guān)系：樹與后綴式的關(guān)系樹與三元式和四元式的關(guān)系 第20頁/共54頁 符號

14、表的組織符號表的組織1.符號表的作用：連接聲明與引用的橋梁2.符號表的條目與信息的存儲：直接存儲與間接存儲3.作用域信息的保存靜態(tài)作用域+最近嵌套原則線性表：棧結(jié)構(gòu)，表上的操作散列表：每個子表是棧結(jié)構(gòu)，提高表上操作的效率 第21頁/共54頁 聲明語句的翻譯聲明語句的翻譯1.定義與聲明：類型定義與變量聲明，過程定義與過程聲明2.變量聲明：符號表信息的填寫（簡單變量和數(shù)組變量）；3.過程聲明：左值與右值；參數(shù)傳遞：參數(shù)傳遞的不同形式，各種參數(shù)傳遞形式的處理方式；名字的作用域：滿足靜態(tài)作用域與最近嵌套原則；聲明中作用域信息的保存。 第22頁/共54頁 可執(zhí)行語句的翻譯可執(zhí)行語句的翻譯1.簡單算術(shù)表達

15、式和賦值句的翻譯：語法制導(dǎo)翻譯的設(shè)計，類型轉(zhuǎn)換；2.數(shù)組元素的引用：多維數(shù)組到一維存儲空間的映射；數(shù)組元素地址計算的遞推公式；數(shù)組元素地址計算的語法制導(dǎo)翻譯；3.布爾表達式短路計算的翻譯：為什么需要短路計算和短路計算的控制流；真出口與假出口；拉鏈/回填技術(shù)：真值鏈與假值鏈4.控制語句的翻譯：控制語句的分類，轉(zhuǎn)移與條件轉(zhuǎn)移。 第23頁/共54頁結(jié)結(jié) 束（束（20102010年年5 5月月2525日）日）第24頁/共54頁試題與習題試題與習題認真復(fù)習，重點是掌握基本概念。基本概念掌握了，相當一部分試題的解就有了。習題與試題的目的區(qū)別：習題的目的是通過反復(fù)的練習理解、掌握所學(xué)知識，會有不少繁、難、大

16、量步驟的題；試題的目的是考察對本課程綜合掌握的情況，特點是短時間內(nèi)覆蓋大量內(nèi)容。太繁瑣步驟或太難等需要耗費大量時間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會有一些綜合性的題目。自己要會辨別什么是主要的什么是次要的，抓什么丟什么?！盎靖拍钜獓乐敚ㄇ宄痉椒ㄒ`活”?？傊痪湓?，學(xué)習方法的掌握是個人努力的結(jié)果，單純靠別人教是學(xué)不會的。第25頁/共54頁26關(guān)于考試關(guān)于考試 題目類型：填空題(30分)、簡答題(20分)、計算題(50分)考試范圍：14章講過的內(nèi)容側(cè)重考察：基本概念與基本方法的掌握易犯的錯誤1. 不認真審題（對題目的要求理解錯誤：意思理解錯、難題想容易、容易題想難。關(guān)鍵問

17、題是基本概念不清楚）2. 所答非所問(例如：沒有要求LL分析卻將文法改為LL的)3. 畫蛇添足(例如：僅問有無沖突卻將分析表先構(gòu)造出來)4. 偷工減料(例如：有若干問，僅回答部分或問題僅答一半)警示千萬不要作弊！命運掌握在自己的手中！第26頁/共54頁實際試題舉例實際試題舉例一、簡答題一、簡答題1（2分）有哪些方法可以去除文法的二義性。2（2分）寫出 -(a+b)*c)+d 的后綴式。3（4分）試證明正規(guī)式(ab)*a與a(ba)*是等價的。1 （1）改寫文法 （2）規(guī)定文法符號的優(yōu)先級和結(jié)合性2 ab+c*d+（或ab+c*-d+）3 證明： 考慮L(ab)*a)中的任意一個串a(chǎn)babab.

18、aba， 由串連接的結(jié)合性可得：a(ba)(ba)(b.a)(ba)，它恰好是L(a(ba)*)，即L(ab)*a)= L(a(ba)*)。 也可以用歸納法證明（提示：以ab重復(fù)0次、1次作為歸納基礎(chǔ)，假設(shè)ab重復(fù)n次成立，證明ab重復(fù)n+1次也成立）。第27頁/共54頁二、填空題（二、填空題（3030分）分）1（6分）編譯程序的基本組成有：詞法分析、 、 、中間代碼生成、 、 、 和 。2（1分）正規(guī)式r和s等價說明 相同。3（2分）不含子串baa的所有a、b符號串的正規(guī)式是 。4（4分） 已知文法G定義如下： SeT|RT TDR| RdR| Da|bd則FIRST(S)= ，F(xiàn)IRST(

19、D)= ，F(xiàn)IRST(T)= ，F(xiàn)IRST(R)= 。 1 語法分析、語義分析、代碼優(yōu)化、目標代碼生成、符號表管理和出錯處理 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， 。第28頁/共54頁三、計算題（三、計算題（1 1）1（13分）已知一個NFA如圖。 (a)(4分) 用自然語言簡要敘述該自動機所識別的語言 的特點，列舉兩個它可識別的串。 (b)（3分）寫出與該自動機等價的正規(guī)式r。 (c)（6分）用子集法構(gòu)造識別r的最小DFA。012bba,ba,b第29頁

20、/共54頁 解：解：1.含有至少兩個連續(xù)b的a、b串，例如bb、bbb等。2.r=(a|b)*bb(a|b)*。3.直接用狀態(tài)轉(zhuǎn)換矩陣構(gòu)造：初態(tài)：0子集法得：（2是終態(tài)）ab000,10,100,1,20,1,2 0,20,1,20,20,20,1,2令： 0=A，0,1=B，0,1,2=C，0,2=D得：abAABBACCDCDDC最小化DFA得：（C和D不可區(qū)分）abAABBACCCC第30頁/共54頁三、計算題（三、計算題（2 2）2（15分）有文法G和G的語法制導(dǎo)翻譯如下：EE1*T E.place=newtemp; emit(*,E1.place,T.place,E.place; |

21、 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=; (a)（4分）求句型(T+F)*id 的短語、直接短語以及句柄；(b)（4分）根據(jù)語法制導(dǎo)翻譯寫出句子a*b+c*d的中間代碼；(c)（3分）若a=3，b=5，c=7，d=8，請給出中間代碼計算結(jié)果；(d)（4分）將文法G簡化為：EE*T|T，TT+F|F，F(xiàn)id。給出它的識別活前綴的DFA。 第31頁/共54頁 解

22、：解：(a) 短語：(T+F)*id、(T+F)、T+F、id 直接短語：T+F、id 句柄：T+F(b) a*b+c*d的中間代碼： (1) (+, b, c, t1)(2) (*, a, t1, t2)(3) (*, t2, d, t3)(c) 計算結(jié)果：t3=288 (d) 識別活前綴的DFA： E.EE.E*TE.TT.T+FT.FF.idEE.EE.*TET.TT.+FTF.Fid.EE*.TT.T+FT.FF.idTT+.FF.idEE*T.TT.+FFETFid*+TididI0I1I2I3I4I5I6I7TT+F.I8F第32頁/共54頁33部分習題解答部分習題解答第33頁/共

23、54頁習題習題2.42.4寫出下述語言的正規(guī)式描述（1）由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有01串（2）所有不含子串011的01串（3）每個a后面至少緊隨兩個b的ab串（4）C的形如/*/ 的注釋。其中代表不含*/的字符串思路：分析題意，從最簡單的例子考慮，然后找出統(tǒng)一規(guī)律（1）的解題步驟：1. 最簡單的符合要求的串：1、010（還有100、001、111等）2. 所有01均為偶數(shù)的串： A=(00|11)|(01|10)(00|11)*(10|01)*3. 符合要求的所有串：A1A、A0A1A0A（為什么沒有后三個？）結(jié)果：A1A | A0A1A0A思考：識別它的DFA又應(yīng)該如何構(gòu)造？第34頁/共

24、54頁（4 4） C C的形如的形如/ /* * */ / 的注釋。其中的注釋。其中代表不含代表不含* */ /的字的字符串符串思路：注釋中若遇到*：若后邊是/則結(jié)束注釋否則仍然是注釋步驟：1. 注釋串是空；2. 考慮沒有*的注釋；3. 考慮含*的注釋結(jié)果：(4) /* (*|*/)* */（2）所有不含子串011的01串：1*(01|0)*（3）每個a后面至少緊隨兩個b的ab串：(b|abb)*第35頁/共54頁習題習題2.92.9 用自然語言給出下述正規(guī)式所描述的語言，并構(gòu)造他們的最小DFA：10*1(0|1)*011(0|1)*說明：所謂用自然語言描述就是解釋字符串的性質(zhì)，一般情況下是已

25、經(jīng)有了形式化描述。解：10*1：首尾是1中間有零或若干個0的01串。(0|1)*011(0|1)* ：至少含一個011的01串。注意： *是0或若干次的重復(fù)；+是至少一次的重復(fù) 絕對不允許用正規(guī)式表示，因為正規(guī)式是已知條件DFA（略）(0|1)*011(0|1)* 的DFA構(gòu)造與考試題中計算題相似第36頁/共54頁習題習題2.102.10有一NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中S為初態(tài)，D為終態(tài)abcSA,BC,DDA,B,CAACBBADCCBAADCBS1.求出它的最小DFA2.用正規(guī)式描述DFA所接受的語言問題：根據(jù)DFA寫出對應(yīng)的正規(guī)式，通常的考慮和步驟是什么？ 再重復(fù)一遍： 正規(guī)式、DFA

26、是從兩個不同的側(cè)面表示一個集合(即正規(guī)集)。所以，根本的方法是把正規(guī)集作為橋梁，先分析清楚DFA識別出的是一個什么集合，然后再設(shè)計此集合的正規(guī)式。反之亦然。第37頁/共54頁習題習題2.102.10（2 2）的解的解 該DFA從初態(tài)到終態(tài)有三條路徑：b|c|a(a|c)*b，而且是這三條路徑的至少一次重復(fù)，故正規(guī)式為：(b|c|a(a|c)*b)+第38頁/共54頁習題習題3.73.7設(shè)計一文法G，使得L(G)=|是不以0開始的正奇數(shù)思路：首先根據(jù)集合的描述設(shè)計幾個句子，然后從句子中找出規(guī)律（或共性），把它們的性質(zhì)用產(chǎn)生式表示出來。解：正規(guī)式：個位：13579 個位以上：0-9* 最高位：1-

27、9三段連起來：1-90-9*13579兩種情況： 1-90-9*13579 | 13579產(chǎn)生式：SACB|BA1|2|3|4|5|6|7|8|9B1|3|5|7|9C|0C|AC第39頁/共54頁習題習題3.143.14(3) S aA | Aa A b |(4) S iCtS | iCtSeS | a C b(1) S Ra | a R Sb | b(2) S aAc | b A a | b | 下述四個文法，無需構(gòu)造預(yù)測分析表，指出哪一個是LL(1)文法，并指出其他文法為什么不是LL(1)文法。解：(1) 不是LL(1)文法，因為它是左遞歸的：S=Ra=Sba。(2) 是LL(1)文法。

28、( 3 ) 不 是 L L ( 1 ) 文 法 ， 因 為 對 于 S 的 兩 個 候 選 項 A a 和 A a ，F(xiàn)IRST(aA)FIRST(Aa)=a不滿足推論3.2的條件。(4) 不是LL(1)文法，因為S的前兩個候選項中含有左公因子iCtS，不滿足推論3.2的條件。第40頁/共54頁習題習題3.11+3.183.11+3.18文法G如下: SaABeAb|Abc Bd(1) 改寫G為等價的LL(1)文法；(2) 求每個非終結(jié)符的FIRST集合和FOLLOW集合；(1) 構(gòu)造識別活前綴的DFA；(2) 指出DFA中的沖突(如果有的話)；解：(3.11) (1) 改寫后的文法：SaAB

29、e 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第41頁/共54頁習題習題3.11+3.183.11+3.18（續(xù)）（續(xù)）解：(3.18) (1) SaABeAb|Abc Bd 的DFA如下。(2) 無沖突。第42頁/共54頁43To know how to do something To know how to do something well is to enjoy it.well is to e

30、njoy it.戰(zhàn)略上藐視敵人，戰(zhàn)術(shù)上重視敵人。戰(zhàn)略上藐視敵人，戰(zhàn)術(shù)上重視敵人。 The trees that are slow to The trees that are slow to grow bear the best fruit.grow bear the best fruit. 認真復(fù)習、迎接考試（結(jié) 束 2010年5月27日）第43頁/共54頁習題習題 3.173.17對于文法G3.4和它所產(chǎn)生的句子-id+id*id 和 -(id+id)*idE E+T|TT T*F|F (G3.4)F (E) |-F|id（1）構(gòu)造基于LR(0)項目集的識別活前綴的DFA（2）指出DFA中所

31、有含有沖突的項目集，并說明這些沖突可以用SLR(1)方法解決；（3）構(gòu)造文法G3.4的SLR(1)分析表（4）用分析表對句子-id+id*id 和 -(id+id)*id進行分析（以格局變化的方式）（5）根據(jù)（4）的分析給出-id+id*id的分析樹和剪句柄的過程解：第44頁/共54頁習題習題 3.173.17（解）（解）（1）構(gòu)造基于LR(0)項目集的識別活前綴的DFA（2）指出DFA中所有含有沖突的項目集，并說明這些沖突可以用SLR(1)方法解決； 沖突的項目集:I2，I11 計算FOLLOW(E)，看*是否在其中（略）第45頁/共54頁構(gòu)造構(gòu)造SLRSLR（1 1）分析表的方法：分析表的

32、方法：1可移進項直接從DFA上看：actionI,a:=sjgotoI,A:=k2可歸約項分兩步走：若在I狀態(tài)中有A.，首先計算：FOLLOW(A),然后填寫：actionI,b:=Ri其中：bFOLLOW(A)且A是第i個產(chǎn)生式。 第46頁/共54頁習題習題3.63.6 設(shè)字母表=0,1,設(shè)計下述語言的文法。對于正規(guī)語言，可用正規(guī)式表示。（1）每個0后面至少跟隨一個1的字符串（2）0和1個數(shù)相等的字符串（3）0和1個數(shù)不相等的字符串（4）不以011作為子串的字符串解：（1）(01|1)* （2）S0S1S|1S0S| （3）SA0A|B1B A0A1A|1A0A|0A|（0不少于1） B0B

33、1B|1B0B|1B|（1不少于0） （4）1*(0|01)*第47頁/共54頁習題習題3.223.22構(gòu)造SLR(1)分析表的算法3.9基于的假設(shè)是LR(0)項目集中可能有沖突。如果基于的假設(shè)是LR(0)項目集中沒有沖突，則構(gòu)造方法可以簡化（無需計算FOLLOW集合），得到的是LR(0)分析表。試修改算法3.9成為構(gòu)造LR(0)分析表的算法。1.if DFA中有不能解決的移進/歸約和歸約/歸約沖突 then error; else for 每個狀態(tài)轉(zhuǎn)移Dtrani,x=j loop if xT then actioni,x:=Sj; else gotoi,x:=j; end if; end

34、loop; for 狀態(tài)i的每個可歸約項A. loop if S S. then actioni, #:=acc; else for 每個aFOLLOW(A) loop actioni,a:=RkRk; end loop; end if; end loop; end if; 每個終結(jié)符aA.狀態(tài)i：B. .x x第48頁/共54頁習題習題 4.44.4假定下述程序分別采用值調(diào)用，引用調(diào)用，復(fù)寫-恢復(fù)和換名調(diào)用，請給出它們的打印結(jié)果。 program main(input output); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin a

35、:=2; b:=3; p(a+b, a, a); print a end;兩種解題的思路：1. 把自己當作計算機，按照參數(shù)傳遞的實現(xiàn)方式“運行”一遍程序，得出結(jié)果；2. 找臺機子把程序敲進去試試（輔助手段）困惑的是：表達式a+b如何作為引用調(diào)用和復(fù)寫-恢復(fù)的實參？解決方案：忽略返回值問題。其實這一思想可以推廣到任何不支持某種方式的情況（放心，考試中不會有這種很困惑的問題）具體結(jié)果（略）第49頁/共54頁習題習題4.94.9設(shè)整型數(shù)組聲明的形式為int Ad1,d2,d3，并且假設(shè)每個整型數(shù)占據(jù)4個字節(jié)。（1）試導(dǎo)出以列為主存儲時計算c和v的遞推公式；（2）*設(shè)計數(shù)組聲明的語法制導(dǎo)翻譯（包括語法和語義），以使得在對數(shù)組聲明從左到右分析的同時，正確填寫符號表和內(nèi)情向量的所有信息。解：（1）n=1時，addr(Ai1)=a+(i1-1)*4n=2時，addr(Ai1,i2)=a+(i2-1)*d1*4+