編譯原理模擬題

編譯原理模擬題編譯原理模擬題編譯原理模擬題資料僅供參考文件編號(hào)：2022年4月編譯原理模擬題版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：一、

填空題（每空1分，共20分）1．詞法分析語(yǔ)法分析代碼優(yōu)化2．語(yǔ)法分析最常用的兩類方法是自上而下和自下而上分析法。3．確定的有窮自動(dòng)機(jī)是一個(gè)

五元組

，通常表示為DFA=(K,∑,M,S,Z)。4．所謂最右推導(dǎo)是指

任何一步都是對(duì)中最右非終結(jié)符進(jìn)行替換

。5．語(yǔ)法分析器的任務(wù)是

分析一個(gè)文法的句子結(jié)構(gòu)。6．如果一個(gè)文法的任何產(chǎn)生式的右部都不含有相鄰的非終結(jié)符，則這種文法稱為算符文法。7．進(jìn)行確定的自上而下語(yǔ)法分析要求語(yǔ)言的文法是無(wú)左遞歸和

公共左因子的。8．LR分析法是一種

自下而上

的語(yǔ)法分析方法。9．根據(jù)優(yōu)化對(duì)象所涉及的程序范圍，代碼優(yōu)化分為

局部?jī)?yōu)化、循環(huán)優(yōu)化和

局部?jī)?yōu)化

等。10．常用的優(yōu)化技術(shù)包括：刪除公共子表達(dá)式代碼外提

變換循環(huán)控制條件

等。（合并已知量、刪除無(wú)用賦值）二、是非題（下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}后的括號(hào)內(nèi)打“√”，錯(cuò)的打“×”。每題2分，共20分）

1．正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。(

×

)2．僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。（√）3．如果一個(gè)文法是遞歸的，則其產(chǎn)生的語(yǔ)言的句子是無(wú)窮個(gè)。

（√）4．四元式之間的聯(lián)系是通過(guò)符號(hào)表實(shí)現(xiàn)的。（×）5．文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。

（√）6．一個(gè)LL(l)文法一定是無(wú)二義的。

(

√

)7．在規(guī)范規(guī)約中用最左素短語(yǔ)來(lái)刻劃可歸約串。(

×

)8．目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。(

√

)9．編譯程序是對(duì)匯編程序的翻譯。

（×）10．逆波蘭法表示的表達(dá)式亦稱前綴式。

(

×

)三、

簡(jiǎn)答題（每題5分，共15分）1、簡(jiǎn)述棧式存儲(chǔ)管理策略；

2、何謂DAG；

3、何謂文法的二義性；四、

給出下述文法對(duì)應(yīng)的正規(guī)式

（7分）

S→0A|1BA→1S|1B→0S|0解：首先得正規(guī)式方程組：

S=0A+1B

A=1S+1

B=0S+0

求解該方程組得：S=(01|10)(01|10)*

五、

已知文法G(E)：（2分）是文法G[S]的句型。

E→T|E+T|E-T短語(yǔ)：E+T*F,

T*F

（2分）T→F|T*F|T/F直接短語(yǔ)：T*F

（2分）F→(E)|I

句柄：T*F

（2分）證明E+T*F是該文法的一個(gè)句型，并指出該句型的所有短語(yǔ)、直接短語(yǔ)和句柄。（8分）何謂二義性文法試舉一例說(shuō)明。（5％）答：若文法G的一個(gè)句子對(duì)應(yīng)有兩棵或兩棵以上不同的推導(dǎo)樹，則稱該句子是二義性的。產(chǎn)生二義性句子的文法稱為二義性文法，否則該文法是無(wú)二義性的。 例子：給定文法G[<R>]：<R>→<R>*|<R><R>|a|b考察句子ab*，它有兩棵不同的推導(dǎo)樹，如下所示：《編譯原理》模擬試題一一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃√，錯(cuò)誤的劃×）（每個(gè)2分，共20分）1．計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。(×)2．在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(×)3．甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(√)4．正則文法其產(chǎn)生式為A->a，A->Bb,

A,B∈VN，a、b∈VT。(×)5．每個(gè)文法都能改寫為L(zhǎng)L(1)文法。(√)6．遞歸下降法允許任一非終極符是直接左遞歸的。(√)7．算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(×)8．自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。(×)9．LR法是自頂向下語(yǔ)法分析方法。(×)10．簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。(×)二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40分)1．一個(gè)編譯程序中，不僅包含詞法分析，_____，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A．()語(yǔ)法分析B．()文法分析C．()語(yǔ)言分析D．()解釋分析2．詞法分析器用于識(shí)別_____。

A．()字符串

B．()語(yǔ)句

C．()單詞D．()標(biāo)識(shí)符3．語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的_____。A．()語(yǔ)義錯(cuò)誤

B．()語(yǔ)法和語(yǔ)義錯(cuò)誤

C．()錯(cuò)誤并校正

D．()語(yǔ)法錯(cuò)誤4．下面關(guān)于解釋程序的描述正確的是_____。(1)解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼(2)解釋程序適用于COBOL和FORTRAN語(yǔ)言(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的

A．()(1)(2)B．()(1)C．()(1)(2)(3)

D．()(2)(3)5．解釋程序處理語(yǔ)言時(shí),大多數(shù)采用的是_____方法。A．()源程序命令被逐個(gè)直接解釋執(zhí)行

B．()先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行

C．()先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,再執(zhí)行

D．()以上方法都可以6．編譯過(guò)程中,語(yǔ)法分析器的任務(wù)就是_____。(1)分析單詞是怎樣構(gòu)成的

(2)

分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的(3)分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的

(4)分析程序的結(jié)構(gòu)A．()(2)(3)B．()(2)(3)(4)

C．()(1)(2)(3)D．()(1)(2)(3)(4)7．編譯程序是一種_____。A.()匯編程序B．()翻譯程序

C．()解釋程序

D．()目標(biāo)程序8．文法G所描述的語(yǔ)言是_____的集合。A.()文法G的字母表V中所有符號(hào)組成的符號(hào)串

B．()文法G的字母表V的閉包V*中的所有符號(hào)串

C．()由文法的開始符號(hào)推出的所有終極符串

D.()由文法的開始符號(hào)推出的所有符號(hào)串9．文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_____。A.()短語(yǔ)文法

B．()正則文法

C．()上下文有關(guān)文法D．()上下文無(wú)關(guān)文法10．一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組_____。A．()句子B．()句型

C．()單詞D．()產(chǎn)生式2．文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_____。A.()短語(yǔ)文法

B．()正則文法

C．()上下文有關(guān)文法D．()上下文無(wú)關(guān)文法3．一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組_____。A．()句子B．()句型C．()單詞D．()產(chǎn)生式4．_____是一種典型的解釋型語(yǔ)言。

A．()BASICB．()CC．()FORTRAN

D．()PASCAL5．與編譯系統(tǒng)相比，解釋系統(tǒng)_____。A．()比較簡(jiǎn)單,可移植性好,執(zhí)行速度快

B．()比較復(fù)雜,可移植性好,執(zhí)行速度快

C．()比較簡(jiǎn)單,可移植性差,執(zhí)行速度慢

D．()比較簡(jiǎn)單,可移植性好,執(zhí)行速度慢6．用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_____。

A．()源程序

B．()目標(biāo)程序

C．()連接程序D．()解釋程序7．詞法分析器用于識(shí)別_____。

A.()字符串

B．()語(yǔ)句

C．()單詞

D．()標(biāo)識(shí)符8．編寫一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后,到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)_____這幾步:(1)編輯

(2)編譯

(3)連接

(4)運(yùn)行A.()(1)(2)(3)(4)

B．()(1)(2)(3)

C．()(1)(3)

D．()(1)(4)9．把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_____完成的。A．()編譯器

B．()匯編器

C．()解釋器

D．()預(yù)處理器10．文法G所描述的語(yǔ)言是_____的集合。A.()文法G的字母表V中所有符號(hào)組成的符號(hào)串

B．()文法G的字母表V的閉包V*中的所有符號(hào)串

C．()由文法的開始符號(hào)推出的所有終極符串

D.()由文法的開始符號(hào)推出的所有符號(hào)串三、填空題(每空1分，共10分)1．編譯程序的工作過(guò)程一般可以劃分為詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有__表格處理___和___出錯(cuò)處理__。2．若源程序是用高級(jí)語(yǔ)言編寫的,___目標(biāo)程序__是機(jī)器語(yǔ)言程序或匯編程序,則其翻譯程序稱為___編譯程序__。3．編譯方式與解釋方式的根本區(qū)別在于__是否生成目標(biāo)代碼___。4．對(duì)編譯程序而言,輸入數(shù)據(jù)是___源程序__,輸出結(jié)果是__目標(biāo)程序___。5．產(chǎn)生式是用于定義___語(yǔ)法成分__的一種書寫規(guī)則。6．語(yǔ)法分析最常用的兩類方法是___自上而下__和___自下而上__分析法。1．語(yǔ)法分析是依據(jù)語(yǔ)言的__語(yǔ)法___規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的__語(yǔ)義___規(guī)進(jìn)行的。2．語(yǔ)法分析器的輸入是__單詞符號(hào)串___，其輸出是__語(yǔ)法單位___。3．一個(gè)名字的屬性包括__類型___和__作用域___。5．逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為__(a+b+c)*d-e___。1．詞法分析基于__正則___文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。2．語(yǔ)法分析基于__上下文無(wú)關(guān)___文法進(jìn)行，即識(shí)別的是該類文法的句子。語(yǔ)法分析的有效工具是__語(yǔ)法樹___。3．分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是__最左素短語(yǔ)___，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是___句柄__。4．語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有__逆波蘭___、___四無(wú)式表示__與___三元式表示__等。5．按Chomsky分類法，文法按照___規(guī)則定義的形式__進(jìn)行分類。6．一個(gè)文法能用有窮多個(gè)規(guī)則描述無(wú)窮的符號(hào)串集合（語(yǔ)言）是因?yàn)槲姆ㄖ写嬖谟衉__遞歸__定義的規(guī)則。四、簡(jiǎn)答題（20分）1.什么是句子什么是語(yǔ)言答：(1)設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Sx(其中x∈VT*),則稱x是文法的一個(gè)句子。

(2)設(shè)G[S]是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G)＝{x│Sx,x∈VT*}。2.寫一文法，使其語(yǔ)言是偶正整數(shù)的集合,要求：

(1)允許0打頭；

(2)不允許0打頭。解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:S->PD|DP->NP|ND->0|2|4|6|8N->0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:S->PD|P0|DP->NR|NR->QR|QD->2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|93.已知文法G[E]為：

E→T|E+T|E-T

T→F|T*F|T/F

F→（E）|i

①該文法的開始符號(hào)（識(shí)別符號(hào)）是什么

②請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VN。

③找出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解：①該文法的開始符號(hào)（識(shí)別符號(hào)）是E。

②該文法的終結(jié)符號(hào)集合VT={+、-、*、/、（、）、i}。非終結(jié)符號(hào)集合VN={E、T、F}。

③句型T+T*F+I的短語(yǔ)為i、T*F、第一個(gè)T、T+T*F+i;簡(jiǎn)單短語(yǔ)為i、T*F、第一個(gè)T;句柄為第一個(gè)T。4.構(gòu)造正規(guī)式相應(yīng)的NFA:1(0|1)*101解1(0|1)*101對(duì)應(yīng)的NFA為5.寫出表達(dá)式(a＋b*c)/(a＋b)－d的逆波蘭表示和三元式序列。逆波蘭表示：abc*＋ab＋/d－

三元式序列：①(*，b，c)②(＋，a，①)③(＋，a，b)④(/，②，③)⑤(－，④，d)五.計(jì)算題（10分）構(gòu)造下述文法G[S]的自動(dòng)機(jī)：S->A0A->A0|S1|0該自動(dòng)機(jī)是確定的嗎若不確定，則對(duì)它確定化。解：由于該文法的產(chǎn)生式S->A0，A->A0|S1中沒有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把SA0代入產(chǎn)生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入S->A0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動(dòng)機(jī)為：

由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA，下面將它確定化：

下表由子集法將NFA轉(zhuǎn)換為DFA:由上表可知DFA為：四、簡(jiǎn)答題（20分）1.文法G[S]為：S->Ac|aBA->abB->bc寫出L(G[S])的全部元素。解：S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的DFA。解：先構(gòu)造NFA：

確定化：

重新命名，令A(yù)B為B、AC為C、ABY為D得：

所以，可得DFA為：3.文法S->a|^|(T)T->T,S|S對(duì)(a,(a,a)和(((a,a),^,(a)),a)的最左推導(dǎo)。解：對(duì)(a,(a,a)的最左推導(dǎo)為：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,