編譯原理法分析習(xí)題集帶答案

1、編譯原理習(xí)題（一）詞法分析一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃X）1編譯程序是對高級語言程序的解釋執(zhí)行。（X）2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （X） 9兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。（X ）二、選擇題1詞法分析器的輸出結(jié)果是A （ ） 記號B （ ） 相應(yīng)條目在符號表中的位置C （ ） 記號和屬性二元組D（ ） 屬性值2 正規(guī)式 M 1 和 M 2 等價是指 A. （ ） M1和M2的狀態(tài)數(shù)相等 等C. （ ） M1和M2所識別的語言集相等 3.語言是B . （ ） M1和M2的有向邊條數(shù)相D. （ ） M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等A.句子的集合B

2、產(chǎn)生式的集合C.符號串的集合D句型的集合4編譯程序前三個階段完成的工作是A. 詞法分析、語法分析和代碼優(yōu)化B. 代碼生成、代碼優(yōu)化和詞法分析C. 詞法分析、語法分析、語義分析和中間代碼生成D. 詞法分析、語法分析和代碼優(yōu)化5掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即A 字符B 單詞6構(gòu)造編譯程序應(yīng)掌握 。A（ ） 源程序BC （ ） 編譯方法 7詞法分析的任務(wù)是A 識別單詞BC .識別句子DC 句子 D 句型（ ） 目標(biāo)語言D（ ） 以上三項都是分析句子的含義生成目標(biāo)代碼三、填空題 1計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。3.

3、編譯過程可分為 （ 詞法分析） ，（語法分析） ，（語義分析與中間代碼生成 ），（優(yōu)化） 和（目標(biāo)代碼生成 ）五個階段。6.掃描器的任務(wù)是從（ 源程序中 ）中識別出一個個（ 單詞符號 ）。17. 一張轉(zhuǎn)換圖只包含有限個狀態(tài) , 其中有一個被認為是（初）態(tài) ;而且實際上至少要有一個 （終 ）態(tài)。1編譯程序首先要識別出源程序中每個 （單詞），然后再分析每個 （句子）并翻譯其意義。 3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序 的（分析），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的（綜合）。5對編譯程序而言，輸入數(shù)據(jù)是 （源程序），輸出結(jié)果是 （目標(biāo)程序

4、）。四、名詞解釋題：1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。13.掃描器-執(zhí)行詞法分析的程序。五、簡答題(一)、描述由正規(guī)式b*(abb*)*(a|)定義的語言，并畫出接受該語言的最簡DFA答：由正規(guī)式b*(abb*)*(a|)定義的語言是字母表a, b上不含子串a(chǎn)a的所有串的集合。最簡DFA如下：DFA答：正規(guī)式b a(bb a) b體現(xiàn)的特點是，每個 a的左邊都有若干b,除非a是第一個字母。該正規(guī)式定義的語言是：至少含一個a，但不含子串a(chǎn)

5、a的所有a和b的串集。最簡DFA如下:(三) .一字母表 工=a, b，試寫出 工上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。答：正規(guī)式a ( a | b )*(四) .令=a,b，則正規(guī)式a*b|b*a表示的正規(guī)集是什么?答：.(a*b|b*a)=a,b,ab,ba,aab,bba (五) 、構(gòu)造下列正規(guī)式相應(yīng)的 DFA(用狀態(tài)轉(zhuǎn)換圖表示)(1) 0 (0 | 1 ) *1(2) 0*10*10*10*1(3) letter (letter | digit ) *（六）設(shè)有非確定的有自限動機NFA M=（A , B, C, 0, 1 , A , C），其中：（A , 0）=C （A , 1

6、）=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)換圖為11110（七）.編譯程序和咼級語言有什么區(qū)別?用匯編語言或咼級語言編與的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn) 換過的叫目標(biāo)程序，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來 將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機器語言表示的程序。 解釋型編譯程序?qū)⒏呒壵Z言程

7、序的一個語句，先解釋成為一組機器語言的指令， 然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序 止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的”對話”，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快， 在過程中，不能進行人機對話修改。FORTRA晤言就是編譯型高級語言。（八） 編譯程序的工作分為那幾個階段？詞法分析、語法分析和語義分析是對源程序進行的分析（稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合（稱為編譯程序的后端

8、），它們從源程序的中間表示建立起和源程序等價的目標(biāo)程序。（九） 、有窮自動機 M接受字母表 =0,1上所有滿足下述條件的串：每個1都有0直接跟 在右邊。構(gòu)造一個最小的 DFA M及和M等價的正規(guī)式。（十）、 證明正規(guī)式（ab）*a 與正規(guī)式a（ba）*等價 （用構(gòu)造他們的最小的DFA方法）?！敬鸢福骸浚ㄊ唬?、設(shè) =0,1上的正規(guī)集S由倒數(shù)第二個字符為 1的所有字符串組成，請給出該字 集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的DFA （8分）答：構(gòu)造相應(yīng)的正規(guī)式：1）*1（0|1） （3分）NFA: （2 分）確定化：（3分）I0,1,21,21,2,31,21,21,2,31,2,31,2,4

9、1,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4（十二）、處于/*和*/之間的串構(gòu)成注解，注解中間沒有 */。畫出接受這種注解的DFA的狀態(tài)轉(zhuǎn)換圖。（十三）設(shè)有字母表a，b上的正規(guī)式 R=（ab|a） *。構(gòu)造NFA確定化，化簡 （2014A）解：（1）（2）將（1）所得的非確定有限自動機確定化ab-01131221+3+（3）對（2）得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2:（十四）、給定文法GS:S aA|bQ; 2aA|bB|b ; B bD|aQ ; CHaQ|bD|b; DbB|aA ; iaB|bFF bD|aE|b構(gòu)造相應(yīng)的最小的DFA。解：先構(gòu)造其NFA用子集法將NFA確定化：將S、A、Q BZ DZ D B重新命名，分別用0、1、2、3、4、5、6表示。因為3、4中含有 z,所以它們?yōu)榻K態(tài)。令匕=( 0,1,2,5,6 , 3,4)用匕進abS