模擬題-編譯原理

選擇1.（B）是兩類程序語言處理程序。A.高級(jí)語言程序和低級(jí)語言程序B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng)D.系統(tǒng)程序和應(yīng)用程序2.編譯程序前三個(gè)階段完成的工作是（c）A.詞法分析、語法分析和代碼優(yōu)化代碼生成、代碼優(yōu)化和詞法分析B.詞法分析、語法分析、語義分析和中間代碼生成C.詞法分析、語法分析和代碼優(yōu)化3.代碼優(yōu)化的目的是（C）。A.節(jié)省時(shí)間B.節(jié)省空間C.節(jié)省時(shí)間和空間,把編譯程序進(jìn)行等價(jià)交換代碼優(yōu)化的目的是（節(jié)省時(shí)間和空間）。4.描述一個(gè)語言的文法是（C）。A.唯一的B.不唯一的C.可能唯一，也可能不唯一D.都不對(duì)5.下推自動(dòng)機(jī)識(shí)別的語言是（C）。A.0型語言B.1型語言C.2型語言D.3型語言6.如果文法G是無二義的，則它的任何句子α(A)。A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同7.LR（0）分析法中，語法分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型(B)的DFA狀態(tài)。A.前綴B.活前綴C.LR（0）項(xiàng)目D.句柄8.若文法G定義的語言是無限集，則文法必然是（A）。A.遞歸的B.前后文無關(guān)的C.二義性的D.無二義性的[分析]本題考查語言文法的特點(diǎn)。所謂文法就是語法規(guī)則，是描述語言的語法結(jié)構(gòu)的形式規(guī)則。如果一個(gè)文法定義的語言是無限集，那么此文法必然是遞歸的。9.掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語法單位即（B）。A.字符B.單詞C.句子D.句型10.算符文法是指(A)的文法。①?zèng)]有形如U→...VW...的規(guī)則（U，V，W?VN）②VT中任意兩個(gè)符號(hào)之間至多存在一種算符優(yōu)先關(guān)系③沒有相同右部的規(guī)則④沒有形如U→ε的規(guī)則A.①B.①和②C.①、②和③D.①、②、③和④11.一般程序設(shè)計(jì)語言的定義都涉及(B)三個(gè)方面。①語法②語義③語用④程序基本符號(hào)的確定A.①、②和③B.①、②和④C.①、③和④D.②、③和④[解析]一般情況下，程序設(shè)計(jì)語言的定義都涉及語法、語義、語用等3個(gè)方面。①語法是指由程序語言基本符號(hào)組成程序中的各個(gè)語法成分(包括程序)的一組規(guī)則，不涉及語法成分的特定含義，也不涉及使用者。②語義是程序語言中按語法規(guī)則構(gòu)成的各個(gè)語法成分的含義，但不涉及使用者。③語用表示了構(gòu)成語言的各個(gè)記號(hào)和使用者的關(guān)系。?????????????????試卷給出的答案是B12.生成能被5整除的正整數(shù)的文法G[Z]是(C)。A.G（Z）：Z→AC，A→BA|B，B→0|1|2|…|9，C→0|5B.G（Z）：Z→AC，A→BA|ε，B→0|1|2|…|9，C→0|5C.G（Z）：Z→AC|5，A→BA|B，B→0|1|2|…|9，C→0|5D.G（Z）：Z→AC|C，A→BA|B，B→0|1|2|…|9，C→0|513.程序的基本塊是指(D)。A.不含無條件轉(zhuǎn)移語句的程序段B.不含條件轉(zhuǎn)移語句的程序段C.不含停機(jī)的語句程序段D.僅含有一個(gè)入口語句和一個(gè)出口語句的順序程序14.文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（B）。A.短語文法B.正則文法C.上下文有關(guān)文法D.上下文無關(guān)文法喬姆斯基把方法分成四種類型，即0型、1型、2型和3型，源于《編譯原理》，但《軟件設(shè)計(jì)師》教程對(duì)于該分類的介紹很簡(jiǎn)略，也很抽象，根據(jù)網(wǎng)上各類博客對(duì)其的解釋和教程的說法，大致總結(jié)如下：首先要闡明的是，一般的文法至少都是0型文法，也就是說0型文法限制最少，二1,2,3型文法都是在0型文法基礎(chǔ)上加以限制形成。若將0型文法比作基類的話，1,2,3,4就是不斷繼承并加以限制得到的子類。①0型文法設(shè)G=（VN，VT，P，S），如果它的每個(gè)產(chǎn)生式α→β是這樣一種結(jié)構(gòu)：α∈(VN∪VT)*且至少含有一個(gè)非終結(jié)符，而β∈(VN∪VT)*，則G是一個(gè)0型文法。0型文法也稱短語文法。0型文法的能力相當(dāng)于圖靈機(jī)(Turing)。我們發(fā)現(xiàn)0型文法是限制最少的一種文法，平時(shí)見到的文法幾乎都屬于0型文法。②1型文法1型文法也叫上下文有關(guān)文法，此文法對(duì)應(yīng)于線性有界自動(dòng)機(jī)。它是在0型文法的基礎(chǔ)上每一個(gè)α→β,都有|β|>=|α|。這里的|β|表示的是β的長(zhǎng)度。注意：雖然要求|β|>=|α|，但有一特例：α→ε也滿足1型文法。如有A->Ba則|β|=2,|α|=1符合1型文法要求。反之,如aA->a，則不符合1型文法。③2型文法2型文法也叫上下文無關(guān)文法，它對(duì)應(yīng)于下推自動(dòng)機(jī)。2型文法是在1型文法的基礎(chǔ)上,再滿足：每一個(gè)α→β都有α是非終結(jié)符。如A->Ba,符合2型文法要求。如Ab->Bab雖然符合1型文法要求,但不符合2型文法要求，因?yàn)槠洇?Ab，而Ab不是一個(gè)非終結(jié)符。④3型文法3型文法也叫正規(guī)文法，它對(duì)應(yīng)于有限狀態(tài)自動(dòng)機(jī)。它是在2型文法的基礎(chǔ)上滿足:A→α|αB（右線性）或A→α|Bα（左線性）。如有：A->a,A->aB,B->a,B->cB，則符合3型文法的要求。但如果推導(dǎo)為:A->ab,A->aB,B->a,B->cB或推導(dǎo)為:A->a,A->Ba,B->a,B->cB則不符合3型方法的要求了。具體的說，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定義,如果把后面的ab,改成“一個(gè)非終結(jié)符＋一個(gè)終結(jié)符”的形式（即為aB）就對(duì)了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改為B->Bc的形式就對(duì)了,因?yàn)锳→α|αB（右線性）和A→α|Bα（左線性）兩套規(guī)則不能同時(shí)出現(xiàn)在一個(gè)語法中,只能完全滿足其中的一個(gè),才能算3型文法。那么這四類文法如何判斷呢？其實(shí)四種文法就是規(guī)定產(chǎn)生式的左和右邊的字符的組成規(guī)則不同而已，于是我們便可以嚴(yán)格根據(jù)左邊和右邊規(guī)則的不同來加以判斷。首先，應(yīng)該明確，四種文法，從0型到3型，其規(guī)則和約定越來越多，限制條件也越來越多，所以我們應(yīng)該按照3->2->1->0的順序去判斷，一旦滿足前面的規(guī)則，就不用去判斷后面的了。1.先來看看3型文法的判斷規(guī)則①：左邊必須只有一個(gè)字符，且必須是非終結(jié)符；②：其右邊最多只能有兩個(gè)字符，要么是一個(gè)非終結(jié)符+終結(jié)符（終結(jié)符+非終結(jié)符），要么是一個(gè)終結(jié)符。③：對(duì)于3型文法中的所有產(chǎn)生式，若其右邊有兩個(gè)字符的產(chǎn)生式，這些產(chǎn)生式右邊兩個(gè)字符中終結(jié)符和非終結(jié)符的相對(duì)位置一定要固定，也就是說如果一個(gè)產(chǎn)生式右邊的兩個(gè)字符的排列是：終結(jié)符＋非終結(jié)符，那么所有產(chǎn)生式右邊只要有兩個(gè)字符的，都必須滿足終結(jié)符+非終結(jié)符。反之亦然。2.再看看2型文法判斷規(guī)則①：與3型文法的第一點(diǎn)相同，即：左邊必須有且僅有一個(gè)非終結(jié)符。②：2型文法所有產(chǎn)生式的右邊可以含有若干個(gè)終結(jié)符和非終結(jié)符（只要是有限的就行，沒有個(gè)數(shù)限制）。3.最后再看看1型文法判斷規(guī)則①：1型文法所有產(chǎn)生式左邊可以含有一個(gè)、兩個(gè)或兩個(gè)以上的字符，但其中必須至少有一個(gè)非終結(jié)符。②：與2型文法第二點(diǎn)相同，但需要滿足|α|≤|β|.0型文法不需要判斷了，一般的文法都是0型文法。O(∩_∩)O15.中間代碼生成時(shí)所依據(jù)的是（C）。A.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價(jià)變換規(guī)則16.符號(hào)串a(chǎn)b1b2是給定文法G[A]：A→aB，B→bB|b的句子，該句子的句柄是(B)。A.b1B.b2C.cD.b1b217.常用的中間代碼形式不含（D）。A.三元式B.四元式C.逆波蘭式D.語法樹18.解釋程序處理語言時(shí)，大多數(shù)采用的是（A）方法。A.源程序命令被逐個(gè)直接解釋執(zhí)行B.先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行C.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,再執(zhí)行D.以上方法都可以19.下列___C___優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A.強(qiáng)度削弱B.刪除歸納變量C.刪除多余運(yùn)算D.代碼外提在編譯程序采用的優(yōu)化方法中，_____D______是在循環(huán)語句范圍內(nèi)進(jìn)行的。①合并已知常量②刪除多余運(yùn)算③刪除歸納變量④強(qiáng)度削弱⑤代碼外提A.①④B.①⑤C.①④⑤D.③④⑤20.一個(gè)文法所描述的語言是（A）。A.唯一的B.不唯一的C.可能唯一，也可能不唯一D.都不對(duì)判斷1.削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性?！?.靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。(×)3.正則文法其產(chǎn)生式為A->a，A->Bb,A,B∈VN，a、b∈VT?！????????????????4.構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表?！蘋OOOOOOOOOOOOO5.設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)?！????????????6.進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用?！?.若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄?！?.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤?！?.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同?！?0.自底而上語法分析方法的主要問題是候選式的選擇。ד用高級(jí)語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。(×)2型文法一定是3型文法。（×）3型文法一定是2型文法。(√)LR法是自頂向下語法分析方法。(×)LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。(√)LR分析技術(shù)無法適用二義文法。(×)LR分析器的任務(wù)就是產(chǎn)生LR分析表。(√)LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。(√)編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。(×)編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。(×)編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。(×)并不是每個(gè)文法都能改寫成LL(1)文法。(√)采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。（√）產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。(×)程序語言的語言處理程序是一種應(yīng)用軟件。(×)遞歸下降法不允許任一非終極符是直接左遞歸的。(√)遞歸下降分析法是一種自下而上分析法。(×)遞歸下降分析法是自頂向下分析方法。(√)對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。(×)分析作為單獨(dú)的一遍來處理較好。(×)符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。(×)歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。(√)計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。(×)甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(√)簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。(×)僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。(√)進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。(×)靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。(×)兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。(×)每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。（√）每個(gè)基本塊可用一個(gè)DAG表示。（√）每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。(√)每個(gè)文法都能改寫為L(zhǎng)L(1)文法。(√)目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。(√)逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。(√)逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。(√)逆波蘭法表示的表達(dá)式亦稱后綴式。(√)逆波蘭法表示的表達(dá)試亦稱前綴式。(√)確定的的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正集(√)如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。(√)如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則文法是二義性的。(√)若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(×)樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(×)數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。(×)數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。(×)算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。(×)算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(×)同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突(×)削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。(√)序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。(√)一個(gè)LL(l)文法一定是無二義的。(√)一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。(√)一個(gè)句型的直接短語是唯一的。（×）一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。(×)一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。(√)一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。(×)