編譯原理》習(xí)題（一）一一詞法分析是非題（請在括號內(nèi)，正確的劃錯誤的劃X）TOC\o"1-5"\h\z1編譯程序是對高級語言程序的解釋執(zhí)行。 （X一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （X）9.兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 （X）二、選擇題1.詞法分析器的輸岀結(jié)果是 oA.（）記號 B.（）相應(yīng)條目在符號表屮的位置C.（）記號和屬性二元組 D.（）屬性值2.正規(guī)式2.正規(guī)式M1和M2等價是指 A. （）Ml和M2的狀態(tài)數(shù)相等C. （）Ml和M2所識別的語言集相等B. （）Ml和M2的有向邊條數(shù)相等D. （）Ml和M2狀態(tài)數(shù)和有向邊條數(shù)相等語言是A?句子的集合 B?產(chǎn)生式的集合C.符號串的集合 D.句型的集合編譯程序前三個階段完成的工作是A?詞法分析、語法分析和代碼優(yōu)化B?代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語法分析、語義分析和中間代碼生成D?詞法分析、語法分析和代碼優(yōu)化5.掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即C.句子D.句型A.字符B.單詞6.構(gòu)造編譯程序應(yīng)掌握A.（）源程序B? (）目標語言C.（）編譯方法D. (）以上二項都是7?詞法分析的任務(wù)是A?識別單詞B.分析句子的含義C.識別句子D?生成目標代碼三、填空題1?計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋—和—編譯_。3.編譯過程可分為 （詞法分析），（語法分析），（語義分析與中間代碼生成），（優(yōu)化）和（目標代碼生成）五個階段。6.掃描器的任務(wù)是從（源程序中）中識別出一個個（單詞符號）。17.—張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認為是（初）態(tài)；而且實際上至少要有一個（終）態(tài)。1.編譯程序首先要識別出源程序中每個 （單詞），然后再分析每個（句子）并翻譯其意義。3.通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（分析），中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的 （綜合）。對編譯程序而言，輸入數(shù)據(jù)是（源程序），輸出結(jié)果是（目標程序）。四、名詞解釋題：1詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示（token）,送給語法分析程序。

13?掃描器 執(zhí)行詞法分析的程序o五、簡答題（一） 、描述由正規(guī)式b*@bb*）*@）定義的語言，并畫出接受該語言的最簡 DFAo答：由正規(guī)式b*（abb*）*@|）定義的語言是字母表{a,b}上不含子串觀的所有串的集合。最簡DFA如下：、描述由正規(guī)式b、描述由正規(guī)式bDFAo(二)a（bba）b定義的語言，并畫出接受該語言的最簡答:正規(guī)式ba（bba）方體現(xiàn)的特點是，每個a的左邊都有若干b,除非a是第一個字母。該正規(guī)式定義的語言是：至少含一個 a,但不含子串a(chǎn)a的所有a和b的串集。最簡DFA如（三）.一字母表工=4,b},試寫出工上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。答：正規(guī)式a(ab)*o(四)?令》={a,b},則正規(guī)式a*b|b*a表示的正規(guī)集是什么?(四)答:?(a*bb*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*1letter(letter■digit)*

o<* 0> 0?⑶(六) ?設(shè)有非確定的有自限動機NFAM=({A,B,C},(0,1},:,{A},{C}),其中：、?必，0)二{C}..(Af1)={A,B}J.(B,1)二{C}(C,l)={C}o請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：501ACA,BB0CC'0C狀態(tài)轉(zhuǎn)換圖為.編譯程序和高級語言有什么區(qū)別？用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標程序(這個過程即編譯) ，才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標程序，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的”對話”，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。 FORTRAN語言就是編譯型高級語言。?編譯程序的工作分為那幾個階段？

詞法分析、語法分析和語義分析是對源程序進行的分析 （稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合 （稱為編譯程序的后端），它們從源程序的屮間表示建立起和源程序等價的目標程序。（九卜有窮自動機M接受字母表Z={0,1}±所有滿足下述條件的串： 每個1都有0直接跟在右邊。構(gòu)造一個最小的DFAM及和M等價的正規(guī)式。最小的DFAM如下圖所示:（十卜證明正規(guī)式（ab）畑與正規(guī)式a（ba）*等價（用構(gòu)造他們的最小的 DFA方法）。【答案：1這兩個正規(guī)式最純都可得到最簡的DFA如圖所示.所以這兩個正規(guī)式等價。 3這兩個正規(guī)式最純都可得到最簡的DFA如圖所示.所以這兩個正規(guī)式等價。 3（十一）、設(shè)*{0,1}上的正規(guī)集S由倒數(shù)第二個字符為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的 DFAo（8分）答：構(gòu)造相應(yīng)的正規(guī)式： ⑼1）*1（01） （3分）NFA: （2分丿1100確定化：（3011011II011{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}:{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}DFA的（十二）、處于/*和狀*/DFA的(2014A)（H）設(shè)有字母表｛a,b｝上的止規(guī)式R二（aba）*。構(gòu)造NFA,確定化，化簡解：（1）(2014A)->+e￡匚丿a（2）將（1）所得的非確定有限自動機確定化￡ab-011312

21+3a(3)對(2)得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2：a(3)對(2)得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2：(十四)、給定文法G[S]：S—aA|bQ;A—aA|bB|b;B—bD|aQF—bD|aE|b構(gòu)造相應(yīng)的最小的DFA。解：先構(gòu)造其NFA:;CHaQbDb;DbBaA;E—aBbFabSAQAABZQQDZBZQDDZABDABBQD用子集法將NFA確定化:分別用0、1、2、3、4、5、6表示。因為將S、A、Q、BZ、DZ、D、B重新命名,3、4中含有z,所以它們?yōu)榻K態(tài)。baba令P°=({0,12