篇一：

　　一、簡答題

　　1.什么是編譯程序？

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

　　將高級程序設計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。

　　2.請寫出文法的形式定義？

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

　　– 其中Vn表示非終結符號

　　– Vt表示終結符號，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ

　　– S是開始符號，

　　– P是產生式，形如：α→β(α∈V+且至少含有一個非終結符號，β∈V*)

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

　　答：在詞法分析的基礎上，根據語言的語法規則，將單詞符號串分解成各類語法短語(例：

　　程序、語句、表達式)。確定整個輸入串是否構成語法上正確的程序。

　　4.局部優化有哪些常用的技術？

　　答：優化技術1—刪除公共子表達式

　　優化技術2—復寫傳播

　　優化技術3—刪除無用代碼

　　優化技術4—對程序進行代數恒等變換（降低運算強度）

　　優化技術5—代碼外提

　　優化技術6—強度削弱

　　優化技術7—刪除歸納變量

　　優化技術簡介——對程序進行代數恒等變換（代數簡化）

　　優化技術簡介——對程序進行代數恒等變換（合并已知量）

　　5．編譯過程分哪幾個階段？

　　答：邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優化、目

　　標代碼生成。每個階段把源程序從一種表示變換成另一種表示。

　　6. 什么是文法？

　　答：文法是描述語言的語法結構的形式規則。是一種工具，它可用于嚴格定義句子的結構；

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

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

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

　　并對靜態語義進行審查。

　　8.代碼優化須遵循哪些原則？

　　答：等價原則：不改變運行結果

　　有效原則：優化后時間更短，占用空間更少

　　合算原則：應用較低的代價取得較好的優化效果

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

　　答：

　　逐個讀入源程序字符并按照構詞規則切分成一系列單詞

　　任務：讀入源程序，輸出單詞符號

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

　　— 追蹤換行標志，指出源程序出錯的行列位置

　　— 宏展開，……

　　10.什么是符號表？

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

　　的類型和特征等相關信息。這些信息一般以表格形式存儲于系統中。如常數表、變量名表、數組名表、過程名表、標號表等等，統稱為符號表。對于符號表組織、構造和管理方法的好壞會直接影響編譯系統的運行效率。

　　11.什么是屬性文法？

　　答：是在上下文無關文法的基礎上，為每個文法符號(含終結符和非終結符)配備若干個屬

　　性值，對文法的每個產生式都配備了一組屬性計算規則(稱為語義規則)。在語法分析過程中，完成語義規則所描述的動作，從而實現語義處理。

　　12.什么是基本塊

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

　　是其第一個語句，出口是其最后一個語句。

　　13.代碼優化階段的功能是什么？

　　答：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高效(時間和空間)。

　　14.文法分哪幾類？

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

　　０型文法(短文文法)： G的每個產生式αβ滿足：α∈V+且α中至少含有一個非終結符,β∈V*

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

　　２型文法(上下文無關文法)：G的每個產生式為Aβ, A是一非終結符，β∈V*

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

　　15.循環優化常用的技術有哪些？

　　答：代碼外提；強度削弱；刪除歸納變量。

　　16.什么是算符優先文法？

　　答：算符文法G的任何終結符a,b之間要么沒有優先關系，若有優先關系,

　　至多有

　　中的一種成立,則G為一算符優先文法。

　　二、計算題

　　（一）推導、最左推導、最右推導和語法樹,復習表達式文法及相關例題。

　　1. 表達式的推導

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

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

　　答：表達式(i)和(i+i)*i的推導：

　　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的最左推導過程：

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

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

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

　　2．語法樹

　　例：對文法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)

　　（二）給定語言求文法

　　（三）逆波蘭式

篇二：

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

　　解釋程序：邊解釋邊執行源程序的程序。區別：編譯程序有中間代碼，而解釋程序沒有。 編譯過程的五個階段：

　　1、 詞法分析 任務：對構成源程序的字符串進行掃描和分解，識別出一個個單詞。

　　2、 語法分析 任務：在詞法分析的基礎上，根據語言規則，把單詞符號串分解成各類語法

　　單位。

　　3、 語義分析和中間代碼產生 任務：對語法分析所識別出的各類語法范疇，分析其含義，

　　并進行初步翻譯。

　　4、 優化 任務：對前段產生的中間代碼進行加工變換，以期在最后階段能產生出更為高效

　　的目標代碼。

　　5、 目標代碼生成 任務：把中間代碼變換成特定機器上的低級語言代碼。

　　編譯程序的七個部分詞法分析器，語法分析器、語義分析與中間代碼產生器、優化器、目標代碼生成器、表格管理和出錯處理。

　　編譯程序生成的五個辦法：機器語言、高級語言、移植、自編譯方式和使用工具自動生成。 詞法規則：指單詞符號的形成規則。（也就是正規式）

　　語法規則：規定了如何從單詞符號形成更大的結構。就是語法單位的形成規則。 空字：不包含任何符號的序列。

　　閉包：中所有的符號組成的集合。

　　上下文無關文法是指：所定義的語法范疇是完全獨立于這種范疇可能出現的環境的文法。 上下文無關文法的四個組成部分：一組終結符號、一組非終結符號、一個開始符號和一組產生式。

　　終結符號也就是不可再分的基本符號。

　　非終結符號是用來代表語法范疇，表示一定符號串的集合。

　　開始符號是語言中我們最感興趣的語法范疇。

　　產生式是定義語法范疇的書寫規則。

　　句子：文法中從開始符號推導的終結符號串。

　　句型：從開始符號推導的符號串。

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

　　程序語言的單詞符號分為五種：關鍵字、標識符、常數、運算符和界符。

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

　　正規式的運算符有三種：或，連接和閉包。優先順序是：閉包，連接，或。

　　DFA怎么識別字：若存在一條從初態結點到某一終態結點的通路，且這條通路上所有弧的標記符連接成的字是a，則稱a可為DFA所識別。

　　DFA怎么識別空字：若DFA的初態結點同時又是終態結點，則空字可為DFA所識別。 NFA怎么識別字：若存在一條從某一初態結點到終態結點的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱a可為NFA識別。

　　NFA怎么識別空字：若M的某些結點即是初態又是終態結點，或者存在一條從某個初態結點到某個終態結點的空通路，那么，空字可為M所識別。

　　語言的語法結構是用上下文無關文法描述的。

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

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

　　為什么消除左遞歸？因為含有左遞歸的文法將自上而下分析的過程陷入無限循環。 為什么消除回溯？因為回溯統一做一大堆無效的工作。

　　自下而上分析法：從輸入串開始，逐步進行歸約，知道歸約到文法的開始符號。 短語：符號串推導過程中某非終結符推導的部分。

　　直接短語：符號串推導過程中某非終結符一步推導的部分。

　　句柄：一個句型的最左直接短語。

　　最左歸約是最有推導的逆過程。

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

　　中間語言的好處：1.便于進行與機器無關的代碼優化工作。2.使編譯程序改變目標機更容易。

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