編譯原理(王力紅 著)習(xí)題答案

《編譯原理(王力紅 著)習(xí)題答案》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、習(xí)題11-1說明解釋程序和編譯程序的區(qū)別。答：通常，翻譯程序可分為解釋程序、匯編程序和編譯程序。所謂解釋程序是一種將源程序按動態(tài)順序逐句進(jìn)行分析解釋編譯，邊解釋邊執(zhí)行、不產(chǎn)生目標(biāo)程序的一種翻譯程序。這種翻譯程序結(jié)構(gòu)簡單、占用內(nèi)存較少，易于在執(zhí)行過程中對源程序進(jìn)行修改，但工作效率低，只適合一些規(guī)模較小的語言，如解釋BASIC等。而編譯程序（也稱編譯器）是源語言為某種高級語言，目標(biāo)語言為相應(yīng)于某一計算機的匯編語言或機器語言的一種翻譯程序。這種編譯程序?qū)⒃闯绦蚍g成執(zhí)行時可完全獨立于源程序的經(jīng)優(yōu)化的目標(biāo)語言代碼，因而運行效率高。更為重要的是，它使工

2、作于高級語言環(huán)境下的程序設(shè)計人員，不必考慮與機器有關(guān)的繁瑣細(xì)節(jié)，卻能完成機器語言所能完成的絕大多數(shù)工作。在解釋方式下，并不生成目標(biāo)代碼，而是直接執(zhí)行源程序本身。這是編譯方式與解釋方式的根本區(qū)別。1-2簡述高級語言程序按編譯方式的執(zhí)行過程。答：高級語言程序按編譯方式的執(zhí)行過程一般可分為兩個階段：編譯階段和運行階段。其中，編譯階段完成由源程序到目標(biāo)程序的翻譯，若目標(biāo)程序是匯編語言程序，還需再通過匯編程序進(jìn)一步翻譯成機器語言程序。而運行階段的任務(wù)是在目標(biāo)計算機上執(zhí)行編譯階段所得到的目標(biāo)程序。但目標(biāo)程序往往不能由計算機直接執(zhí)行，一般還應(yīng)有運行系統(tǒng)進(jìn)行

3、配合，這個運行系統(tǒng)包括鏈接程序和由這樣一些子程序組成的系統(tǒng)庫，如標(biāo)準(zhǔn)函數(shù)計算子程序、數(shù)組動態(tài)存儲子程序等。由鏈接程序?qū)⒛繕?biāo)程序和系統(tǒng)庫連接在一起，最終形成一個可執(zhí)行程序，在計算機上直接執(zhí)行。1-3什么是編譯系統(tǒng)？答：通常將編譯程序、鏈接程序、系統(tǒng)庫、源程序編輯程序等軟件組成的系統(tǒng)稱為編譯系統(tǒng)。1-4編譯過程通常有哪幾個階段？簡述各階段的主要任務(wù)。答：程序設(shè)計語言的編譯過程一般可以分為詞法分析、語法分析、語義分析和中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成5個階段。詞法分析是編譯過程的第一個階段。該階段的主要任務(wù)是從構(gòu)成源程序的字符串中識別出一個個具

4、有獨立意義的最小語法單位——單詞，并指出其屬性。語法分析階段的主要任務(wù)是在詞法分析的基礎(chǔ)上，根據(jù)相應(yīng)程序設(shè)計語言的語法規(guī)定進(jìn)行語法分析，在源程序的單詞串中識別出各種語法成分，如“程序”、“語句”、“表達(dá)式”等，并確定整個輸入串是否構(gòu)成一個語法上正確的程序，檢查出語法錯誤。語義分析和中間代碼生成階段的主要任務(wù)有兩個，其一是進(jìn)行相應(yīng)的語義檢查，以保證源程序在語義上的正確性，其二是確定各語法成分的含義、用途，收集類型信息，確定應(yīng)進(jìn)行的運算和操作，并將其轉(zhuǎn)換為某種內(nèi)部表示形式，即生成中間代碼。代碼優(yōu)化階段是編譯過程的最后階段。這一階段的任務(wù)是對上一階

5、段產(chǎn)生的中間代碼進(jìn)行變換和改造，以期獲得高質(zhì)量的目標(biāo)代碼。目標(biāo)代碼生成階段的任務(wù)是把優(yōu)化后的中間代碼轉(zhuǎn)換成特定機器上的絕對指令代碼，或可重定位的指令代碼，或匯編指令代碼。由于這種轉(zhuǎn)換工作與具體的目標(biāo)計算機的系統(tǒng)結(jié)構(gòu)及其指令系統(tǒng)有關(guān)，涉及各種變量的存儲空間分配、寄存器的調(diào)度、各種硬件功能部件的使用等，因此工作比較復(fù)雜。1-5什么是編譯程序的遍？對編譯程序來說，遍多和遍少各有什么優(yōu)缺點？所謂一遍（pass）或一趟，是指在編譯過程中對源程序或與之等價的中間程序從頭到尾掃描一遍，并將其轉(zhuǎn)換成下一個中間程序的整個過程。答：編譯程序按其掃描次數(shù)可分為單遍

6、（趟）掃描和多遍（趟）掃描。采用多遍掃描方式，各遍的工作分工明確，便于多人合作開發(fā)，縮短開發(fā)周期，同時節(jié)省運行時的內(nèi)存空間，易于提高目標(biāo)程序的質(zhì)量。但各遍之間的重復(fù)工作多，編譯效率低。而單遍（趟）掃描的編譯程序，編譯速度快、效率高，但運行時占用空間大，目標(biāo)程序質(zhì)量低。1-6一個最簡單的編譯程序至少要包含哪幾個組成部分（程序）？答：至少要包含詞法分析程序、語法分析程序、目標(biāo)代碼生成程序等3個組成部分（程序）。習(xí)題22-3已知算術(shù)表達(dá)式文法G[E]：E→E+T

7、TT→T*F

8、FF→(E)

9、i求符號串i*i的最左推導(dǎo)、最右推導(dǎo)、最左歸約、最右歸約。

10、解：最左推導(dǎo)：E=>T=>T*F=>F*F=>i*F=>i*i最右推導(dǎo)：E=>T=>T*F=>T*i=>F*i=>i*i最左歸約：i*i=>F*i=>T*i=>T*F=>T=>E最右歸約：i*i=>i*F=>F*F=>T*F=>T=>E2-4設(shè)有文法G[A]：A→bA

11、cc判斷符號串bbc，bbbcc，bbA，bbAc是否是G[A]的句型或句子。解答：∵A=>bA=>bbA=>bbbA=>bbbcc∴bbA是G[A]的句型,bbbcc是G[A]的句子，bbAc不是G[A]的句型,bbc不是G[A]的句子。2-5分別求下列文法所描述的語言：①G

12、1[S]：S→aaSbb

13、e解答：∵S=>aaSbb=>aaaaSbbbb=>…∴L(G1[S])={a2nb2n

14、n≥0}②G2[S]：S→10S0

15、aAA→bA