編譯原理課后習(xí)題答案

1、第一章第一章1解答：程序設(shè)計語言：程序設(shè)計語言是遵守一定規(guī)范的、描述“計算”（Computing）過程的形式語言。一般可以劃分為低級語言和高級語言兩大類。低級語言是面向機器的語言，它是為特定的計算機系統(tǒng)設(shè)計的語言，機器指令、匯編語言是低級語言。高級語言是與具體計算機無關(guān)的“通用”語言，它更接近于人類的自然語言和數(shù)學(xué)表示，例如FTRAN、Pal、C等等我們熟悉的語言是高級語言。語言處理程序：由于目前的計算機只能理解和執(zhí)行機器語言，因此必須

2、有一個程序?qū)⒂贸绦蛟O(shè)計語言書寫的程序等價（執(zhí)行效果完全一致）地轉(zhuǎn)換為計算機能直接執(zhí)行的形式，完成這一工作的程序稱為“語言處理程序”。它一般可分為解釋程序和翻譯程序兩大類。翻譯程序：翻譯程序(Translat)是一種語言處理程序，它將輸入的用程序設(shè)計語言書寫的程序（稱為源程序）轉(zhuǎn)換為等價的用另一種語言書寫的程序（稱為目標(biāo)程序）。若源語言是匯編語言，目標(biāo)程序是機器語言，稱這種翻譯程序為匯編程序。若源語言是高級語言，目標(biāo)程序是低級語言，稱這種

3、翻譯程序為編譯程序。解釋程序：解釋程序（Interpreter）是一種語言處理程序，它對源程序逐個語句地進(jìn)行分析，根據(jù)每個語句的含義執(zhí)行語句指定的功能。2解答：編譯程序的總框圖見圖1.2。其中詞法分析器，又稱掃描器，它接受輸入的源程序，對源程序進(jìn)行詞法分析，識別出一個個的單詞符號，其輸出結(jié)果是單詞符號。語法分析器，對單詞符號串進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或歸約），識別出程序中的各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序

4、”。語義分析及中間代碼產(chǎn)生器，按照語義規(guī)則對語法分析器歸約出（或推導(dǎo)出）的語法單位進(jìn)行語義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒有中間代碼形式，而直接生成目標(biāo)代碼。優(yōu)化器對中間代碼進(jìn)行優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代碼的優(yōu)化，其過程實際上是對中間代碼進(jìn)行等價替換，使程序在執(zhí)行時能更快，并占用更小的空間。目標(biāo)代碼生成器把中間代碼翻譯成目標(biāo)程

5、序。中間代碼一般是一種機器無關(guān)的表示形式，只有把它再翻譯成與機器硬件直接相關(guān)的機器能識別的語言，即目標(biāo)程序，才能在機器上運行。表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個編譯過程都在不斷地和表格打交道。出錯處理程序?qū)Τ霈F(xiàn)在源程序中的錯誤進(jìn)行處理。如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報集合DEFG不需要進(jìn)一

6、步劃分，考察子集ABC。由于?（Ba）=D?DEFG，而?（Aa）＝?（Ca）＝B?ABC，因此Q可進(jìn)一步劃分為：（ACBDEFG）。由于?（Ab）＝C?AC，而?（C，b）＝E?DEFG。因此Q可進(jìn)一步劃分為：（ACBDEFG）。這時不能再劃分了，得到的最小化的有限狀態(tài)自動機如表3.2所示：表2.2最小化的有限狀態(tài)自動機ab?ABCCBEBDCDDDAccept4某程序語言的無（正負(fù)）符號常數(shù)可以用下面正則表達(dá)式R來表示：（DE|D.

7、DE|E|.DE）((|)D|D)D|D|D.D⑴試把它轉(zhuǎn)換成確定性有限狀態(tài)自動機。⑵把上述有限狀態(tài)自動機最小化。⑶在上述有限狀態(tài)自動機中添加相應(yīng)動作，取出無（正負(fù)）符號常數(shù)。分析：從正則表達(dá)式構(gòu)造有限狀態(tài)自動機可以分兩步進(jìn)行。①畫一條從結(jié)點X到結(jié)點Y的有向弧，有向弧上標(biāo)以正則表達(dá)式R。結(jié)點X為標(biāo)以“－”的初始狀態(tài)，結(jié)點Y為標(biāo)以“＋”的最終狀態(tài)。從這一有向圖出發(fā)反復(fù)應(yīng)用圖3.2所示的替代規(guī)則，直至所有有向弧都以VT中的符號或標(biāo)記?為止。

8、圖2.23條替代規(guī)則②消除應(yīng)用①所得到的傳遞圖中的ε弧，可以分為兩步：首先消除ε環(huán)路，其次消除其他ε弧。a)ε環(huán)路的消除方法：i將ε環(huán)路的諸項合并為一個頂點。ii修改各個相關(guān)的有向弧。iii若ε環(huán)路中某一狀態(tài)是最終（或初始）狀態(tài)，則新頂點是最終（或初始）狀態(tài)。b)其它ε弧的消除有兩種方法：1）子集法：即計算εClosure（T），其表示從狀態(tài)集T中任何一狀態(tài)沿ε弧可以到達(dá)的狀態(tài)全體。其要點是：從初始狀態(tài)q0的X=εClosure（q0）

9、開始，按如下方法構(gòu)造狀態(tài)集：i令Set＝X；ii若Set中還有未考察過的狀態(tài)子集Xi，則對于每一輸入符號a?VT，求T=εClosure（move（Xia）），Set=Set∪T（其中move(Xia)=q|q?δ(pa)p?Xi）。重復(fù)執(zhí)行（2），直至不存在這樣的Xi。這樣得到的Set即為消除ε弧后的確定的有限狀態(tài)機（DFA）。DFA的初始狀態(tài)就是εClosure（q0），最終狀態(tài)由那些至少含有一個最終狀態(tài)的狀態(tài)子集組成。2）逐步消除