《編譯原理》作業(yè)與試題講解.ppt

《《編譯原理》作業(yè)與試題講解.ppt》由會員分享，可在線閱讀，更多相關(guān)《《編譯原理》作業(yè)與試題講解.ppt（22頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1,編譯原理作業(yè)與試題講解,黃岡師范學(xué)院計科院基礎(chǔ)理論教研室張瑞紅,2,2.4寫出下述語言的正規(guī)式描述,（1）由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有01串采用算法解決：首先構(gòu)造出識別偶數(shù)個0和奇數(shù)個1的自動機(jī)，然后使用自動機(jī)到正則表達(dá)式的算法求解。具體步驟參考《自動機(jī)理論、語言和計算導(dǎo)論》。,((00+01(11)*10)*(1+01(11)*0)(0(11)*0)*(1+0(11)*10))*(00+01(11)*10)*(1+01(11)*0)(0(11)*0)*,JFLAP,,注：JFLAP中的“或”用“+”表示,3,2.4寫出下述語言的正規(guī)式描述,（1）由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有01串另一種思路：先寫出偶數(shù)個0和偶數(shù)個1的正則表達(dá)式A，在此基礎(chǔ)上，使用A、0、1構(gòu)造出偶數(shù)個0和奇數(shù)個1的正則表達(dá)式。A=((00+11)+(10+01)(00+11)*(10+01))*,A1A+A0A1A0A,,4,2.4寫出下述語言的正規(guī)式描述,（1）由偶數(shù)個0和奇數(shù)個1構(gòu)成的所有01串另一種思路：先寫出偶數(shù)個0和偶數(shù)個1的正則表達(dá)式A，在此基礎(chǔ)上，使用A、0、1構(gòu)造出偶數(shù)個0和奇數(shù)個1的正則表達(dá)式。A=((00+11)+(10+01)(00+11)*(10+01))*,,1A+0A(10+01)A,若是1開頭，則再加偶0和偶1即得結(jié)果;若是0開頭，則討論0A后可跟：跟00、11，則等價于0A；跟01、10，則是0A(01+10)，已是偶0奇1，則再加偶0和偶1即得結(jié)果,5,2.4寫出下述語言的正規(guī)式描述,（2）所有不含子串011的01串思路一：3種狀態(tài)：只接收了1，接收了0，接收了01思路二：接收011的RE->DFA->不接收011的DFA->RE,接收011的DFA,不接收011的DFA,x,6,2.4寫出下述語言的正規(guī)式描述,（2）所有不含子串011的01串,注：JFLAP中的“ε”用“λ”表示,7,2.4寫出下述語言的正規(guī)式描述,（3）每個a后面至少緊隨兩個b的ab串思路：abb應(yīng)該為一個整體，和b進(jìn)行組合，串的形式如下bbbbbabbabbbbbbabbbbbbb......(b*|abb)*(b|abb)*,8,2.4寫出下述語言的正規(guī)式描述,（4）C的形如/*…*/的注釋。其中…代表不含*/的字符串思路：接收*/的DFA->不接收*/的DFA->RE接收*/的DFA中有3個狀態(tài)：沒有接收*；接收了*；接收了*/,([^*]|**[^*/])***/*([^*]|**[^*/])****/,x,9,2.9用自然語言給出下述正規(guī)式所描述的語言，并構(gòu)造它們的最小DFA10*1(0|1)*011(0|1)*,所謂用自然語言描述：即解釋字符串的性質(zhì)練習(xí)目的：鍛煉思維推理能力歸納：由特殊到一般的推理，如根據(jù)要求寫正規(guī)式演繹：由一般到特殊的推理，如根據(jù)正規(guī)式生成字符串解：10*1：首尾是1中間有零或若干個0的01串(0|1)*011(0|1)*：至少含一個011的01串,10,2.10,有一NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中S為初態(tài)，D為終態(tài),求出它的最小DFA用正規(guī)式描述DFA所接受的語言,問題：根據(jù)DFA寫出對應(yīng)的正規(guī)式，通常的考慮和步驟是什么？,正規(guī)式、DFA是從兩個不同的側(cè)面表示一個集合(即正規(guī)集)。所以，根本的方法是把正規(guī)集作為橋梁，先分析清楚DFA識別出的是一個什么集合，然后再設(shè)計此集合的正規(guī)式。(當(dāng)然也可以采用機(jī)械化的算法來實(shí)現(xiàn)，不過結(jié)果往往很復(fù)雜，難以理解),11,2.10,該DFA從初態(tài)到終態(tài)有三條路徑：b|c|a(a|c)*b，而且是這三條路徑的至少一次重復(fù)，故正規(guī)式為：(b|c|a(a|c)*b)+,12,3.6設(shè)字母表∑={0,1}，設(shè)計下列語言的文法。對于正規(guī)語言，可用正規(guī)式表示。（2）0和1個數(shù)相等的字符串；（3）0和1個數(shù)不相等的字符串；（2）（3）均不能用正規(guī)式表示，為什么？（鴿巢原理反證）（2）思路：S包含0、1個數(shù)相等，0、1相等的最小項(xiàng)是ε、01、10，則給它們加上S，則0、1個數(shù)仍相等S->S0S1S|S1S0S|ε消除直接左遞歸S->S’S’->0S1SS’|1S0SS’|ε即是S->0S1S|1S0S|ε這些文法都等價,13,3.6設(shè)字母表∑={0,1}，設(shè)計下列語言的文法。對于正規(guī)語言，可用正規(guī)式表示。（2）0和1個數(shù)相等的字符串；（3）0和1個數(shù)不相等的字符串；（3）思路：將0、1個數(shù)相等的字符串加上若干個0或1即可S->0S1S|1S0S|ε加0：A->0A1A|1A0A|0A|ε加1：B->0B1B|1B0B|1B|εS->A|B?不能推導(dǎo)出ε，結(jié)果應(yīng)該為S->A0A|B1B,14,3.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)項(xiàng)目集的識別活前綴的DFA（2）指出DFA中所有含有沖突的項(xiàng)目集，并說明這些沖突可以用SLR(1)方法解決；（3）構(gòu)造文法G3.4的SLR(1)分析表（4）用分析表對句子-id+id*id和-(id+id)*id進(jìn)行分析（以格局變化的方式）（5）根據(jù)（4）的分析給出-id+id*id的分析樹和剪句柄的過程,15,構(gòu)造SLR（1）分析表的方法：,1．可移進(jìn)項(xiàng)直接從DFA上看：action[I,a]:=sjgoto[I,A]:=k2．可歸約項(xiàng)分兩步走：若在I狀態(tài)中有[A→α.]，首先計算：FOLLOW(A),然后填寫：action[I,b]:=Ri其中：b∈FOLLOW(A)且A→α是第i個產(chǎn)生式。,,16,3.19假設(shè)所討論的文法是非二義的，說明為什么在規(guī)范歸約中，非終結(jié)符絕不會出現(xiàn)在句柄的右邊。解：（解題思路：用反證的方法，假設(shè)在規(guī)范歸約中句柄右邊有非終結(jié)符，則推出矛盾）假設(shè)在規(guī)范歸約中有句型“...α...A...”，其中α是句柄，A非終結(jié)符。根據(jù)規(guī)范歸約定義，A必定是由句型中相對于A的短語歸約而來。而A的短語在α右邊（即先歸約了右邊的短語），與規(guī)范歸約矛盾。得證。請進(jìn)一步思考：為什么假設(shè)文法是非二義的？,17,4.4假定下述程序分別采用值調(diào)用，引用調(diào)用，復(fù)寫-恢復(fù)和換名調(diào)用，請給出它們的打印結(jié)果。programmain(inputoutput);procedurep(x,y,z);beginy:=y+1;z:=z+xend;begina:=2;b:=3;p(a+b,a,a);printaend;兩種解題的思路：1.把自己當(dāng)作計算機(jī)，按照參數(shù)傳遞的實(shí)現(xiàn)方式“運(yùn)行”一遍程序，得出結(jié)果；2.找臺機(jī)子把程序敲進(jìn)去試試（輔助手段）表達(dá)式a+b如何可以作為復(fù)寫-恢復(fù)的實(shí)參？解決方案：忽略返回值問題（因?yàn)閺?fù)寫-恢復(fù)一般要求形參要有左值）考試中不會有這樣很困惑的問題！,18,procedureAisprocedureBisProcedureDisx:character;begin……endD;begin……endB;procedureCisx:integer;procedureEisy:integer;begin……endE;procedureFisy:float;begin……endF;begin……endD;begin……endA;,5.5有一過程A如下所示。采用靜態(tài)作用域、最近嵌套原則，設(shè)A是第0層的過程。,19,（4）若一個可能的程序運(yùn)行控制流是A-C-E-F-B,試給出每次調(diào)用和返回時的控制棧中各活動記錄的可確定內(nèi)容和顯示表的變化；（5）分別給出C調(diào)用E的調(diào)用序列和從E返回的返回序列。解：（4）若一個可能的程序運(yùn)行控制流是A-C-E-F-B，給出控制棧中的內(nèi)容和控制鏈與訪問鏈的指向。靜態(tài)嵌套結(jié)構(gòu)、活動棧、以及控制鏈與訪問鏈：,,20,試題舉例一、簡答題,1.1（2分）有哪些方法可以去除文法的二義性。1.2（2分）寫出-((a+b)*c)+d的后綴式。1.5（4分）試證明正規(guī)式(ab)*a與a(ba)*是等價的。,1.1（1）改寫文法（2）規(guī)定文法符號的優(yōu)先級和結(jié)合性1.2ab+c*@d+（或ab+c*-d+）1.5證明：考慮L((ab)*a)中的任意一個串a(chǎn)babab...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次也成立）。,21,二、填空題,2.2（6分）編譯程序的基本組成有：詞法分析、、、中間代碼生成、、、和。2.3（1分）正規(guī)式r和s等價說明相同。2.4（2分）不含子串baa的所有a、b符號串的正規(guī)式是。2.9（4分）已知文法G定義如下：S→eT|RTT→DR|εR→dR|εD→a|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.3r和s表示的正規(guī)集2.4a*(b|ba)*2.9FIRST(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，ε}。,22,三、計算題（3.3）,3.3（13分）已知一個NFA如圖。(a)(4分)用自然語言簡要敘述該自動機(jī)所識別的語言的特點(diǎn)，列舉兩個它可識別的串。(b)（3分）寫出與該自動機(jī)等價的正規(guī)式r。(c)（6分）用子集法構(gòu)造識別r的最小DFA。,