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

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

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

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

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

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

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

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

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

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

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

11、=A，B （B，1）=C （C, 1）=C。請(qǐng)畫(huà)出狀態(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）它生成的語(yǔ)言是什么？答：（1）由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部 的符號(hào)長(zhǎng)度，所以文法 GS是ChOmSkyI型文法，即上下文有關(guān)文法。（2） 按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低（否則無(wú)法推出句子），我們可以得到:S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ

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

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

14、46、將文法GV改造成為L(zhǎng)L(I)的。GV : V NNEE VV+EN i答：對(duì)文法GV提取公共左因子后得到文法：GV : V NAA EE VBB |+EN i求出文法GV中每一個(gè)非終結(jié)符號(hào)的FIRST集：FlRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個(gè)非終結(jié)符號(hào)的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)=,+,#可以看到，對(duì)文法 G ' V的產(chǎn)生式A |E,有FIRST(E) FOLLOW(A)= +,#= ?對(duì)產(chǎn)生式B | + E ,有FIRST(+E) FOLLOW(B)=+ = ?而文法的其他產(chǎn)生式都只有一個(gè)不為的右部，所以文法G ' V是LL(I)文法。47、 對(duì)于文法 GS : S ASIbA SAla(1) 列出所有LR (0)項(xiàng)目(2) 列出構(gòu)成文法 LR (0)項(xiàng)目集規(guī)范族。答：首先將文法G拓廣為GS:S' SS ASIbA SA|a(1)文法GS 的L

16、R ( 0)項(xiàng)目是: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）項(xiàng)目集規(guī)范族。用 -CLOSURE （閉包）辦法構(gòu)造文法 G 的 LR （ 0）項(xiàng)目集規(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