電子科技大學(xué)編譯原理--A1答案--網(wǎng)絡(luò)教育

1、計算機編譯原理試卷 A1 參考答案一、單項選擇題(每小題 1 分，共 25 分)1、語言是 AA、句子的集合B、產(chǎn)生式的集合C、符號串的集合 D、句型的集合2、 編譯程序前三個階段完成的工作是 CA、詞法分析、語法分析和代碼優(yōu)化B、代碼生成、代碼優(yōu)化和詞法分析C、詞法分析、語法分析、語義分析和中間代碼生成D、詞法分析、語法分析和代碼優(yōu)化3、 一個句型中稱為句柄的是該句型的最左 DA、非終結(jié)符號B、短語C、句子D、直接短語4、 下推自動機識別的語言是 CA、 0 型語言 B、 1 型語言 C、 2 型語言 D、 3 型語言5、掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義的最

2、小語法單位即 BA、字符B、單詞C、句子 D、句型6、 對應(yīng)ChomSky四種文法的四種語言之間的關(guān)系是 BA、 L0L1L2L3B、 L3L2L1L0C、L3=L2 L1 L0 D、 L0 L1L2=L37、 詞法分析的任務(wù)是AA、識別單詞B、分析句子的含義C、識別句子D、生成目標代碼8、 常用的中間代碼形式不含DA、三元式B、四元式C、逆波蘭式D、語法樹9、 代碼優(yōu)化的目的是CA、節(jié)省時間B、節(jié)省空間C、節(jié)省時間和空間D、把編譯程序進行等價交換10、 代碼生成階段的主要任務(wù)是CA 、把高級語言翻譯成匯編語言B 、把高級語言翻譯成機器語言C、把中間代碼變換成依賴具體機器的目標代碼D 、把匯編

3、語言翻譯成機器語言11、 一個上下文無關(guān)文法G 包括四個組成部分：一組終結(jié)符，一組非終結(jié)符，一個開始符號，以及一組B 。A、字符串B、產(chǎn)生式C、數(shù)字符號D、文法12、 程序的基本塊是指D 。A、一個子程序B、一個僅有一個入口和一個出口的語句C、一個沒有嵌套的程序段D、一組順序執(zhí)行的程序段，僅有一個入口和一個出口13、 高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于B 分析方 法。A、自左向右 B、自頂向下 C、自底向上D、自右向左14、 在通常的語法分析方法中，A 特別適用于表達式的分析。A、算符優(yōu)先分析法B、LR分析法C、遞歸下降分析法D、LL (1)分析法15、 經(jīng)過編譯所得到的

4、目標程序是D。A、四元式序列B、間接三元式序列C、二元式序列D、機器語言程序或匯編語言程序16、 一個文法所描述的語言是 A。A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、無法確定17、 描述一個語言的文法是 C。A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、以上都不正確18、設(shè)有文法 GI ： I I1 |I0|Ia|Ic|a|b|c下列符號串中是該文法句子的有 B。 ab a0c01 aaa bc1O可選項有：A、B、C、D、19、運行階段的存儲組織與管理的目的是 C。 提高編譯程序的運行速度 節(jié)省編譯程序的存儲空間 提高目標程序的運行速度可選項有：A、 B、C、20、將編譯程

5、序分成若干個“遍”是為了 為運行階段的存儲分配做準備D、B。A、提高程序的執(zhí)行效率B、使程序的結(jié)構(gòu)更加清晰C、利用有限的機器內(nèi)存并提高機器的執(zhí)行效率D、禾U用有限的機器內(nèi)存但降低了機器的執(zhí)行效率21、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標 代碼生成等五個部分，還應(yīng)包括 C。A、模擬執(zhí)行器B、解釋器C、表格處理和出錯處理D、符號執(zhí)行器22、一個句型中的最左 B稱為該句型的句柄。A、短語B、簡單短語C、素短語 D、終結(jié)符號23 、 設(shè) G 是 一 個 給 定 的 文 法 ， S 是 文 法 的 開 始 符 號 ， 如 果x（其中X V*）,則稱X是文法G的一個

6、._ BA、候選式B、句型C、單詞 D、產(chǎn)生式24、一個上下文無關(guān)文法G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 D。A、句子 B、句型C、單詞D、產(chǎn)生式25、文法 GE ：E T E + TT F T * FF a ( E)該文法句型E + F* (E + T)的簡單短語是下列符號串中的 B。( E+ T)E+ T F F* (E + T)可選項有：A、和B、和C、和 D、二、判斷題(每小題 1 分，共 10分)( ) 26、對任意一個右線性文法 G,都存在一個 NFA M ,滿足L(G)=L(M)。( ) 27、對任意一個右線性文法 G,都存在一個

7、DFA M ,滿足L(G)=L(M)。( ) 28、對任何正規(guī)表達式 e,都存在一個 NFA M ,滿足L(G)=L(e)。( ) 29、對任何正規(guī)表達式 e,都存在一個 DFA M ,滿足L(G)=L(e)。( × ) 30、計算機高級語言翻譯成低級語言只有解釋一種方式。( × ) 31、在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。( × ) 32、甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng) 功能完全相同。( ) 33、正則文法其產(chǎn)生式為 A a, A Bb, A,B VN, a、b VTO(× ) 34、每個文法都能

8、改寫為 LL(1)文法。( ) 35、遞歸下降法允許任一非終極符是直接左遞歸的。三、名詞解釋題(每小題4 分，共 8 分)36、歸約我們稱直接歸約出 A ,僅當 A 是一個產(chǎn)生式，且>(VN U Vt)*。歸約過程就是從輸入串開始， 反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號， 直至文法開始符。37、推導(dǎo)我們稱 A 直接推出 ,即 A ,僅當 A 是一個產(chǎn)生式，且> (VN U Vt)*。如果 1 2 n,則我們稱這個序列是從1至 2的一個推導(dǎo)。若存在一個從 1 n的推導(dǎo)，則稱 1可推導(dǎo)出 n。推導(dǎo)是歸約的逆過程。四、簡答題(每小題 4 分,共 8分)38、試給出非確定自動機的定義

9、。答：一個非確定的有窮自動機( NFA) M 是一個五元組： M=(K, f, S , Z)。 其中 :(1) K 是一個有窮集,它的每個元素稱為一個狀態(tài)；(2 )是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；(3) f 是狀態(tài)轉(zhuǎn)換函數(shù),是在K× *K 的子集的映射,即, f: K×*2K ；表明在某 狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；(4) S ( K 是- 個非空初態(tài)集；( 5) Z ( K 是一 個終態(tài)集(可空) 。39、編譯程序的工作分為那幾個階段？答：詞法分析、語法分析和語義分析是對源程序進行的分析 （稱為編譯程序的前端），而中間 代

10、碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合 （稱為編譯程序的后端）， 它們從源程序的中間表示建立起和源程序等價的目標程序。五、應(yīng)用題（每小題 5分，共25分）40、對于文法 GS : SAB，A AalbB，B aSb求句型baSb的全部短語、直接短語和句 柄？句型baSb的語法樹如下圖所示。答：baSb為句型baSb的相對于S的短語，ba為句型baSb的相對于 A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的相對于B的短語，且為直接短語 和句柄。41、設(shè)有非確定的有自限動機NFA M=（A，B，C，0，1，A，C）,其中：（A，0）=C （A，1）

11、=A，B （B，1）=C （C, 1）=C。請畫出狀態(tài)轉(zhuǎn)換距陣和狀 態(tài)轉(zhuǎn)換圖。答：狀態(tài)轉(zhuǎn)換距陣為:01ACA，BBCCC狀態(tài)轉(zhuǎn)換圖為:42、文法 GS:S aSPQabQQP PQ bP bb bQ bccQ CC（1）它是ChomSky哪一型文法？（2）它生成的語言是什么？答：（1）由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部 的符號長度，所以文法 GS是ChOmSkyI型文法，即上下文有關(guān)文法。（2） 按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低（否則無法推出句子），我們可以得到:S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ

12、aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQ aaabbPqqq aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法GS生成的語言L=a nbncnn 143、下面文法GS是否為LL (1)文法？說明理由。S A BlPQXA XyB bcP d P| Q aQ| 答：該文法不是 LL ( 1)文法。只有三個非終結(jié)符有兩個選擇。(1) P的兩個右部d P和的開始符號肯定不相交。(2) Q的兩個右部a Q和的開始符號肯定不相交。(3) 對S來說，由于x FIRST(A B)，同時也有x

13、 FIRST(P Q x)(因為P和Q都可能為空)所以該文法不是 LL ( 1)文法。44、設(shè)有文法GS:S aAA AbA b求識別該文法所有活前綴的DFA。答：(1)首先拓廣文法：在G中加入產(chǎn)生式0.S'S,然后得到新的文法 G':0.S' S1.S aA2. A Ab3. A b再求G '的識別全部活前綴的 DFA :六、綜合題(每小題 8分，共24分)45、對給定正規(guī)式 b* (d|ad) (b|ab) +,構(gòu)造其NFA M。答：首先用A+=AA *改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*;其次，構(gòu)造該正規(guī)式的 NFA M，如 下圖所示。

14、46、將文法GV改造成為LL(I)的。GV : V NNEE VV+EN i答：對文法GV提取公共左因子后得到文法：GV : V NAA EE VBB |+EN i求出文法GV中每一個非終結(jié)符號的FIRST集：FlRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個非終結(jié)符號的FoLLoW集：FoLLoW(V)=# U FIRST(B) U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST() U FOLLOW(B)= FIRST() U FOLLOW(E)=FOL

15、LOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) U FOLLOW(V)=,+,#可以看到，對文法 G ' V的產(chǎn)生式A |E,有FIRST(E) FOLLOW(A)= +,#= ?對產(chǎn)生式B | + E ,有FIRST(+E) FOLLOW(B)=+ = ?而文法的其他產(chǎn)生式都只有一個不為的右部，所以文法G ' V是LL(I)文法。47、 對于文法 GS : S ASIbA SAla(1) 列出所有LR (0)項目(2) 列出構(gòu)成文法 LR (0)項目集規(guī)范族。答：首先將文法G拓廣為GS:S' SS ASIbA SA|a(1)文法GS 的L

16、R ( 0)項目是:1、S S5、SAS 9、A S A2、S S6、S b10、A SA 3、SAS7、S b 11、 A a4、SAS8、A SA12、 Aa（ 2）列出構(gòu)成文法 LR （ 0）項目集規(guī)范族。用 -CLOSURE （閉包）辦法構(gòu)造文法 G 的 LR （ 0）項目集規(guī)范族如下:0: 1、 S S3:9、 AS A6: 12、 A a3、 S AS8、 A SA7: 7、 Sb8、 A SA3、 S AS11 、 A a6、 S b6、 S b11、 A a1: 2、 S S4: 10、 A SA9、 AS A4、 S A S8、 A SA3、 S AS11、 A a6、 S b3、 S A