編譯原理復(fù)習(xí)及典型題解

《編譯原理復(fù)習(xí)及典型題解》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理復(fù)習(xí)及典型題解（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,a,單擊此處編輯母版文本樣式,a,第二級(jí),a,第三級(jí),a,第四級(jí),a,第五級(jí),*,合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院軟件所,編譯原理,復(fù)習(xí)及典型題解,一、單選題,1,文法所描述的語(yǔ)言是,的集合。,A.,文法的字匯表,V,中符號(hào)組成的符號(hào)串,B.,文法的字匯表,V,中終結(jié)符號(hào)組成的符號(hào)串,C.,由文法開始符推導(dǎo)的符號(hào)串,D.,由文法開始符推導(dǎo)的終結(jié)符號(hào)串,D,2,生成能被,5,整除的正整數(shù)的文法,GZ,是,_,。,A.G,Z,:ZAC,ABA|B,B0|1|2|,|9,C0|5,B.G,Z,:ZAC,ABA|,B0|1|2|,|9,C0|5,C.,GZ,：,ZDA0|A5,

2、，,ABA|,，,B0|D,，,D1|2|,|9,D.G,Z,：,ZAC|C,ABA|B,B0|1|2|,|9,C0|5,C,3,符號(hào)串,ab,1,b,2,是文法,GA,：,AaB,BbB|b,的句子，該句子的句柄是,_,。,A.b,1,B.b,2,C.a D.b,1,b,2,A,a,解釋：,B,b,1,B,b,2,B,4,LL(1),文法中第一個(gè),L,表示,_,。,A.,最左推導(dǎo),B.,最左歸約,C.,從左到右識(shí)別輸入串,D.,規(guī)范歸約,C,5,對(duì)于,LR(0),分析法，語(yǔ)法分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型,_,的,DFA,狀態(tài)。,A,前綴,B.,活前綴,C.LR(0),項(xiàng)目,D.,句柄,B

3、,6,算符文法是指,的文法。,沒有形如,U.VW.,的規(guī)則（,U,，,V,，,W,V,N,）,V,T,中任意兩個(gè)符號(hào)之間至多存在一種算符優(yōu)先關(guān)系,沒有相同右部的規(guī)則,沒有形如,U,的規(guī)則,A.B.,和,C.,、和,D.,、和,A,7,下述語(yǔ)句類中，,_,在編譯階段通常不產(chǎn)生可執(zhí)行代碼。,A.,變量說(shuō)明語(yǔ)句,B.,流程控制語(yǔ)句,C.,輸入輸出語(yǔ)句,D.,賦值語(yǔ)句,A,8,在編譯程序采用的優(yōu)化方法中，,是在循環(huán)語(yǔ)句范圍內(nèi)進(jìn)行的。,合并已知常量 刪除多余運(yùn)算 刪除歸納變量 運(yùn)算強(qiáng)度削弱 代碼外提,A.B.C.D.,D,9,程序的基本塊是指,_,。,A.,不含無(wú)條件轉(zhuǎn)移語(yǔ)句的程序段,B.,不含條件轉(zhuǎn)移

4、語(yǔ)句的程序段,C.,不含停機(jī)的語(yǔ)句程序段,D.,僅含有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句的順序程序段,D,二、,多選題,1,符號(hào)串,dbb,是給定文法,GA,：,AdBC,，,BaB,|,，,CbC|b,的句子，試問其活前綴包括,。,A.B.d C.db D.,dbb,2,已知字母表,=,a,，,b,下列,_,是字母表,上的正規(guī)式。,A.,ab,+,a,B.,abc|b,*,C.(,a|b,),*,D.,A,、,B,注解：,符號(hào)串,dbb,可歸約前綴為,d,。,C,、,D,3,常見的自底而上語(yǔ)法分析方法有,。,A.,遞歸下降分析,B.,算符優(yōu)先分析,C.LL(1),預(yù)測(cè)分析,D.LR,分析,B,、,D

5、,4,一個(gè)文法是,LR(0),文法一定也是,。,A.SLR(1),文法,B.LR(1),文法,C.LALR(1),文法,D.,二義文法,A,、,B,、,C,注解：,S,LR(0),S,SLR,(,1,),S,LALR,(,1,),S,LR,(,1,),1,設(shè),A,是符號(hào)串集，則,A,0,。,（）,2,在形式語(yǔ)言中，最右推導(dǎo)的逆過程稱為規(guī)范歸約。（）,3,一個(gè)語(yǔ)言的文法是唯一的。（）,4,句型的每個(gè)直接短語(yǔ)都是某規(guī)則的右部。（）,5,如果語(yǔ)言的文法是二義性，則該語(yǔ)言也是二義性的。（）,6,任何正規(guī)文法都是上下文無(wú)關(guān)文法。（）,7,符號(hào)表的主要作用是輔助語(yǔ)義分析和代碼生成。（）,三、,判斷題,1,

6、構(gòu)造一個(gè)高級(jí)語(yǔ)言的詞法分析程序的基本技術(shù)線路是什么？,四、,簡(jiǎn)述題,簡(jiǎn)答：,依據(jù)給定的源語(yǔ)言之單詞集，設(shè)計(jì)其正規(guī)文法或正規(guī)式，之后等價(jià)地轉(zhuǎn)換成非確定有窮自動(dòng)機(jī)，再通過子集法將其確定化，最終將確定有窮自動(dòng)機(jī)最小化，最后依據(jù)最小化的確定有窮自動(dòng)機(jī)，設(shè)計(jì)詞法分析程序。,五、,填空題,1,編譯程序是一種翻譯程序，它將用戶用高級(jí)語(yǔ)言編寫的,_,翻譯成等價(jià)的,_,的目標(biāo)程序。,2,有這樣一個(gè)推導(dǎo)過程，其每一步推導(dǎo)都是對(duì)符號(hào)串中最右的非終結(jié)符進(jìn)行替換，我們把這種推導(dǎo)過程稱為,_,。,3,屬性文法中的屬性分為綜合屬性和,_,兩種。,源程序,匯編語(yǔ)言或機(jī)器語(yǔ)言,最右推導(dǎo)（或規(guī)范推導(dǎo)）,繼承屬性,4,已知文法,G

7、A,：,A,(,B,),|a|,，,B,B,，,A|A,，該文法的開始符號(hào)是,_,，非終結(jié)符號(hào)集合為,_,，終結(jié)符號(hào)集合為,_,。,5,自下而上的語(yǔ)法分析方法的基本思想是從待識(shí)別的輸入串開始逐步,_,到文法的,_,。,6,已知文法,GS,：,SAB,A,aAb,|,c,B,aBb,|d,，則對(duì)于非終結(jié)符,A,，,FOLLOW(A)=_,。,A,A,B,(,),a,歸約,開始符,a,b,d,注解：,FOLLOW,可以采用依據(jù)定義直接計(jì)算，或依據(jù)教材所給算法計(jì)算。,13,六、,解答題,1.,已知文法,GS,：,S*A,，,A*0A1,。,(1),求文法,G,非終結(jié)符的,FIRSTVT,集和,LAS

8、TVT,集；,(2),構(gòu)造文法,G,算符優(yōu)先關(guān)系分析表，并判斷,G,是否為算符優(yōu)先文法。,解：,（,1,）計(jì)算,FIRSTVT,集和,LASTVT,集,FIRSTVT,(,S,)=*,LASTVT,(,S,)=*,1,FIRSTVT,(,A,)=0,*,LASTVT,(,A,)=1,*,注解：,FIRSTVT,集和,LASTVT,集,可以采用依 據(jù)定義直接計(jì)算，或依據(jù)教材所給算法計(jì)算。,顯然，文法,G,是,OG,文法、沒有空規(guī)則、,任何兩個(gè)終結(jié)符之間至多存在一種算符優(yōu)先關(guān)系。所以文法,G,是算符優(yōu)先文法。,(2),對(duì)于,S,*,A,，,FIRSTVT,(,A,),，,有：*,0,，*,對(duì)于,A

9、,0A1,，,有：,0 1,對(duì)于,A,0A1,，,FIRSTVT,(,A,),，有：,0,0,，,0,*,對(duì)于,A,0A1,，,LASTVT,(,A,),，有：,1,1,，*,1,FIRSTVT,(,A,)=0,*,LASTVT,(,A,)=1,*,構(gòu)造文法,G,算符優(yōu)先關(guān)系分析表如下。,2.,試設(shè)計(jì)文法描述語(yǔ)言,L=0,n,1,2n+1,|n,1,。,解：,G(S):S 0S111,3.,已知文法,GS,：,S,AB,，,A,aAb,|,ab,，,B,Bc,|,，試寫出該文法描述的語(yǔ)言。,解：,L(G(S),a,n,b,n,c,m,n1,m0,4.,將賦值語(yǔ)句,a,:,=b*,(,c+d,)

10、,翻譯成四元式。,解：,(+,，,c,，,d,，,T,1,),(*,，,b,，,T,1,，,T,2,),(:=,，,T,2,，,a),5,構(gòu)造正規(guī)式,R,0,(,10|01,),*,0,的,DFA M,。,解：,(1),根據(jù),正規(guī)式到轉(zhuǎn)換,NFA,方法，構(gòu)造,NFA M1,(2),根據(jù),NFA,到,DFA,轉(zhuǎn)換,方法，構(gòu)造,DFA M,0,0,X,A,C,B,Y,0,0,D,E,1,1,A,B,C,X,E,Y,D,C,B,0,0,1,1,0,1,0,6,給定文法,GS,：,S,a,S,b,|,試判斷,GS,是否為,SLR,(,1,),文法。,解：,改寫文法為,G,S,:,G,S,:,(0),S,S,(1),S,a,S,b,(2),S,構(gòu)造識(shí)別,LR(0),活前綴,DFA,S,S,S,aSb,S,Sa,Sb,S,aSb,S,S,S,SaS,b,SaSb,S,a,S,b,a,I,0,I,1,I,2,I,3,I,4,follow(s,),#,b,I,0,:,afollow(s),I,2,:,afollow(s),故,GS,是,SLR,(,1,),文法,