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

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

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

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

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

5、序。中間代碼一般是一種機(jī)器無(wú)關(guān)的表示形式，只有把它再翻譯成與機(jī)器硬件直接相關(guān)的機(jī)器能識(shí)別的語(yǔ)言，即目標(biāo)程序，才能在機(jī)器上運(yùn)行。表格管理模塊保持一系列的表格，登記源程序的各類(lèi)信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個(gè)階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個(gè)編譯過(guò)程都在不斷地和表格打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)集合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）。這時(shí)不能再劃分了，得到的最小化的有限狀態(tài)自動(dòng)機(jī)如表3.2所示：表2.2最小化的有限狀態(tài)自動(dòng)機(jī)ab?ABCCBEBDCDDDAccept4某程序語(yǔ)言的無(wú)（正負(fù)）符號(hào)常數(shù)可以用下面正則表達(dá)式R來(lái)表示：（DE|D.

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

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

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