編譯原理總復(fù)習(xí)習(xí)題與試題實(shí)用教案

1、如果如果(rgu)(rgu)是是我復(fù)習(xí)我復(fù)習(xí)詞法分析基本概念：正規(guī)式：正規(guī)表達(dá)式。正規(guī)集：正規(guī)表達(dá)式所表示的集合。有限自動機(jī)(一個(gè)五元數(shù)組)：確定的有限自動機(jī)(DFA)和非確定的有限自動機(jī)(NFA)。詞法分析器的構(gòu)造：1)單詞符號分類；2)單詞輸出的形式常見計(jì)算題類型：已知集合求正規(guī)式、DFA；已知正規(guī)式求DFA、集合；已知FA求正規(guī)式、集合；FA的確定化、最小化。語法分析基本概念：上下文無關(guān)文法、語言、下推自動機(jī)，LL分析與LR分析；一些(yxi)必要的定義、公式、算法的核心思想等；常見的計(jì)算題類型：（自己思考）基本解題方法與技巧等。3. 語法制導(dǎo)翻譯（略）4. 運(yùn)行環(huán)境（略）（哪些最重要？

2、）第1頁/共30頁第一頁，共31頁。2關(guān)于關(guān)于(guny)(guny)考試考試 題目類型：簡答題(25分)、填空題(25分)、計(jì)算題(50分)內(nèi)容分布(大概)：概述與詞法分析(30分)、語法分析(40分)、語法制導(dǎo)翻譯與運(yùn)行環(huán)境(30分) 考試范圍：15章講過的內(nèi)容側(cè)重考察(koch)：基本概念與基本方法的掌握易犯的錯誤不認(rèn)真審題（對題目的要求理解錯誤：意思理解錯、難題想容易、容易題想難。關(guān)鍵問題是基本概念不清楚）所答非所問(例如：沒有要求LL分析卻將文法改為LL的)畫蛇添足(例如：僅問有無沖突卻將分析表先構(gòu)造出來)偷工減料(例如：有若干(rugn)問，僅回答部分或問題僅答一半)警示千萬不要作

3、弊！命運(yùn)掌握在自己的手中！第2頁/共30頁第二頁，共31頁。實(shí)際實(shí)際(shj)(shj)試題舉例試題舉例一、簡答題一、簡答題（2分）有哪些方法可以去除(q ch)文法的二義性。（2分）寫出 -(a+b)*c)+d 的后綴式。（4分）試證明正規(guī)式(ab)*a與a(ba)*是等價(jià)的。1.1 1.1 （1 1）改寫文法）改寫文法 （2 2）規(guī)定文法符號的優(yōu)先級和結(jié)合性）規(guī)定文法符號的優(yōu)先級和結(jié)合性1.2 ab+c1.2 ab+c* *d+d+（或（或ab+cab+c* *-d+-d+）1.5 1.5 證明：證明： 考慮考慮L(ab)L(ab)* *a)a)中的任意一個(gè)串中的任意一個(gè)串a(chǎn)babab.a

4、baababab.aba， 由串連接由串連接(linji)(linji)的結(jié)合性可得：的結(jié)合性可得：a(ba)(ba)(b.a)(ba)a(ba)(ba)(b.a)(ba)，它恰好是，它恰好是L(a(ba)L(a(ba)* *) )，即，即L(ab)L(ab)* *a)= a)= L(a(ba)L(a(ba)* *) )。 也可以用歸納法證明（提示：以也可以用歸納法證明（提示：以abab重復(fù)重復(fù)0 0次、次、1 1次作為歸納基礎(chǔ)，假設(shè)次作為歸納基礎(chǔ)，假設(shè)abab重復(fù)重復(fù)n n次成立，證明次成立，證明abab重重復(fù)復(fù)n+1n+1次也成立）。次也成立）。第3頁/共30頁第三頁，共31頁。二、填空題

5、（二、填空題（3030分）分）（6分）編譯程序的基本組成有：詞法分析、 、 、中間代碼生成、 、 、 和 。（1分）正規(guī)式r和s等價(jià)說明 相同。（2分）不含子串baa的所有(suyu)a、b符號串的正規(guī)式是 。（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)= 。 2.2 語法分析、語義分析、代碼優(yōu)化、目標(biāo)代碼生成、 符號表管理和出錯處理 2.3 r和s表示(biosh)的正規(guī)集 a*(b|ba)* FIRST(S)= e，d，a，b ，F(xiàn)IRST(D)= a，b ，F(xiàn)IRST(T)

6、= ，a，b ，F(xiàn)IRST(R)= d， 。第4頁/共30頁第四頁，共31頁。三、計(jì)算題（）三、計(jì)算題（）（13分）已知一個(gè)NFA如圖。 (a)(4分) 用自然語言簡要敘述該自動機(jī)所識別的語言 的特點(diǎn)(tdin)，列舉兩個(gè)它可識別的串。 (b)（3分）寫出與該自動機(jī)等價(jià)的正規(guī)式r。 (c)（6分）用子集法構(gòu)造識別r的最小DFA。012bba,ba,b第5頁/共30頁第五頁，共31頁。（）解：（）解：含有至少兩個(gè)連續(xù)(linx)b的a、b串，例如bb、bbb等。r=(a|b)*bb(a|b)*。直接用狀態(tài)轉(zhuǎn)換矩陣構(gòu)造：初態(tài)：0子集法得：（2是終態(tài)）ab000,10,100,1,20,1,2 0,

7、20,1,20,20,20,1,2令： 0=A，0,1=B，0,1,2=C，0,2=D得：abAABBACCDCDDC最小化DFA得：（C和D不可(bk)區(qū)分）abAABBACCCC第6頁/共30頁第六頁，共31頁。三、計(jì)算題（）三、計(jì)算題（）（15分）有文法G和G的語法制導(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

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

9、t1)(2) (*, a, t1, t2)(3) (*, t2, d, t3)(c) 計(jì)算結(jié)果：t3=288 (d) 識別(shbi)活前綴的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第8頁/共30頁第八頁，共31頁。9部分部分(b fen)(b fen)習(xí)題解答習(xí)題解答第9頁/共30頁第九頁，共31頁。習(xí)題習(xí)題(xt)(xt)寫出下述語言的正規(guī)式描述(mio sh)（1）由偶數(shù)個(gè)0和奇數(shù)個(gè)

10、1構(gòu)成的所有01串（2）所有不含子串011的01串（3）每個(gè)a后面至少緊隨兩個(gè)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（為什么沒有后三個(gè)？）結(jié)果：A1A | A0A1A0A思考：識別(shbi)它的DFA又應(yīng)該如何構(gòu)造？第10頁/共30頁第十頁，共31頁。（4 4）C C的形如的形如/ /*

11、* */ / 的注釋的注釋(zhsh)(zhsh)。其中。其中代表代表不含不含* */ /的字符串的字符串思路：注釋中若遇到*：若后邊是/則結(jié)束注釋否則仍然是注釋步驟：1. 注釋串是空；2. 考慮(kol)沒有*的注釋；3. 考慮(kol)含*的注釋結(jié)果：(4) /* (*|*/)* */（2）所有(suyu)不含子串011的01串：1*(01|0)*（3）每個(gè)a后面至少緊隨兩個(gè)b的ab串：(b|abb)*第11頁/共30頁第十一頁，共31頁。習(xí)題習(xí)題(xt)(xt) 用自然語言(yyn)給出下述正規(guī)式所描述的語言(yyn)，并構(gòu)造他們的最小DFA：10*1(0|1)*011(0|1)*說明：

12、所謂用自然語言描述就是解釋字符串的性質(zhì)，一般情況(qngkung)下是已經(jīng)有了形式化描述。解：10*1：首尾是1中間有零或若干個(gè)0的01串。(0|1)*011(0|1)* ：至少含一個(gè)011的01串。注意：絕對不允許用正規(guī)式表示，因?yàn)檎?guī)式是已知條件第12頁/共30頁第十二頁，共31頁。習(xí)題習(xí)題(xt)(xt)有一NFA的狀態(tài)(zhungti)轉(zhuǎn)換矩陣下表，其中S為初態(tài)，D為終態(tài)abcSA,BC,DDA,B,CAACBBADCCBAADCBS求出它的最小DFA用正規(guī)式描述(mio sh)DFA所接受的語言問題：根據(jù)DFA寫出對應(yīng)的正規(guī)式，通常的考慮和步驟是什么？ 再重復(fù)一遍： 正規(guī)式、DFA是

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

14、表示出來。解：正規(guī)式：個(gè)位：13579 個(gè)位以上：0-9* 最高位：1-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第15頁/共30頁第十五頁，共31頁。習(xí)題習(xí)題(xt) (xt) 對于文法和它所產(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)項(xiàng)目集的識別活前綴的DFA（2）指出DFA中所有含有沖突的項(xiàng)目集，并說明這些沖突可以用SLR(1)方法解決；（3）構(gòu)造文法

15、的SLR(1)分析表（4）用分析表對句子-id+id*id 和 -(id+id)*id進(jìn)行分析（以格局變化(binhu)的方式）（5）根據(jù)（4）的分析給出-id+id*id的分析樹和剪句柄的過程解：作為練習(xí)，本題的每一步都是必要的。相對來說分析表的構(gòu)造并不重要。（具體步驟有時(shí)間板書）第16頁/共30頁第十六頁，共31頁。構(gòu)造構(gòu)造(guzo)SLR(guzo)SLR（1 1）分析表的方法：）分析表的方法：1可移進(jìn)項(xiàng)直接(zhji)從DFA上看：actionI,a:=sjgotoI,A:=k2可歸約項(xiàng)分兩步走：若在I狀態(tài)中有A.，首先計(jì)算：FOLLOW(A),然后填寫：actionI,b:=Ri其

16、中：bFOLLOW(A)且A是第i個(gè)產(chǎn)生式。 第17頁/共30頁第十七頁，共31頁。習(xí)題習(xí)題(xt) (xt) 假定下述程序分別采用值調(diào)用，引用調(diào)用，復(fù)寫-恢復(fù)(huf)和換名調(diào)用，請給出它們的打印結(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. 找臺機(jī)子把程序敲進(jìn)去試試（輔助手段）困惑的是：表達(dá)式a+b如何

17、作為引用調(diào)用和復(fù)寫-恢復(fù)(huf)的實(shí)參？解決方案：忽略返回值問題。其實(shí)這一思想可以推廣到任何不支持某種方式的情況（放心，考試中不會有這種很困惑的問題）具體結(jié)果（略）第18頁/共30頁第十八頁，共31頁。習(xí)題習(xí)題(xt)5.5 (xt)5.5 procedure A is procedure B is Procedure D is x : character; begin end D; begin end B; procedure C is x : integer; procedure E is y: integer; begin end E; procedure F is y: float

18、; begin end F; begin end D;begin end A; 有一過程A如下所示。采用靜態(tài)(jngti)作用域、最近嵌套原則，設(shè)A是第0層的過程。第19頁/共30頁第十九頁，共31頁。習(xí)題習(xí)題(xt)(xt)（續(xù)）（續(xù)）（4）若一個(gè)可能的程序運(yùn)行控制(kngzh)流是 A-C-E-F-B,試給出每次調(diào)用和返回時(shí)的控制(kngzh)棧中各活動記錄的可確定內(nèi)容和顯示表的變化；（5）分別給出C調(diào)用E的調(diào)用序列和從E返回的返回序列。說明：（4）（5）是學(xué)生希望講解的題目解：（4）若一個(gè)可能的程序運(yùn)行控制(kngzh)流是 A-C-E-F-B，給出控制(kngzh)棧中的內(nèi)容和控制(k

19、ngzh)鏈與訪問鏈的指向。靜態(tài)嵌套結(jié)構(gòu)、活動棧、以及控制(kngzh)鏈與訪問鏈：第20頁/共30頁第二十頁，共31頁。21ToTo know how know how toto do something do something well is well is toto enjoy it. enjoy it.戰(zhàn)略上藐視戰(zhàn)略上藐視(miosh)(miosh)敵人，戰(zhàn)術(shù)上敵人，戰(zhàn)術(shù)上重視敵人。重視敵人。 The trees that are slow The trees that are slow toto grow bear the best fruit. grow bear the bes

20、t fruit. 認(rèn)真復(fù)習(xí)、迎接(yngji)考試（結(jié) 束 2007年6月19日）第21頁/共30頁第二十一頁，共31頁。22附件附件(fjin)1(fjin)1：教材與習(xí)題答案：教材與習(xí)題答案中的錯誤中的錯誤 教材教材23頁：例上邊兩行：將“Msi,sj”改為“Msi,ch”將“.是從狀態(tài)si到狀態(tài)sj的邊上的標(biāo)記ch(或)?！备臑椤?是從狀態(tài)si經(jīng)ch(或)到達(dá)的下一狀態(tài)sj。”24頁：倒11行：將“Msi,sj”改為“Msi,ch”25頁：圖最后一行狀態(tài)“000”應(yīng)改為“012”34頁：算法方法(fngf)2、3行：將“從si出發(fā)”改為“從si出發(fā)”，將“稱為D的初態(tài)”改為“稱為D的初態(tài)

21、”45頁：10行：將“N是僅出現(xiàn)”改為“僅N是可以出現(xiàn)”70頁：例：將FOLLOW集合中的“”改為“”75頁：到4行：將“文法”改為“文法”81頁：圖：將I0中的“T.-F”改為“F.-F”第22頁/共30頁第二十二頁，共31頁。23附件附件(fjin)1(fjin)1：教材與習(xí)題答案中的錯誤（續(xù)：教材與習(xí)題答案中的錯誤（續(xù)1 1）教材(jioci)100頁：圖：將A.code=(3)“(x,:=,(2)”改為“(:=,x,(2)”129頁：例的中間代碼：將“t3:=+r t4”改為“t3:=C +r t4”133頁：例的中間代碼：將“t5:=t3*t4”改為“t5:=t3*4”，將“V7”改

22、為“V5”134頁：圖：將“V5、V6、V7”分別改為“V6、V7、V5”136頁：上邊一行：將“ptr.data/=x”改為“ptr.data=x”138頁：例：將代碼序列中的“L1”改為“L2”， “L2”改為“L1”144頁：例上邊一行：將“mklist”改為“mkchain”習(xí)題解答(jid)4頁：2.4(1)：A1A|A0A1A0可以簡化為A(1|010)A32頁：缺少3.19(1)的解答(jid)32頁：到2行：將兩處“I10”均改為“I11”，將“I12”改為“I13”第23頁/共30頁第二十三頁，共31頁。二班二班(r bn)(r bn)同學(xué)提出的問題及相應(yīng)解答同學(xué)提出的問題及

23、相應(yīng)解答習(xí)題習(xí)題 設(shè)字母表=0,1,設(shè)計(jì)下述語言的文法。對于正規(guī)語言，可用正規(guī)式表示。（1）每個(gè)0后面至少跟隨一個(gè)(y )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| B0B1B|1B0B|1B| （4）1*(0|01)*第24頁/共30頁第二十四頁，共31頁。習(xí)題習(xí)題(xt)(xt)構(gòu)造SLR(1)分析表的算法3.9基于(jy)的假設(shè)是LR(0)項(xiàng)目集中可能有沖突。如果基于(jy)的假設(shè)是LR(0)項(xiàng)目集中沒有沖突，則構(gòu)造方法可以

24、簡化（無需計(jì)算FOLLOW集合），得到的是LR(0)分析表。試修改算法3.9成為構(gòu)造LR(0)分析表的算法。1.if DFA中有不能解決的移進(jìn)/歸約和歸約/歸約沖突 then error; else for 每個(gè)狀態(tài)(zhungti)轉(zhuǎn)移Dtrani,x=j loop if xT then actioni,x:=Sj; else gotoi,x:=j; end if; end loop; for 狀態(tài)(zhungti)i的每個(gè)可歸約項(xiàng)A. loop if S S. then actioni, #:=acc; else for 每個(gè)aFOLLOW(A) loop actioni,a:=Rk; e

25、nd loop; end if; end loop; end if; 每個(gè)終結(jié)符aA.狀態(tài)i：BB. .x x第25頁/共30頁第二十五頁，共31頁。習(xí)題習(xí)題(xt)(xt)設(shè)整型數(shù)組聲明的形式為int Ad1,d2,d3，并且假設(shè)每個(gè)整型數(shù)占據(jù)4個(gè)字節(jié)。（1）試導(dǎo)出以列為主存儲時(shí)計(jì)算c和v的遞推公式；（2）*設(shè)計(jì)數(shù)組聲明的語法(yf)制導(dǎo)翻譯（包括語法(yf)和語義），以使得在對數(shù)組聲明從左到右分析的同時(shí)，正確填寫符號表和內(nèi)情向量的所有信息。解：（1）n=1時(shí)，addr(Ai1)=a+(i1-1)*4n=2時(shí)，addr(Ai1,i2)=a+(i2-1)*d1*4+(i1-1)*4addr(A

26、i1,i2,in)=?第26頁/共30頁第二十六頁，共31頁。n n維數(shù)組元素的地址維數(shù)組元素的地址(dzh)(dzh)計(jì)算計(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其中(qzhng)：c=dn-1*dn-2*dn-3*d1+dn-2*dn-3*dn-4*d1+*dn-3

27、*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 第27頁/共30頁第二十七頁，共31頁。n n維數(shù)組元素維數(shù)組元素(yun s)(yun s)的地址計(jì)算（續(xù)的地址計(jì)算（續(xù)1 1）c=(.(dn-1+1)*dn-2+1)*dn-3.+1)*d1+1 v=(.(in*dn-1+in-1)*dn-2+