03-編譯原理課程測試第三套卷(附解析)-編譯原理試題-中國科技大學(xué)

編譯原理課程測試第三套卷（附解析）1．（15分）(a)字母表={(,)}上的語言{(),(()()),((())),()()()()()}是不是正規(guī)語言？為什么？(b)正規(guī)式(0|1)*和((|0)1*)*是否等價(jià)，說明理由。2．（15分）接受文法 SAa|bAc|dc|bda AdS’S’.SS.AaS.bAcS.dcS.bdaA.dI0Sb.AcSb.daA.dI3daSd.cAd.I4AS’S.I1SSA.aI2ASAa.I5bSbA.cI6dSdc.I8Sbd.aAd.I7cSbAc.I9Sbda.I10ca活前綴的DFA見下圖。請根據(jù)這個(gè)DFA來構(gòu)造該文法的SLR(1)分析表，并說明該文法為什么不是SLR(1)文法。3．（10分）現(xiàn)有字母表={a}，寫一個(gè)和正規(guī)式a*等價(jià)的上下文無關(guān)文法，要求所寫的文法既不是LR文法，也不是二義文法。4．（20分） (a)下面的文法定義語言L={anbncm|m,n1}。寫一個(gè)語法制導(dǎo)定義，其語義規(guī)則的作用是：對不屬于語言L的子集L1={anbncn|n1}的句子，打印出錯(cuò)信息。 SDC DaDb|ab CCc|c (b)語句的文法如下： Sid:=E|ifEthenS|whileEdoS|beginS;Send|break寫一個(gè)翻譯方案，其語義動(dòng)作的作用是：若發(fā)現(xiàn)break不是出現(xiàn)在循環(huán)語句中，及時(shí)報(bào)告錯(cuò)誤。5．（5分）C程序設(shè)計(jì)的教材上說，可以用兩種形式表示字符串：其一是用字符數(shù)組存放一個(gè)字符串，另一種是用字符指針指向一個(gè)字符串。教材上同時(shí)介紹了這兩種形式的很多共同點(diǎn)和不同點(diǎn)，但是有一種可能的區(qū)別沒有介紹。下面是一個(gè)包含這兩種形式的C程序：charc1[]=“good!”;char*c2=“good!”;main(){c1[0]=‘G’;printf(“c1=%s\n”,c1);c2[0]=‘G’;printf(“c2=%s\n”,c2);}該程序在X86/Linux機(jī)器上運(yùn)行時(shí)的信息如下： c1=Good! Segmentationfault(coredumped)請問，出現(xiàn)Segmentationfault的原因是什么？6．（15分）下面是一個(gè)C語言程序：longf1(i)longi;{ return(i*10);}longf2(longi){ return(i*10);}main(){ printf(“f1=%d,f2=%d\n”,f1(10.0),f2(10.0));}其中函數(shù)f1和f2僅形式參數(shù)的描述方式不一樣。該程序在X86/Linux機(jī)器上的運(yùn)行結(jié)果如下： f1=0,f2=100請解釋為什么用同樣的實(shí)在參數(shù)調(diào)用這兩個(gè)函數(shù)的結(jié)果不一樣。7．（10分）下面是一個(gè)C語言程序和在X86/Linux機(jī)器上編譯（未使用優(yōu)化）該程序得到的匯編代碼（為便于理解，略去了和討論本問題無關(guān)的部分，并改動(dòng)了一個(gè)地方）。(a)為什么會(huì)出現(xiàn)一條指令前有多個(gè)標(biāo)號(hào)的情況，如.L2和.L4，還有.L5、.L3和.L1？從控制流語句的中間代碼結(jié)構(gòu)加以解釋。(b)每個(gè)函數(shù)都有這樣的標(biāo)號(hào).L1，它的作用是什么，為什么本函數(shù)沒有引用該標(biāo)號(hào)的地方？main(){ longi,j; if(j) i++; else while(i)j++;}main: pushl%ebp ――將老的基地址指針壓棧 movl%esp,%ebp ――將當(dāng)前棧頂指針作為基地址指針 subl$8,%esp ――為局部變量分配空間 cmpl$0,-8(%ebp) je.L2 incl-4(%ebp) jmp.L3.L2:.L4: cmpl$0,-4(%ebp) jne.L6 jmp.L5.L6: incl-8(%ebp) jmp.L4.L5:.L3:.L1: leave ――和下一條指令一起完成恢復(fù)老的基地址指針，將棧頂 ret ――指針恢復(fù)到調(diào)用前參數(shù)壓棧后的位置，并返回調(diào)用者8．（5分）cc是UNIX系統(tǒng)上C語言編譯命令，l是連接庫函數(shù)的選擇項(xiàng)。兩個(gè)程序員分別編寫了函數(shù)庫libuser1.a和libuser2.a。當(dāng)用命令 cctest.cluser1.aluser2.a編譯時(shí)，報(bào)告有重復(fù)定義的符號(hào)。（備注：庫名中的lib在命令中省略。該命令和命令cctest.clibuser1.alibuser2.a的效果是一致的）。而改用命令 cctest.cluser2.aluser1.a時(shí)，能得到可執(zhí)行程序。試分析原因。9．（5分）根據(jù)教材上所介紹的方法，C++中的對象聲明語句應(yīng)如何翻譯成C語句？如教材圖11.11（舊教材的圖10.11）程序中的Point_center;應(yīng)怎樣翻譯？編譯原理課程測試第三套卷參考答案1． (a)語言{(),(()()),((())),()()()()()}是正規(guī)語言，因?yàn)樵撜Z言只包括有限個(gè)句子，它可以用正規(guī)式定義如下： ()|(()())|((()))|()()()()()(b)我們分析正規(guī)式((|0)1*)*表示的語言。可以看出正規(guī)式(|0)1*描述的語言是集合{,1,11,111,…,0,01,011,0111,…}，它含長度為1的兩個(gè)串0和1。那么，(0|1)*所描述的語言是((|0)1*)*所描述的語言的子集，因?yàn)?0|1)*表示字母表{0,1}上所有串的集合，因此((|0)1*)*所描述的語言不可能再有更多的句子，因而也是表示字母表{0,1}上所有串的集合。2．分析表如下。因?yàn)橛袃商幱幸七M(jìn)－歸約沖突，所以該文法不是SLR(1)文法。注：Fallow(A)={a,c}狀態(tài)狀態(tài)動(dòng)作轉(zhuǎn)移abcd$SA0s3s4121acc2s53s764r5s8,r55r16s97s10,r58r39r210r43．滿足條件的一個(gè)文法如下： SaSa|a|4． (a)語法制導(dǎo)的定義如下： SDC ifD.lengthC.lengththenprint(“error”) Dab D.length:=1 DaD1b D.length:=D1.length+1 Cc C.length:=1 CC1c C.length:=C1(b)翻譯方案如下：S{S.loop:=false}SSid:=ESifEthen{S1.loop:=S.loop}S1SwhileEdo{S1.loop:=true}S1Sbegin{S1.loop:=S.loop}S1;{S2.loop:=S.loop}S2endSbreak{ifnotS.loopthenprint(“error”)}5．c1是字符數(shù)組，c1[]=“good!”看成是對這個(gè)數(shù)組的元素逐個(gè)地賦值。c2是字符指針，它所指向的“good!”看成是一個(gè)字符串常量，常量的值不允許修改，因此編譯器把這個(gè)字符串常量分配在只讀數(shù)據(jù)區(qū)。 當(dāng)執(zhí)行賦值c2[0]=‘G’時(shí)，試圖對只讀數(shù)據(jù)區(qū)賦值，因此報(bào)告錯(cuò)誤。6．歷史上，C語言中有參函數(shù)定義的一般形式是： 類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)列表） 形式參數(shù)聲明對于這種形式的聲明，C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的。如本題中函數(shù)f1的聲明是這種形式。 現(xiàn)在，ANSI新標(biāo)準(zhǔn)允許使用另一種方法聲明形式參數(shù)，即在函數(shù)名后的括號(hào)中列出形式參數(shù)的同時(shí)，聲明形式參數(shù)的類型。本題中函數(shù)f2的聲明是這種形式。C語言編譯器對于這種形式的函數(shù)聲明是要進(jìn)行實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的。 因此，在編譯函數(shù)調(diào)用f2(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成整數(shù)10，并產(chǎn)生將整數(shù)10壓棧的指令。因此函數(shù)調(diào)用f2(10.0)的結(jié)果是100。而在編譯函數(shù)調(diào)用f1(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成雙精度型（參見《編譯原理習(xí)題精選》第5.8題），并產(chǎn)生將該雙精度型數(shù)壓棧的指令。雙精度型數(shù)占8個(gè)字節(jié)。它低地址的4個(gè)字節(jié)看成整數(shù)時(shí)正好是0。因此函數(shù)調(diào)用f1(10.0)的結(jié)果是0（參見/~yiyun上2003年編譯原理試題第7題）。7．(a)條件語句和循環(huán)語句的中間代碼結(jié)構(gòu)如下： if(E)thenS1elseS2 while(E)doS E的代碼 L4: E的代碼 假轉(zhuǎn)L2 真轉(zhuǎn)L6 S1的代碼 轉(zhuǎn)L5 轉(zhuǎn)L3 L6: S的代碼 L2: S2的代碼 轉(zhuǎn)L4 L3: L5:用這種代碼結(jié)構(gòu)，當(dāng)while語句作為條件語句的S2時(shí)，就會(huì)出現(xiàn)題目所給的這種情況。 (b).L1標(biāo)號(hào)定義的入口是返回調(diào)用者時(shí)該執(zhí)行的指令，在函數(shù)內(nèi)部有return語句時(shí)就會(huì)跳轉(zhuǎn)到.L1。8．這是基于下面幾點(diǎn)原因。1．兩個(gè)函數(shù)庫libuser1.a和libuser2.a都定義了某個(gè)函數(shù)或某個(gè)置初值的外部變量，把它簡稱為a。2．test.c引用a。3．test.c還引用libuser2.a的其它某個(gè)函數(shù)或外部變量，把它簡稱為b。在libuser2.a中，a和b在同一個(gè)目標(biāo)文件中。4．在libuser1.a中，含a的那個(gè)目標(biāo)文件不含b。進(jìn)一步的解釋如下。由于test.c引用a和b，用第二種次序連接時(shí)，a和b的定義在libuser2.a都能找到，所以不會(huì)再把libuser1.a中含a定義的目標(biāo)文件連接進(jìn)來。而用第一種次序連接時(shí)，先把libuser1.a中含a定義的目標(biāo)文件連接進(jìn)來，然后還需要把libuser2.a中含b定義的目標(biāo)文件連接進(jìn)來，引起把a(bǔ)