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

《編譯原理(王力紅 著)習(xí)題答案》由會員上傳分享，免費(fèi)在線閱讀，更多相關(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)于某一計(jì)算機(jī)的匯編語言或機(jī)器語言的一種翻譯程序。這種編譯程序?qū)⒃闯绦蚍g成執(zhí)行時可完全獨(dú)立于源程序的經(jīng)優(yōu)化的目標(biāo)語言代碼，因而運(yùn)行效率高。更為重要的是，它使工

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

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

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

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

6、（趟）掃描和多遍（趟）掃描。采用多遍掃描方式，各遍的工作分工明確，便于多人合作開發(fā)，縮短開發(fā)周期，同時節(jié)省運(yùn)行時的內(nèi)存空間，易于提高目標(biāo)程序的質(zhì)量。但各遍之間的重復(fù)工作多，編譯效率低。而單遍（趟）掃描的編譯程序，編譯速度快、效率高，但運(yùn)行時占用空間大，目標(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