一、簡答題
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 = (, , , {ip , 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)
（二）給定語言求文法
（三）逆波蘭式
（四）將for語句和if語句翻譯成相應的四元式序列
(五) 短語、素短語、最左素短語，firstvt集和lastvt集的求解方法
(複習第四章算符優先文法相關內容)
1. 短語、素短語、最左素短語
集和lastvt集的求解方法
例：設文法為：
e' →#e#；t→f；e→e+t；f→p↑f | p； e→t ；p→(e)；t→t*f；p→i；
3. 算符優先文法
優先關係的定義:
算符優先文法的定義:
三、綜合題
的確定化和最小化(參看課件第三章62頁：例5)
2.自頂向下分析(參看課件第四章（1）67頁：綜合練習)
例：求對應於下述文法的**分析表: e te'
e' +te' |ε
t ft'
t' *ft' |ε
f (e) |i
答：1） 首先求first集:
2） 由於ε first(e'), ε first(t'), 求e'和t'的follow集:
3） 根據集合的值填表，得到:
例:設文法g(s)：s→(l) | as | a
l→l，s | s
(1) 消除左遞迴和回溯；
(2) 計算每個非終結符的first和follow集；
(3) 構造**分析表。
答：(1) 消除左遞迴和回溯：
(2)(3)構造**分析表：
分析方法(參看課件第四章（3）28頁及30頁)
(附)1.短語、直接短語、控制代碼
例：考慮如下文法： e =>t | e+t
t =>f | t*f
f =>i | (e)
求句型 i1 * i2 + i3的短語、直接短語和控制代碼
答：e => f * i2 + i3 e => i1 * f + i3e => i1 * i2 + f
e => t + i3（t =>t*f =>i1 * i2） f=>i
e => i1 * i2 + i3
因此： 短語有：i1, i2, i3, i1*i2, i1*i2+i3
直接短語有：i1, i2 , i3
控制代碼是： i1
i2 + i3 不是短語，因為e => i1 * e （e =>i2 +i3）
2. 什麼是語法制導翻譯
語法制導翻譯：定義翻譯所必須的語義屬性和語義規則，一般不涉及計算順序。
語法制導翻譯(syntax-directed translations)：
– 乙個句子的語義翻譯過程與語法分析過程同時進行。
在文法中，文法符號有明確的意義，文法符號之間有確定的語義關係。屬性描述語義資訊，語義規則描述屬性間的的關係，將語義規則與語法規則相結合，在語法分析的過程中計算語義屬性值。
編譯原理期末總結
第一章編譯概述 程式的翻譯 源程式 用組合語言或高階語言編寫的程式。目標程式 用目標語言所表示的程式。目標語言 可以是介於源語言和機器語言之間的中間語言，可以是某種機器的機器語言，也可以是某機器的組合語言 翻譯程式 將源程式轉換為目標程式的程式稱為翻譯程式。它是指各種語言的翻譯器，包括匯程式設計序和...
編譯原理期末複習題
第八節習題 一 單項選擇題 1 將編譯程式分成若干個 遍 是為了 a 提高程式的執行效率 b 使程式的結構更加清晰 c 利用有限的機器記憶體並提高機器的執行效率 d 利用有限的機器記憶體但降低了機器的執行效率 2 構造編譯程式應掌握 a 源程式b 目標語言 c 編譯方法d 以上三項都是 3 變數應當...
編譯原理試卷A 複習卷
編譯原理 課程 a 試卷考試形式閉卷考試用時120分鐘,本試卷共2頁,另 答題紙0張,草稿紙2張一 10分 簡述pl 0編譯程式的基本結構。二 10分 文法g s 為 s ac ab a ab b bc 寫出l g s 的全部元素。三 15分 令文法g e 為 e e t e t t t f t f...