篇一：

　　一、簡答題

　　1.什么是編譯程序？

　　答：編譯程序是一種將高級(jí)語言程序(源程序)翻譯成低級(jí)語言(目標(biāo)程序)的程序 。

　　將高級(jí)程序設(shè)計(jì)語言程序翻譯成邏輯上等價(jià)的低級(jí)語言(匯編語言,機(jī)器語言)程序的翻譯程序。

　　2.請(qǐng)寫出文法的形式定義？

　　答：一個(gè)文法G抽象地表示為四元組 G=（Vn,Vt,P,S）

　　– 其中Vn表示非終結(jié)符號(hào)

　　– Vt表示終結(jié)符號(hào)，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ

　　– S是開始符號(hào)，

　　– P是產(chǎn)生式，形如：α→β(α∈V+且至少含有一個(gè)非終結(jié)符號(hào)，β∈V*)

　　3.語法分析階段的功能是什么？

　　答：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號(hào)串分解成各類語法短語(例：

　　程序、語句、表達(dá)式)。確定整個(gè)輸入串是否構(gòu)成語法上正確的程序。

　　4.局部優(yōu)化有哪些常用的技術(shù)？

　　答：優(yōu)化技術(shù)1—?jiǎng)h除公共子表達(dá)式

　　優(yōu)化技術(shù)2—復(fù)寫傳播

　　優(yōu)化技術(shù)3—?jiǎng)h除無用代碼

　　優(yōu)化技術(shù)4—對(duì)程序進(jìn)行代數(shù)恒等變換（降低運(yùn)算強(qiáng)度）

　　優(yōu)化技術(shù)5—代碼外提

　　優(yōu)化技術(shù)6—強(qiáng)度削弱

　　優(yōu)化技術(shù)7—?jiǎng)h除歸納變量

　　優(yōu)化技術(shù)簡介——對(duì)程序進(jìn)行代數(shù)恒等變換（代數(shù)簡化）

　　優(yōu)化技術(shù)簡介——對(duì)程序進(jìn)行代數(shù)恒等變換（合并已知量）

　　5．編譯過程分哪幾個(gè)階段？

　　答：邏輯上分五個(gè)階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目

　　標(biāo)代碼生成。每個(gè)階段把源程序從一種表示變換成另一種表示。

　　6. 什么是文法？

　　答：文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。是一種工具，它可用于嚴(yán)格定義句子的結(jié)構(gòu)；

　　用有窮的規(guī)則刻劃無窮的集合；文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式；文法描述語言的時(shí)候不考慮語言的含義。

　　7. 語義分析階段的功能是什么？

　　答：對(duì)語法分析所識(shí)別出的各類語法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)；

　　并對(duì)靜態(tài)語義進(jìn)行審查。

　　8.代碼優(yōu)化須遵循哪些原則？

　　答：等價(jià)原則：不改變運(yùn)行結(jié)果

　　有效原則：優(yōu)化后時(shí)間更短，占用空間更少

　　合算原則：應(yīng)用較低的代價(jià)取得較好的優(yōu)化效果

　　9.詞法分析階段的功能是什么？

　　答：

　　逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞

　　任務(wù)：讀入源程序，輸出單詞符號(hào)

　　— 濾掉空格，跳過注釋、換行符

　　— 追蹤換行標(biāo)志，指出源程序出錯(cuò)的行列位置

　　— 宏展開，……

　　10.什么是符號(hào)表？

　　答：符號(hào)表在編譯程序工作的過程中需要不斷收集、記錄和使用源程序中一些語法符號(hào)

　　的類型和特征等相關(guān)信息。這些信息一般以表格形式存儲(chǔ)于系統(tǒng)中。如常數(shù)表、變量名表、數(shù)組名表、過程名表、標(biāo)號(hào)表等等，統(tǒng)稱為符號(hào)表。對(duì)于符號(hào)表組織、構(gòu)造和管理方法的好壞會(huì)直接影響編譯系統(tǒng)的運(yùn)行效率。

　　11.什么是屬性文法？

　　答：是在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(含終結(jié)符和非終結(jié)符)配備若干個(gè)屬

　　性值，對(duì)文法的每個(gè)產(chǎn)生式都配備了一組屬性計(jì)算規(guī)則(稱為語義規(guī)則)。在語法分析過程中，完成語義規(guī)則所描述的動(dòng)作，從而實(shí)現(xiàn)語義處理。

　　12.什么是基本塊

　　答：是指程序中一順序執(zhí)行的語句序列，其中只有一個(gè)入口語句和一個(gè)出口語句，入口

　　是其第一個(gè)語句，出口是其最后一個(gè)語句。

　　13.代碼優(yōu)化階段的功能是什么？

　　答：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為高效(時(shí)間和空間)。

　　14.文法分哪幾類？

　　答：文法有四種:設(shè)有G=(Vn,Vt,P,S),不同類型的文法只是對(duì)產(chǎn)生式的要求不同：

　?。靶臀姆?短文文法)： G的每個(gè)產(chǎn)生式αβ滿足：α∈V+且α中至少含有一個(gè)非終結(jié)符,β∈V*

　　１型文法(上下文有關(guān)文法)：如果G的每個(gè)產(chǎn)生式αβ均滿足|β|>=|α|,僅當(dāng)Ｓε除外，但S不得出現(xiàn)在任何產(chǎn)生式的右部

　　２型文法(上下文無關(guān)文法)：G的每個(gè)產(chǎn)生式為Aβ, A是一非終結(jié)符，β∈V*

　　３型文法(正規(guī)文法)：G的每個(gè)產(chǎn)生式的形式都是：AαB或Aα，其中A,B是非終結(jié)符，α是終結(jié)符串。(右線性文法)。

　　15.循環(huán)優(yōu)化常用的技術(shù)有哪些？

　　答：代碼外提；強(qiáng)度削弱；刪除歸納變量。

　　16.什么是算符優(yōu)先文法？

　　答：算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,

　　至多有

　　中的一種成立,則G為一算符優(yōu)先文法。

　　二、計(jì)算題

　?。ㄒ唬┩茖?dǎo)、最左推導(dǎo)、最右推導(dǎo)和語法樹,復(fù)習(xí)表達(dá)式文法及相關(guān)例題。

　　1. 表達(dá)式的推導(dǎo)

　　例： G = ({E}, {i, +, *, (, ) } , P , E)

　　P： E E+E | E*E | (E) | i

　　答：表達(dá)式(i)和(i+i)*i的推導(dǎo)：

　　E (E) (i)

　　E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i

　　E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i

　　(i+i)*i的最左推導(dǎo)過程：

　　E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i

　　(i+i)*i的最右推導(dǎo)過程：

　　E E*E E*i (E + E)*i (E+ i)*i (i + i)*i

　　2．語法樹

　　例：對(duì)文法G = ({E}, {i, +, *, (, ) } , P , E)

　　P： E E + E | E * E | ( E ) | i

　　答： 句子(i+i)*i 的語法樹：

　　例： G = ({E}, {i, +, *, (, ) } , P , E)

　　P： E E + E | E * E | ( E ) | i

　　答：句子 ( i * i + i)的語法樹：

　　(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)

　?。ǘ┙o定語言求文法

　?。ㄈ┠娌ㄌm式

篇二：

　　翻譯程序:把一種語言程序轉(zhuǎn)換成另一種語言程序，且在功能上是相同的這樣的程序。 編譯程序：把高級(jí)語言轉(zhuǎn)換成低級(jí)語言，且在功能上是相同的這樣的程序。

　　解釋程序：邊解釋邊執(zhí)行源程序的程序。區(qū)別：編譯程序有中間代碼，而解釋程序沒有。 編譯過程的五個(gè)階段：

　　1、 詞法分析 任務(wù)：對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞。

　　2、 語法分析 任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言規(guī)則，把單詞符號(hào)串分解成各類語法

　　單位。

　　3、 語義分析和中間代碼產(chǎn)生 任務(wù)：對(duì)語法分析所識(shí)別出的各類語法范疇，分析其含義，

　　并進(jìn)行初步翻譯。

　　4、 優(yōu)化 任務(wù)：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效

　　的目標(biāo)代碼。

　　5、 目標(biāo)代碼生成 任務(wù)：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼。

　　編譯程序的七個(gè)部分詞法分析器，語法分析器、語義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標(biāo)代碼生成器、表格管理和出錯(cuò)處理。

　　編譯程序生成的五個(gè)辦法：機(jī)器語言、高級(jí)語言、移植、自編譯方式和使用工具自動(dòng)生成。 詞法規(guī)則：指單詞符號(hào)的形成規(guī)則。（也就是正規(guī)式）

　　語法規(guī)則：規(guī)定了如何從單詞符號(hào)形成更大的結(jié)構(gòu)。就是語法單位的形成規(guī)則。 空字：不包含任何符號(hào)的序列。

　　閉包：中所有的符號(hào)組成的集合。

　　上下文無關(guān)文法是指：所定義的語法范疇是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的文法。 上下文無關(guān)文法的四個(gè)組成部分：一組終結(jié)符號(hào)、一組非終結(jié)符號(hào)、一個(gè)開始符號(hào)和一組產(chǎn)生式。

　　終結(jié)符號(hào)也就是不可再分的基本符號(hào)。

　　非終結(jié)符號(hào)是用來代表語法范疇，表示一定符號(hào)串的集合。

　　開始符號(hào)是語言中我們最感興趣的語法范疇。

　　產(chǎn)生式是定義語法范疇的書寫規(guī)則。

　　句子：文法中從開始符號(hào)推導(dǎo)的終結(jié)符號(hào)串。

　　句型：從開始符號(hào)推導(dǎo)的符號(hào)串。

　　語言：文法中所有句子的集合。

　　程序語言的單詞符號(hào)分為五種：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符和界符。

　　二元式表示：（種類，屬性）

　　正規(guī)式的運(yùn)算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。

　　DFA怎么識(shí)別字：若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字是a，則稱a可為DFA所識(shí)別。

　　DFA怎么識(shí)別空字：若DFA的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字可為DFA所識(shí)別。 NFA怎么識(shí)別字：若存在一條從某一初態(tài)結(jié)點(diǎn)到終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字等于a，則稱a可為NFA識(shí)別。

　　NFA怎么識(shí)別空字：若M的某些結(jié)點(diǎn)即是初態(tài)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的空通路，那么，空字可為M所識(shí)別。

　　語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。

　　語法分析分為兩類：自上而下分析法，自下而上分析法。

　　自上而下分析法面臨的問題：1.文法的左遞歸問題。2.回溯3.成功可能是暫時(shí)的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯(cuò)的確切位置。5.效率低，代價(jià)高。

　　為什么消除左遞歸？因?yàn)楹凶筮f歸的文法將自上而下分析的過程陷入無限循環(huán)。 為什么消除回溯？因?yàn)榛厮萁y(tǒng)一做一大堆無效的工作。

　　自下而上分析法：從輸入串開始，逐步進(jìn)行歸約，知道歸約到文法的開始符號(hào)。 短語：符號(hào)串推導(dǎo)過程中某非終結(jié)符推導(dǎo)的部分。

　　直接短語：符號(hào)串推導(dǎo)過程中某非終結(jié)符一步推導(dǎo)的部分。

　　句柄：一個(gè)句型的最左直接短語。

　　最左歸約是最有推導(dǎo)的逆過程。

　　中間語言形式：后綴式，三元式，四元式，間接三元式。

　　中間語言的好處：1.便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作。2.使編譯程序改變目標(biāo)機(jī)更容易。

　　3.使編譯程序的結(jié)構(gòu)在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清晰。