編譯原理與技術(shù)模擬試題一

編譯原理與技術(shù)模擬試題一編譯原理與技術(shù)模擬試題一編譯原理與技術(shù)模擬試題一xxx公司編譯原理與技術(shù)模擬試題一文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度模擬試題一一、填空題（10分）從程序運(yùn)行的角度看，編譯程序和解釋程序的主要區(qū)別是：。編譯程序的基本組成有：詞法分析、、、中間代碼生成、代碼優(yōu)化、、和。正規(guī)式r和s等價(jià)說(shuō)明相同。不含子串baa的所有a、b符號(hào)串的正規(guī)式是。規(guī)范規(guī)約（最左歸約）和是互逆的兩個(gè)過(guò)程。在賦值語(yǔ)句“x=y+2”中，常量2是右值，變量x提供，變量y提供二、選擇題（20分）文法的終結(jié)符集和非終結(jié)符集的交集一定為空。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是，它只能出現(xiàn)在產(chǎn)生式的右部。A.終結(jié)符 B.非終結(jié)符 C.產(chǎn)生式 D.起始符號(hào)為數(shù)組聲明a:array[1..4,2..3]中a分配的存儲(chǔ)空間的首地址為base_a，且每個(gè)數(shù)組元素占據(jù)一個(gè)存儲(chǔ)單元。若以行為主存放，數(shù)組元素a[3,3]在存儲(chǔ)空間中相對(duì)base_a的偏移量是。A.2 B.3 C.5 D.6主流程序設(shè)計(jì)語(yǔ)言（如Pascal、C++等）均采用和最近嵌套原則，為此類語(yǔ)言的編譯器設(shè)計(jì)的符號(hào)表應(yīng)該具有后進(jìn)先出的性質(zhì)。A.靜態(tài)作用域 B.動(dòng)態(tài)作用域 C.靜態(tài)綁定 D.動(dòng)態(tài)綁定參數(shù)傳遞中，值調(diào)用傳遞的是實(shí)參的右值（或值），引用調(diào)用傳遞的是實(shí)參的。A.右值 B.左值 C.名字 D.結(jié)果靜態(tài)數(shù)據(jù)區(qū)用于存放一對(duì)一的綁定、且編譯時(shí)就可確定存儲(chǔ)空間大小的數(shù)據(jù)；用于存放一對(duì)多的綁定且與活動(dòng)同生存期的數(shù)據(jù)。A.棧 B.堆 C.數(shù)組 D.鏈表LR(1)分析法中，L的含義是，R的含義是最右推導(dǎo)的逆，1的含義是確定下一個(gè)動(dòng)作向前看1個(gè)終結(jié)符。A.最左推導(dǎo) B.自左向右掃描輸入 C. 最左歸約D.自右向左掃描輸入 改寫文法或者規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性是的基本方法。A.代碼生成 B.語(yǔ)法分析 C.語(yǔ)義分析 D.去除文法的二義性 是正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中的元素。A.135202cde B.1202c C.302cde D.52c表達(dá)式“(a+b)*(c-d)”的后綴表示為。A.ab+cd-* B.abcd+-* C.ab+*cd- D.abcd*+-若程序P經(jīng)編譯并鏈接后可執(zhí)行，則。A.P是正確的程序 B.P中沒(méi)有語(yǔ)法錯(cuò)誤 C.P中沒(méi)有邏輯錯(cuò)誤 D.P在運(yùn)行中不會(huì)出錯(cuò)三、簡(jiǎn)答題（30分）（6分）有文法G：S→aSbS|bSaS|ε和G產(chǎn)生的一個(gè)句子ababab。(a)該文法是二義的嗎為什么(b)該文法產(chǎn)生的語(yǔ)言L(G)=？（10分）有文法G：S→(L)|a,L→L,S|S。(a)說(shuō)明G不是LL(1)文法；(b)將G改寫為L(zhǎng)L(1)文法。（5分）簡(jiǎn)述過(guò)程的活動(dòng)和活動(dòng)的生存期。（9分）給出語(yǔ)句while(a<b)doif(c<d)thenx:=y+z的中間代碼序列。四、綜合題（40分）（15分）有C++程序如下所示：#include<>intf(intn){ if(n<2)returnn; returnf(n-1)+f(n-2);}voidmain(){inta=4;cout<<f(a)<<endl;}(a)（5分）畫出程序運(yùn)行時(shí)的活動(dòng)樹；(b)（3分）給出程序的運(yùn)行結(jié)果；(c)（5分）若控制棧從左向右增長(zhǎng)（最右邊是棧頂），請(qǐng)問(wèn)(main,f(4),f(1))是不是一個(gè)可能的控制棧狀態(tài)為什么(d)（2分）為C語(yǔ)言設(shè)計(jì)的棧式存儲(chǔ)分配策略中，是否需要display為什么（10分）某表達(dá)式的語(yǔ)法制導(dǎo)翻譯方案如下(運(yùn)算符-,*,+的優(yōu)先級(jí)依次遞減)。（1）M→ε { :=nextstat;}（2）E→E1+ME2{backpatch，；:=merge,;:=;}（3）E→E1*ME2{backpatch,；:=merge(,;:=;}（4）E→-E1 {:=;:=;}（5）E→(E1) {:=;:=;}（6）E→id {:=mkchain(nextstat);:=mkchain(nextstat+1);emit('if''goto_');emit('goto_');}(a)（5分）給出表達(dá)式p*(-a)+b的注釋分析樹；(b)（5分）根據(jù)上述翻譯方案，生成表達(dá)式p*(-a)+b的三地址碼序列。（15分）已知一個(gè)NFA如下圖所示。(a)(5分)用自然語(yǔ)言簡(jiǎn)要敘述該自動(dòng)機(jī)所識(shí)別的語(yǔ)言的特點(diǎn)，列舉兩個(gè)它可識(shí)別的串。(b)(2分)寫出與該自動(dòng)機(jī)等價(jià)的正規(guī)式r。(c)（8分）用子集法構(gòu)造識(shí)別r的最小DFA。

模擬試題一參考答案一、填空題（10分）從程序運(yùn)行的角度看，編譯程序和解釋程序的主要區(qū)別是：運(yùn)行目標(biāo)程序時(shí)控制權(quán)在解釋程序而不在目標(biāo)程序，或者是否生成目標(biāo)代碼，或者是否與機(jī)器相關(guān)。編譯程序的基本組成有：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、表格管理和出錯(cuò)處理。正規(guī)式r和s等價(jià)說(shuō)明r和s表示的正規(guī)集相同。不含子串baa的所有a、b符號(hào)串的正規(guī)式是a*(b|ba)*。規(guī)范規(guī)約（最左歸約）和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。在賦值語(yǔ)句“x=y+2”中，常量2是右值，變量x提供左值二、選擇題（20分）文法的終結(jié)符集和非終結(jié)符集的交集一定為空。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是A，它只能出現(xiàn)在產(chǎn)生式的右部。A.終結(jié)符 B.非終結(jié)符 C.產(chǎn)生式 D.起始符號(hào)為數(shù)組聲明a:array[1..4,2..3]中a分配的存儲(chǔ)空間的首地址為base_a，且每個(gè)數(shù)組元素占據(jù)一個(gè)存儲(chǔ)單元。若以行為主存放，數(shù)組元素a[3,3]在存儲(chǔ)空間中相對(duì)base_a的偏移量是C。A.2 B.3 C.5 D.6主流程序設(shè)計(jì)語(yǔ)言（如Pascal、C++等）均采用A和最近嵌套原則，為此類語(yǔ)言的編譯器設(shè)計(jì)的符號(hào)表應(yīng)該具有后進(jìn)先出的性質(zhì)。A.靜態(tài)作用域 B.動(dòng)態(tài)作用域 C.靜態(tài)綁定 D.動(dòng)態(tài)綁定參數(shù)傳遞中，值調(diào)用傳遞的是實(shí)參的右值（或值），引用調(diào)用傳遞的是實(shí)參的B。A.右值 B.左值 C.名字 D.結(jié)果靜態(tài)數(shù)據(jù)區(qū)用于存放一對(duì)一的綁定、且編譯時(shí)就可確定存儲(chǔ)空間大小的數(shù)據(jù)；A用于存放一對(duì)多的綁定且與活動(dòng)同生存期的數(shù)據(jù)。A.棧 B.堆 C.數(shù)組 D.鏈表LR(1)分析法中，L的含義是B，R的含義是最右推導(dǎo)的逆，1的含義是確定下一個(gè)動(dòng)作向前看1個(gè)終結(jié)符。A.最左推導(dǎo) B.自左向右掃描輸入 C. 最左歸約D.自右向左掃描輸入 改寫文法或者規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性是D的基本方法。A.代碼生成 B.語(yǔ)法分析 C.語(yǔ)義分析 D.去除文法的二義性 B是正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中的元素。A.135202cde B.1202c C.302cde D.52c表達(dá)式“(a+b)*(c-d)”的后綴表示為A。A.ab+cd-* B.abcd+-* C.ab+*cd- D.abcd*+-若程序P經(jīng)編譯并鏈接后可執(zhí)行，則B。A.P是正確的程序 B.P中沒(méi)有語(yǔ)法錯(cuò)誤 C.P中沒(méi)有邏輯錯(cuò)誤 D.P在運(yùn)行中不會(huì)出錯(cuò)三、簡(jiǎn)答題（30分）（6分）有文法G：S→aSbS|bSaS|ε和G產(chǎn)生的一個(gè)句子ababab。(a)該文法是二義的嗎為什么(b)該文法產(chǎn)生的語(yǔ)言L(G)=？解：(a)是二義文法，對(duì)句子ababab存在兩個(gè)分析樹如下所示：(b)L(G)={a,b個(gè)數(shù)相等的a,b串}（10分）有文法G：S→(L)|a,L→L,S|S。(a)說(shuō)明G不是LL(1)文法；(b)將G改寫為L(zhǎng)L(1)文法。解：(a)因?yàn)镕IRST(L,S)∩FIRST(S)={a}，即非終結(jié)符L產(chǎn)生式的兩個(gè)候選項(xiàng)有公共左因子，所以G不是LL(1)文法。(b)G中有左遞歸，消除左遞歸如下：1．將沒(méi)有直接左遞歸的S代入有直接左遞歸的L產(chǎn)生式，得：L→L,(L)|L,a|(L)|a （或：L→L,S|(L)|a）消除直接左遞歸，得：L→(L)L'|aL' L'→,(L)L'|,aL'|ε最后的消除左遞歸的文法G'：G： S→(L)|aL→(L)L'|aL'L'→,(L)L'|,aL'|ε （或：L'→,SL'|ε）（5分）簡(jiǎn)述過(guò)程的活動(dòng)和活動(dòng)的生存期。解：過(guò)程的一次運(yùn)行稱為過(guò)程的一次活動(dòng)；活動(dòng)的生存期是指從進(jìn)入活動(dòng)的第一條指令開(kāi)始執(zhí)行，到離開(kāi)活動(dòng)的最后一條指令執(zhí)行完成的時(shí)間，其中包括被調(diào)用過(guò)程活動(dòng)的生存期。（9分）給出語(yǔ)句while(a<b)doif(c<d)thenx:=y+z的中間代碼序列。解：程序流圖：中間代碼：101(j<,a,b,103)102(j,-,-,108)103(j<,c,d,105)104(j,-,-,101)105(+,y,z,t1)106(:=,t1,-,x)107(j,-,-,101)108...或： 101ifa<bgoto103 102goto108 103ifc<dgoto105 104goto101 105t1:=y+z 106x:=t1 107goto101 108...四、綜合題（40分）（15分）有C++程序如下所示：#include<>intf(intn){ if(n<2)returnn; returnf(n-1)+f(n-2);}voidmain(){inta=4;cout<<f(a)<<endl;}(a)（5分）畫出程序運(yùn)行時(shí)的活動(dòng)樹；(b)（3分）給出程序的運(yùn)行結(jié)果；(c)（5分）若控制棧從左向右增長(zhǎng)（最右邊是棧頂），請(qǐng)問(wèn)(main,f(4),f(1))是不是一個(gè)可能的控制棧狀態(tài)為什么(d)（2分）為C語(yǔ)言設(shè)計(jì)的棧式存儲(chǔ)分配策略中，是否需要display為什么解：(a)活動(dòng)樹如下：(b)程序的運(yùn)行結(jié)果為：3(c)不是一個(gè)可能的控制棧狀態(tài)，因?yàn)閒(4)不能直接調(diào)用f(1)。從活動(dòng)樹也可以看出，f(4)所在的任何一條路徑上，f(4)和f(1)不相鄰。(d)不需要，因?yàn)閐isplay是用于訪問(wèn)非本地?cái)?shù)據(jù)的。而C程序中不允許過(guò)程的嵌套定義，故C程序中的變量或者是全程的，或者是本地的，沒(méi)有所謂的非本地?cái)?shù)據(jù)。（10分）某表達(dá)式的語(yǔ)法制導(dǎo)翻譯方案如下(運(yùn)算符-,*,+的優(yōu)先級(jí)依次遞減)。（1）M→ε { :=nextstat;}（2）E→E1+ME2{backpatch，；:=merge,;:=;}（3）E→E1*ME2{backpatch,；:=merge(,;:=;}（4）E→-E1 {:=;:=;}（5）E→(E1) {:=;:=;}（6）E→id {:=mkchain(nextstat);:=mkchain(nextstat+1);emit('if''goto_');emit('goto_');}(a)（5分）給出表達(dá)式p*(-a)+b的注釋分析樹；(b)（5分）根據(jù)上述翻譯方案，生成表達(dá)式p*(-a)+b的三地址碼序列。解：（a）注釋分析樹如下：(b)三地址碼序列如下：(1)ifpgoto3(2)goto5(3)ifagoto5(4)goto-(5)ifbgoto-(6)goto-（15分）已知一個(gè)NFA如下圖所示。(a)(