編譯原理期末總結複習

編譯原理期末總結複習

　　篇一：

　　一、簡答題

　　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) 有窮自動機

　　有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程