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

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

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