大學(xué)課程《編譯原理》練習(xí)測試題庫

\h大學(xué)課程《編譯原理》練習(xí)測試題庫一、填空若源程序是用高級語言編寫的，目標(biāo)程序是 ，則其翻譯程序稱為編譯程序。詞法分析和語法分析本質(zhì)上都是對源程序的 進(jìn)行分析。如果源語言(編寫源程序的語言)是高級語言而目標(biāo)語言是某計算機(jī)的匯編語言或機(jī)器語言，則這種翻譯程序稱為 。對編譯程序而言，輸入數(shù)據(jù)是 ,輸出結(jié)果是 。 ，是構(gòu)成語言文法的單詞，是語法成分的最小單位。PL／0EBNF，PL／0PASCAL 。由于PL／0編譯程序采用 法分析過程BLOCK是整個編譯過程的核心。用語法圖描述語法規(guī)則的優(yōu)點是 、 。每個非終結(jié)符是一個語法成分，在書寫語言程序時并不出現(xiàn)，它是由 和 、或終結(jié)符串定義的。的目標(biāo)程序為假想棧式計算機(jī)的匯編語言，與具體計算機(jī) 。的編譯程序和目標(biāo)程序的解釋執(zhí)行程序都是用 在配備 的任何機(jī)器上實現(xiàn)。個嵌套及并列的過程或函數(shù)組成調(diào)用 并按用戶程序要求輸入數(shù)據(jù)和輸出運(yùn)行結(jié)果。由于對某些非終結(jié)符可以遞歸定義，這就使得 可用有窮的文法描述。 的任務(wù)是識別由詞法分析給出的單詞符號序列在結(jié)構(gòu)上是否符合給定的文法規(guī)則。PL／0編譯程序的語法分析采用了 。語法分析程序除總控外主要有兩大部分的功能，即 和 .PL／0詞法分程序GETYM是一獨(dú)立過其功能是為 提供單用的是 的基礎(chǔ)，它把輸入的字符串形式的源程序分割成一個個單詞符號。每個過程應(yīng)有過程首部以定義局部于它自己過程的常量變量和過程標(biāo)識符也稱 。詞法分析程序GETSYM將完成的任務(wù)有: ,識別保留字； ,拼數(shù),拼復(fù)合詞,輸出源程序.如果一個PL／0語言的單詞序列在整個語法分析中都能逐個得到匹配直到 ，這時就說所輸入的程序是正確的。若要構(gòu)造程序設(shè)計語言的編譯程序，則首先要對程序設(shè)計語言本身有較為精確的描述。而關(guān)于程序設(shè)計語言的描述，將涉及 、語義和 三個方面。凡是具有某種特殊性質(zhì)的客體的聚合，都可稱為 。如果集合中元素個數(shù)為零即集合中不含有任何元素這樣的集合稱為 記為φ。設(shè)有集合A和B，如果A和B有相同的元素，則稱這兩個集合是 .設(shè)AB為意兩個合由所有于集合A或于集合B元素組的集合叫集A與B的 ．B為任意兩個集合，由所有用于集合A且屬于集合B的元素組成的集合，稱為集合A與B的 .如果一個集合，它能包含我們所要考慮目標(biāo)之內(nèi)的所有元素，則稱此集合為 ，記為E。設(shè)A為一集合，由A的所有子集(包括空集及A本身)所組成的集合，稱為A的 .由兩個按一定次序排列的客體組成的序列，稱為 .設(shè)A和B為任意兩個集合若序偶的第一個成員是集合A的一個元素第二個成員是集合B的一個元素，則所有這樣的序偶組成的集合稱為集合A和B的 .集合X上的關(guān)系R，如對任意x∈X，均有(x，x)∈R，則稱關(guān)系R是 。。在集合X上的關(guān)系R，如果合(x，y)∈R且(y，z)∈R，必有(x，z)∈R，則稱關(guān)系R是 。35.例設(shè)P{（1，2（3，4（2，）}Q=（47（2，9（3，1}則P·Q= 符號串與符號組成順序 ，如符號串a(chǎn)b ba，符號申001也 。假設(shè)G是一個文法，S是文法的開始符號，如果S=>*x,則稱x是 。文法G產(chǎn)生的 該文法描述的語言。39.一個文法G[Z]存在推序列Z=>+·Z·,是 文法，這類文法所產(chǎn)生的句子有 個。40.喬姆斯基把文法分成 類型.四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是 .最右推導(dǎo)常被稱為 。由規(guī)范推導(dǎo)所得的句型稱為 。文法的二義性和語言的二義性是兩個 概念。對于上下文無關(guān)文法， 是句型推導(dǎo)過程的幾何表示。直接短語也稱 .每棵語法樹的葉子組成一個 .每棵子樹的葉子組成一個 .每棵簡單子樹的葉子組成一個 .最左邊簡單子樹的葉子組成 .一個句型的最左直接短語稱為該句型的 。而且推導(dǎo)"=>+"為直接推導(dǎo)"=>"的 。 BNF則是多余的。也稱這種非終結(jié)符為.不出終結(jié)符號串，顯然，所有含有U的規(guī)則是多余的。也稱這種非終結(jié)符為 。L∪{εLε}分別是上下文有關(guān)語言、和正規(guī)語言。GUUSxSUSSU的推導(dǎo)的.文無關(guān)文法G包括四個組成部分依次是： , , , .11文法所描述的語言是 集合。詞法分析器工作的第一步是輸入源程序文本。輸入串一般是放在一個緩沖區(qū)中，這個緩沖區(qū)稱 。二、選擇編譯程序是一種常用的 件。A.應(yīng)用 B.系統(tǒng) C.工具 D.測試在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 錯誤和部分 錯誤。語法B.語義 C.語用D.運(yùn)行編譯程序生成的目標(biāo)程序 是機(jī)器語言的程序。一定 B.不一定C.某種情況下一定D.某種情況下不一定4.編譯程序生成的目標(biāo)程序 是可執(zhí)行的程序。A.一定 B.不一定 C.某種情況下一定D.某種情況下不一定5.一個語言的文法是 .A．惟一的 B．不惟一的 C.個數(shù)有限的D.無限的巴科斯-諾爾范式(即BNF)是一種廣泛采用的 的工具。A．描述規(guī)則 B.描述語言 C．描述文法 D．描述句子r=(a|b|c)(x|y|z)L（r）中元素為個（）A．9B．6C．18 D．278L={an|n≧0}相應(yīng)的正則表達(dá)式是（）a*B．a(chǎn)+C．a(chǎn)a*D．a(chǎn)a+編譯過程中掃描器的任務(wù)包括 。①組織源程序的輸入②按詞法規(guī)則分割出單詞，識別出其屬性，并轉(zhuǎn)換成屬性字的形式輸出⑧刪除注解④刪除空格及無用字符⑤行計數(shù)、列計數(shù)⑥發(fā)現(xiàn)并定位詞法錯誤⑦建立符號表A．②③④⑦ B．②③④⑥⑦C．①②③④⑥⑦ D．①②③④⑤⑥⑦10、編譯過程中，語法分析器的任務(wù)是 。分析單詞是怎樣構(gòu)成的c.分析語句和說明是如何構(gòu)成程序的d.分析程序的結(jié)構(gòu)A.bc Bd C．bcd D．a(chǎn)bcd11、語法分析的常用方法是 。a.自頂向下b.自底向上c.自左向右d.自右向左A．a(chǎn)bcd B．a(chǎn)b C．cd D．a(chǎn)bc12、編譯程序中的語法分析器接受以 為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。A．表達(dá)式 B．產(chǎn)生式 C．單詞 D．語句13、LL(1)文法的條件是 。FIRST(Xi)∩FIRST(Xj)=Φ，(i≠j)FIRST(Xj)∩FOLLOW(U)=ΦC．ABD．都不是14、一個右線性文法G一定是（）A．LL（1）C．SLR（1）文法B．LR（1）D．上述三者都不是15、算符文法是指 的文法。26U->…VW…的規(guī)則(U，V，W∈VN)VT中任意兩個符號對之間至多有一種優(yōu)先關(guān)系成立⑧沒有相同的規(guī)則右部U->ε的規(guī)則A.① B．①② C．①②③ D．①②③④16、算符優(yōu)先文法是指 的文法。U->…VW…的規(guī)則(U，V，W∈VN)VT中任意兩個符號對之間至多有一種優(yōu)先關(guān)系成立⑧沒有相同的規(guī)則右部U->ε的規(guī)則A.①② B．①②③ C.①②③④ D．①②④17、下列文法G[S]的句型aR／aSb／aTb／,b 的最左素短語為 。S->aTb|，T->RR->R／S|SA.aTb B.aSb C.S D.R／18算符優(yōu)先分析法每次都是對 進(jìn)行歸約簡單優(yōu)先分析法每次都是對句柄進(jìn)行歸約。A．最左短語 B.簡單短語 C.最左素短浯 D．素短語19、xab+cde-*f/:=是賦值語句( )相應(yīng)的后綴式A．x:=a+b+c*d-e/f B．x:=a+(b+c)*d-e/fC．x:+a+b+c*(d-e)/f D．x:=a+b+c+(c*d)-e/f20、LR(K)方法是 。A．從左到右分析，每次走K步的一種編譯方法B．從左到右分析，共經(jīng)過K步的一種編譯方法K步的一種編譯方法K個輸入符號的一種編譯方法、下面三個文法中，為SLR(1)文法的是 。10G1：P->PaP|bG3：P->bPb|bPc|d僅Gl G2 C．僅G3 D．G2和G322、有下列文法：11S->Pa|Pb|cP->Pd|Se|f該文法是 。A.LL(1)文法 B.SLR(1)文法C.a和b D.都不是23．代碼優(yōu)化的主要目標(biāo)是( ①如何提高目標(biāo)程序的運(yùn)行速度②如何減少目標(biāo)程序運(yùn)行所需的空間③如何協(xié)調(diào)①和②④如何使生成的目標(biāo)代碼盡可能短A①② B①②③ C①②④ D①②③④24、設(shè)文法G（S為其開始符號）產(chǎn)生式如下：S→aSb|ab|ε則G是一個（）A．LR（1）文法B．SLR（1）文法C．三型文法 D．二型文法在編譯程序采用的優(yōu)化方法中， 內(nèi)進(jìn)行的。12①合并已知常量 ②刪除多余運(yùn)算，③刪除歸納變量 ④強(qiáng)度削弱⑤代碼外提A①④ B①⑤ C①④⑤D③④⑤合并表達(dá)式中常量運(yùn)算的目的是 。12①合并常量，使表達(dá)式中的常量盡可能少②合并常量，使表達(dá)式盡可能簡短③將可在編譯時刻計算的常量運(yùn)算在編譯時刻計算出來，然后用所計算出來的值替換表達(dá)式中出現(xiàn)的所有這種常量運(yùn)算，使得生成的代碼指令盡可能少A① B② C③ D①②③下面的程序段可以進(jìn)行哪些優(yōu)化 。12i：=1j：=l0read kL：x：=x*iy：=j*iz：=x*ywriteji：=i+1ifi<100 goto Lhalt①合并已知常量 ②刪除多余運(yùn)算③刪除歸納變量 ④強(qiáng)度削弱⑤代碼外提可選項有：A．①④ B①⑤C，①④⑤D．③④⑤屬于低級語言的是（）B.Pascal C.Lisp DMasmC語言的八進(jìn)制無符號整規(guī)表達(dá)式是（A.(oct)8 B.(oct)* C.(oct)+ D.(oct)#采用（）實現(xiàn)三地址代碼時，不利于對中間代碼進(jìn)行優(yōu)化。A.四元式B.間接三元式C.D.有向無循環(huán)圖一個正規(guī)語言只能對應(yīng)( A一個正規(guī)文法；B一個最小有限狀態(tài)自動機(jī)；C.一個下推自動機(jī)D.一個確定的有限自動機(jī)文法G[A]：A→εA→aBB→AbB→a是( )：A正規(guī)文法 B二型文法上下無關(guān)文法 D.不確定下面說法正確的是( )：LALR（1）文法LALR（1）文法)：A．必要條件充分必要條件充分條件PL/0語言的目標(biāo)程序解釋執(zhí)行時用到的數(shù)據(jù)對象有( )：A目標(biāo)代碼CODEC關(guān)鍵字表WORDDSPL/0語言編譯時產(chǎn)生或使用的數(shù)據(jù)對象不包括( )：A目標(biāo)代碼CODECSWORD37、編譯程序是一種常用的 件。A.應(yīng)用 B.系統(tǒng) C支撐 D.自動化38、在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 錯誤和部分語義錯誤。A.語法 B語義 C.語用 D.運(yùn)行LR（1）LALR（1）文法：A則可能存在移進(jìn)/歸約沖突B則可能存在歸約/歸約沖突C則可能存在移進(jìn)/歸約沖突和歸約/歸約沖突D不存在沖突40、運(yùn)算符與運(yùn)算對象類型不符"屬于 。A.語法錯誤 B.語義錯誤 C.語用錯誤 D.規(guī)則三、簡答題解釋程序定義哪些寄存器?PL／0LIT?LOD?STO?CAL?INT?JMP?JPC?OPR?5S→a|∧|(T)T→T，S|S((a，a)，a)的規(guī)范歸約過程及每一步的句柄。寫出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示及三元式序列。0開頭。編譯程序的結(jié)構(gòu)是什么?關(guān)系有哪些基本性質(zhì)？解釋字母表,符號,符號串,符號串的長度,符號串聯(lián)結(jié)？自下而上分析算法的基本思想是什么？設(shè)有文法G：s::=Qc|cQ::=Rb|bR::=Sa|aBNF范式表示下述文法以消去ε規(guī)則：S::=aABb|abA::=Aab|εB::=Aa|a考慮下面程序…………Vara：integer；ProcedureS(X)；Begina：＝a＋1；X：＝a＋XBegina：＝5；S(a)；Print(a)End．試問：若參數(shù)傳遞方式分別采取傳名和傳值時，程序執(zhí)行后輸出a的值是什么？設(shè)有文法G[I]:8判斷下面符號串中哪些是該文法的句子.ab0(2)a0c01(3)aaabc10aabc(6)bbca為了正確地對源程序進(jìn)行編譯，不允許文法有二義性，那么怎樣才能排除文法的二義性呢?9什么是簡單子樹？什么是子樹？什么是句型的分析？自下而上分析算法的基本思想是什么？設(shè)有文法G：s::=Qc|cQ::=Rb|bR::=Sa|a四、綜合題Whilea＞0∨b＜0doBeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻譯成四元式序列。設(shè)布爾表達(dá)式的文法為EE(1)∨E(2)E→E(1)∧E(2)E→i改寫文法，使之適合進(jìn)行語法制導(dǎo)翻譯和實現(xiàn)回填；寫出改寫后的短個產(chǎn)生式的語義動作。設(shè)文法G(S)：S→(L)|aS|aL→L，S|S消除左遞歸和回溯；FIRSTFOL