編譯原理期末總結復習
篇一：
一、簡答題
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.使編譯程序的結構在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清晰。
篇三：
(1)程序設計語言
機器語言: 由0、1代碼構成，不需翻譯就可直接執行其程序。
匯編語言: 機器指令助記符（偽代碼）形式，匯編后才可執行其程序。
高級程序設計語言: 類自然語言和數學公式形式
(2) 基本術語
源程序(Source Program)：用源語言寫的程序。源語言可以是匯編語言，也可以是高級程
序設計語言。
目標程序(Target Program) ：也稱為“結果程序”，是源程序經翻譯程序加工以后所生成
的程序。目標程序可以用機器語言表示，也可以用匯編語言或其它中間語言表示。
翻譯程序(Translating Program)：是指把一個源程序翻譯成邏輯上等價的目標程序的程序。
源程序為其輸入，目標程序為其輸出。
匯編程序(Assembler)：是指把一個匯編語言寫的源程序轉換成等價的機器語言表示的目
標程序的翻譯程序。
編譯程序(Compiler)：若源程序是用高級程序設計語言所寫，經翻譯程序加工生成目標程
序，則該翻譯程序就稱為“編譯程序”，也可稱為編譯器。
解釋程序：是高級語言翻譯程序的一種，他將源語言書寫的源程序作為輸入，解釋一句
后就提交計算機執行一句，并不形成目標程序，就像外語翻譯中的“口譯”一樣，不產生全文的翻譯文本。
運行系統(Running System)：目標程序執行時，需要有一些子程序（如一些連接裝配程序
及一些連接庫等）配合進行工作，由這些子程序組成的一個子程序庫稱為運行系統。 編譯系統(Compiling System)：編譯程序和運行系統合稱編譯系統。
(3) 程序的翻譯
除機器語言程序外，用其它語言書寫的程序都必須經過翻譯才能被計算機識別。這一過
程由翻譯程序來完成。
編譯方式是一種分階段進行的方式，包括翻譯和運行兩部分。
前一階段：翻譯
后一階段：運行，由運行系統配合完成。
(4) 過程
1、詞法分析階段
這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或符號TOKEN）。
某源程序片斷如下：
begin var sum, first, count: real; sum:=first+count*10 end.
保留字 begin var real end
標識符 sumfirstcountsumfirstcount
界符 .
逗號，逗號,冒號：分號；加號+乘號*賦值號 ：=整數10 10
2、語法分析階段
是編譯過程的第二個階段。語法分析的任務是在詞法分析的基礎上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。一般這種語法短語，也稱語法單位，或語法成分，或語法范疇。
語法分析所依據的是語言的語法規則，即描述程序結構的規則。通過語法分析確定整個輸入串是否構成一個語法上正確的程序。
3、語義分析階段
依據語言的語義規則，對語法分析得到的語法結構分析其含義以及應進行的運算，審查源程序中有無語義錯誤，為代碼生成階段收集類型信息。
4、中間代碼生成
在進行了上述的語法分析和語義分析階段的工作之后，有的編譯程序將源程序轉變成一種內部表示形式，這種內部表示形式叫做中間代碼。
所謂“中間代碼”是一種結構簡單，含義明確的記號系統，這種記號系統可以設計為多種多樣的形式。
重要的設計原則：一是容易生成；二是容易將它翻譯成目標代碼。
5、代碼優化
任務：對前階段產生的中間代碼系列進行變換或改造。目的是使生成的目標代碼更高效，即省時間省空間。例如上例四個四元式可優化為下面兩個四元式。
6、目標代碼生成
任務：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。它的工作與硬件系統結構和指令含義有關。
7、表格管理
編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，因此需要有表格管理的工作；
8、出錯處理
如果編譯過程中發現源程序有錯誤，編譯程度應報告錯誤的性質和錯誤發生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。
(5) 前端與后端
參考上面的圖，目的是為了在多種源語言和多種目標語言的開發過程中，可以靈活搭配組合，消除重復開發的工作量，提高編譯系統的開發效率。
(6) 遍
所謂遍，是對源程序或源程序的中間形式從頭到尾掃視并完成規定任務的過程。
每一遍掃視可完成一個階段或多個階段的功能。
一遍的編譯程序：以語法分析程序為核心 。
多遍掃描的優點：
可以減少內存容量的需求，分遍后，以遍為單位分別調用編譯的各個程序，各遍程序可以相互覆蓋。
可使各遍的編譯程序相互獨立，結構清晰。
能夠進行充分優化，產生高質量的目標程序。
可將編譯程序分為前端和后端，有利于編譯程序的移植。
多遍掃描的缺點
每遍都要讀符號、送符號，增加了許多重復性的工作，降低編譯效率。
(7) 程序設計語言范型（從支持的計算模式）
1. 強制(命令)式語言:是面向動作的，即一個計算過程看做是一系列動作，其動作是命令驅動，以語言形式表示。
也稱過程式語言，如C,FORTRAN等;
2. 函數式語言：注重程序表示的功能
也稱應用式語言，如ML和LISP等；
3. 基于規則的語言：檢查一定的使能條件，滿足時執行動作
也稱邏輯程序設計語言，如PROLOG。
4. 面向對象語言：提供抽象數據類型，支持封裝性、繼承性和多態性。
如C++和Java等。
(1) 符號和符號串
1、 字母表：元素的有窮非空集合。
2、 符號串：由字母表中的符號組成的任何有窮序列。
3、 符號串的頭尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z
的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。 如:設z=abc，那么z的頭是，a, ab, abc, 除abc外，其它都是固有頭；z的尾是, c, bc, abc, z的固有尾是, c, bc。
4、 符號串的運算
（1）符號串的連接：設x和y是符號串，x和y的連接xy是把y的符號寫在x的符號后得的符號串。
如：x=ST, y=abu, 則xy=STabu顯然有x=x=x。
（2）符號串的方冪：設x是符號串，把x自身連接n次得x的幾次方冪xn。
如：設x=ab則x0=x1=abx2=ababx3=ababab
（3）符號串集合的乘積：設A和B為符號串集合，則A和B的乘積定義為AB={xy|xA且yB}
如：a={a, b}, B={00, 11} 則AB={a00, a11, b00, b11} 顯然：{}A=A{}=A
（4）符號串集合的方冪：設A為符號串集，則A的n次方冪An定義為:An=AA……A=AAn-1=An-1A
（5）符號串集合的正閉包A+：A+=A1 U A2 U … U An U …
（6）符號串集合的閉包A*：A*=A0 U A+ = {} U A+
如：設有正字母表={0，1} 則*=0 U 1 U 2 U … U n U …={, 0, 1, 00,01, 10, 11, 000, 001,……}
(2) 文法
文法G定義為四元組（VN ，VT，P，S）其中:
（1）VN 為非終結符號集
非終結符號表示一個語言短語（或語法成分、語法單位）。 如 程序、語句、表達式等。一般用大寫字母或用〈 〉括起表示非終結符號。
（2）VT 為終結符號集
終結符號：組成語言的基本符號。是文法中不屬于非終結符號集合的符號。一般用小寫字母或不帶〈 〉的符號表示。如程序設計語言的單詞符號。
設V=VN U VT，稱V為文法G的字母表。
（3）P 為產生式（也稱規則）的集合。
產生式的形式：→或∷=，其中∈V+，∈V*
（4）S 稱作識別符號或開始符號，是一個非終結符號。
一般表示此文法定義的最大語法短語，至少要在一條產生式 中作為左部出現。 句型、句子的定義
設G[S]是一文法，如果符號串x是從識別符號推導出來的，即有S*x， 則稱x是文法G[S]的句型。
若x僅由終結符號組成，即S*x, xV T ，則稱x為G[S]的句子。
句型：在一棵樹生長過程的任何時刻，所有那些端末結點自左至右的排列，就是一個句型。
語言的定義：文法G產生的語言記為L（G），它是文法G產生的全部句子的集合。 文法等價定義：若L（G1）=L（G2）則稱文法G1和G2是等價的。
(3) 文法的類型 N.Chomsky
0型文法：定義0型語言，對應Turing機；
1型文法：定義1型語言，對應線性限界自動機；箭頭后面的要比前面的長或相等 2型文法：定義2型語言，對應非確定下推自動機；箭頭前面的是非終結符，后面是串 3型文法：定義3型語言，對應有限自動機。非終結符可以推出一個終結符或一個終結符和一個非終結符
最右推導也稱為規范推導，所得句型稱為規范句型。
如果一個文法存在某個句型對應兩棵不同的語法樹，則說這個文法是二義的。或者說，若一個文法中存在某個句型，它有兩個不同的最左（最右）推導，則這個文法是二義的。
上下文無關文法是否具有二義性是不可判定的。
但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是無二義性的。 一個文法兼有左遞歸和右遞歸是導致二義性的常見原因。
排除文法二義性通常有兩種方法:
（1）在語義上加些限制
（2）重新構造一個無二義性的文法
(4) 句型的分析
句型的分析：就是識別一個符號串是否為某文法的句型。是某個推導的構造過程。 分析方法分兩大類：自上而下分析法和自下而上分析法推導與歸約，最右推導是規范推導，逆過程為規范規約
若S*A+（由A+得）則稱是句型相對于非終結符A的短語。
若S*A(由A→得)則稱是句型相對于A→的直接短語（也稱簡單短語）。 一個句型的最左直接短語稱為該句型的句柄。
一棵子樹（至少要有父子兩代）的所有端末結點自左至右排列起來形成相對于子樹根的短語。若子樹只有父子兩代，則得到直接短語。
(5) 有關文法
（1）有害規則 文法中含形如U→U的產生式。
它對描述語言沒有必要，且會引起文法的二義性。
（2）多余規則 文法中任何一個句子的推導都用不到的規則。
（3）無用規則 文法中含形如U→V的產生式，即單產生式。
為保證文法G的任一非終結符A在句子推導中出現，必須滿足如下兩個條件：
（1）A必須在某句型中出現，A。
（2） 必須能夠從A推導出終結符號串t。
有關文法的化簡和改造，包括以下幾項工作：
（１）無用符號和無用產生式的刪除。
（２） －產生式的消除。
（３）單產生式的消除。
（４）左遞歸的消除。
(1) 詞法分析輸出
單詞符號（TOKEN) 是一個程序設計語言的基本語法符號。程序設計語言的單詞符號一般可分成下列5種：
1．基本字，也稱關鍵字，如PASCAL語言中的begin，end，if，while和var等。
2．標識符，用來表示各種名字，如常量名、變量名和過程名等。
3．常數，各種類型的常數，如25，3.1415，TRUE和"ABC"等。
4．運算符，如+，*，<= 等。
5．界符，如逗點，分號，括號等。
詞法分析程序所輸出的單詞符號常常采用下二元式表示：（單詞種別，單詞自身的值） 可用整數碼或助記符等表示。
(2) 單詞的描述工具
程序設計語言中的單詞(TOKEN)是基本語法符號。單詞符號的語法可以用有效的工具加以描述。
正規式和它所表示的正規集的遞歸定義如下。設字母表為∑，輔助字母表∑ ={ |, ·, *, (, ) }
定義（正規式和它所表示的正規集）：
設字母表為Σ，輔助字母表Σ`={Φ，ε，|，·，*，(， }。
② ε和Φ都是Σ上的正規式，它們所表示的正規集分別為{ε}和{ }；
② 任何a∈Σ，a是Σ上的一個正規式，它所表示的正規集為{a}；
③ 假定e1和e2都是Σ上的正規式，它們所表示的正規集分別為L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正規式,它們所表示的正規集分別為L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。
④ 僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規式，僅由這些正規式所表示的字集才是Σ上的正規集。
(3) 有窮自動機
有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程
【編譯原理期末總結復習】相關文章：
編譯原理小論文03-30
編譯原理知識點總結03-30
編譯原理的學習心得體會03-19
編譯原理實驗課程教學設計的改進論文06-12
編譯原理課程設計心得體會01-12
會計學原理復習總結08-05
會計學原理復習總結范文04-29
物理期末復習總結03-05
《編譯原理》教學過程中的思考與探討論文07-05