編譯原理期末總結(jié)

編譯是計算機系統(tǒng)軟件的最重要組成部分之一，也是用戶最直接關(guān)心的工具之一。編譯原理的整個知識體系是數(shù)十年中無數(shù)學(xué)術(shù)精英在形式語義學(xué)、計算數(shù)學(xué)、計算機科學(xué)等相關(guān)領(lǐng)域探索、積累的結(jié)果。整個編譯程序,也是一個完整的系統(tǒng)算法,將數(shù)據(jù)結(jié)構(gòu)的理論進一步專一化。

編譯原理的主要內(nèi)容概括了開發(fā)一個編譯程序所需要的基本理論、方法和技術(shù),如詞法分析、語法分析、語義分析、中間代碼生成、符號表、存儲空間組織、優(yōu)化和目標代碼生成等。隨著編譯技術(shù)的發(fā)展,加入了屬性文法、語法制導(dǎo)翻譯、面向?qū)ο笳Z言的編譯、并行編譯等知識。在程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)等課程學(xué)習(xí)后,學(xué)生對較為孤立的算法有了一定的了解,再學(xué)習(xí)編譯原理,可以較系統(tǒng)地認識程序算法,培養(yǎng)分析問題和解決問題的能力。

作為授課教師，如何在有限的學(xué)時內(nèi)，使學(xué)生理解編譯的基本原理、掌握編譯的基本方法，提高學(xué)生的動手能力，使課程的教學(xué)效果得到較大改觀，是一個迫切需要解決的課題。課程組以現(xiàn)代教育教學(xué)理論為指導(dǎo)，在教學(xué)過程中，針對教材選擇、課堂教學(xué)、習(xí)題指導(dǎo)、答疑討論、網(wǎng)絡(luò)輔助、教學(xué)互動等環(huán)節(jié)進行綜合探索和創(chuàng)造性的改革與實踐，積累經(jīng)驗。為學(xué)生創(chuàng)造一個全方位立體化的教學(xué)環(huán)境，滿足各層次學(xué)生的需要。

在教學(xué)過程中，學(xué)生理解和掌握這門課有一定難度，出現(xiàn)這種情況的原因存在以下幾個方面：

(1)編譯程序規(guī)模大。由于編譯原理是一個極其復(fù)雜的系統(tǒng)，程序規(guī)模大，導(dǎo)致不可能在一節(jié)課或一段時間講述完，只好將它分解開一部分一部分地研究， 但是這樣容易造成知識體系斷裂。不可能在短時間讓學(xué)生對整個編譯系統(tǒng)各部分融會貫通，理清各部分邏輯關(guān)系的順序。

(2)理論知識抽象。要完整地構(gòu)造一個編譯系統(tǒng)并不是一件容易的事情，它不僅需要具有較完備的軟件知識，并需要掌握現(xiàn)有的軟件工具的使用，而且更重要的是要有豐富的實踐經(jīng)驗，了解硬件系統(tǒng)結(jié)構(gòu)和操作系統(tǒng)的功能。這些對于剛學(xué)完基礎(chǔ)知識的學(xué)生來講，理解難度系數(shù)相當大。

(3)算法的理解和實現(xiàn)。編譯原理這門課包含許多理論知識和算法，這些理論的學(xué)習(xí)和理解都存在著一定的難度。其中理論知識包括：詞法分析器的構(gòu)造，語法中各種分析器（LR, LL,SLR,LALR 等）實現(xiàn)與完成。

針對這些問題，分別采取各種不同的策略，策略包括傳統(tǒng)教學(xué)方法和現(xiàn)代教學(xué)理論兩方面， 已經(jīng)應(yīng)用這些方法于實際教學(xué)中，已取得良好的教學(xué)效果。

第一、傳統(tǒng)的教學(xué)方法是教學(xué)成果的精華，如何在現(xiàn)今的教學(xué)中靈活應(yīng)用，

也值得我們討論，我們常用的方法為：比喻式教學(xué)方法、問題式教學(xué)方法、反思式教學(xué)方法。

(1)比喻式教學(xué)方法就是用接近我們生活中的例子來近似地表示問題， 使問題更容易理解和解決。一般來說大學(xué)生的想象能力，邏輯能力比較強，但由于計算機處理問題的過程與日常處理問題有些不同， 而且計算機領(lǐng)域中涉及到一些概念比較抽象， 所以在講解時打比方，轉(zhuǎn)換問題的難度， 是常采用的方法。

(2)問題式教學(xué)方法可以更好地擴展學(xué)生的思維，發(fā)揮學(xué)生學(xué)習(xí)的遷移。問題式教學(xué)一般分四步： 提出問題、引導(dǎo)問題、解決問題、擴充問題。 在分析語法分析器時，首先提出：語法分析的解決問題？常用的語法分析的方法？引導(dǎo)語法分析構(gòu)造的步驟和過程， 在引導(dǎo)過程中，解決語法構(gòu)造過程的難點，并且擴充問題到，對于同一種語法在用不同的語法分析器中，將產(chǎn)生的結(jié)果和基理。語法分析器，讓學(xué)生在分解問題的過程中得到了理解和應(yīng)用。

(3)反思式教學(xué)方法要求教師從學(xué)生的角度來考慮問題，講解問題。這種方式可以加強學(xué)生和老師之間的互動， 降低學(xué)生學(xué)習(xí)焦慮的情緒，提高教學(xué)的效果。

第二、構(gòu)建多媒體環(huán)境下的教學(xué)環(huán)境，利用現(xiàn)代的教學(xué)手段，多媒體設(shè)施，電子教案等多種途徑，實現(xiàn)課堂時間的有效化，在傳統(tǒng)的教學(xué)模式下，推導(dǎo)理論需要大量的板書，老師忙于講，而學(xué)生忙于記筆記，一堂課下來，學(xué)生累，老師累， 結(jié)果學(xué)生不知道具體內(nèi)容。借助多媒體，各種算法的推導(dǎo)一目了然，老師的重點放在講解算法的原理， 理順原理之間的邏輯關(guān)系上，學(xué)生則側(cè)重于理解。具體的做法為向?qū)W生提供各類資源庫的網(wǎng)上教學(xué)系統(tǒng)，幫助學(xué)生理解課堂教學(xué)內(nèi)容。

編譯原理期末總結(jié) [篇2]

1編譯程序： 從高級語言到匯編語言或機器語言的翻譯程序

2.源程序：用匯編語言或高級語言編寫的程序

3. 目標程序:用目標語言所表示的程序。 目標語言：介于源語言和機器語言之間的 “中間語言”，也可以是某種機器的機器語言,也可以是 某機器的匯編語言。

4 翻譯程序:將源程序轉(zhuǎn)換為目標程序的程序稱為翻譯程序。

5 賦值語句的語法規(guī)則： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=標識符 C::=常數(shù)

6 遍：對源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標程序，通常稱之為一遍。

優(yōu)點：節(jié)省內(nèi)存空間，提高目標代碼質(zhì)量，邏輯機構(gòu)清晰

缺點：編譯時間較長，會增加輸入輸出所消耗的時間，在內(nèi)存許可下少用為妙

7前端：通常將與源程序有關(guān)的編譯部分稱為前端。 包括詞法分析，語法分析，語義分析，等分析部分

后端：與目標機有關(guān)的部分稱為后端。包括中間代碼生成，代碼優(yōu)化，目標程序生成等綜合部分

8編譯程序構(gòu)成部分以及功能： （1）詞法分析（掃描器）：輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞及其有關(guān)屬性，并轉(zhuǎn)換成屬性字。（2）語法分析(分析器)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，逐一分析詞法分析時得到的屬性字，檢查語法錯誤，若沒有錯誤，則給出正確的語法結(jié)構(gòu)（如短語、子句、句子、程序段、程序等）。（3）語義分析(語義處理)：語法分析識別出的各類語法范疇，分析其含義,進行和初步翻譯，產(chǎn)生介于源代碼和目標代碼之間的一種代碼“中間代碼”。或者直接生成目標代碼。（4）優(yōu)化：依據(jù)程序的等價變換規(guī)則，盡量壓縮

目標程序運行時所需的時間和所占的存儲空間，以提高目標程序的質(zhì)量（5）目標代碼生成：把經(jīng)過優(yōu)化的中間代碼轉(zhuǎn)化成特定機器上的低級語言代碼。

9計算機執(zhí)行用高級語言編寫的程序途徑有兩種：解釋方式和編譯方式。 根本區(qū)別：是否生成了目標代碼。 解釋方式下，翻譯程序事先并不對高級語言程序進行徹底翻譯以得到機器代碼，而是讀入一條語句，就解釋其含義并執(zhí)行，然后再讀入下一條語句，再解釋執(zhí)行，即按，源程序中語句的動態(tài)順序逐句地進行分析解釋，并立即予以執(zhí)行。 編譯方式下，翻譯程序先對高級語言程序進行徹底翻譯并生成目標代碼，然后再對目標代碼進行執(zhí)行，即對源程序的處理是先翻譯后執(zhí)行。簡單來說解釋方式不生成目標代碼，編譯方式生成目標代碼

10編譯程序采用多遍掃描還是單編掃描需要考慮哪些因素 不一定，多遍編譯器結(jié)構(gòu)清晰，構(gòu)造時間短，運行時需要內(nèi)存少，產(chǎn)生的目標代碼質(zhì)量高，但時間效率低，

應(yīng)該根據(jù)具體情況決（1）語句的大小與結(jié)構(gòu)，（2）機器規(guī)模（3）設(shè)計目的（4）設(shè)計人員的素質(zhì)及數(shù)量。 11 比較LR（0）,SLR（1）,LR（1）和LALR（1）

分析表的優(yōu)缺點

（1）LR（0）分析表局限性大，但其構(gòu)造方法是其他構(gòu)造方法的基礎(chǔ)

（2）SLR分析表雖然不是對所有文法都存在，但這種分析表狀態(tài)少，存儲空間占用少，較易實現(xiàn)又極有實用價值。

（3）規(guī)范LR分析表，即LR（1）分析表，它的，它的分析能力最強，能適用于一大類文法，但是實現(xiàn)代價過高，主要是體積過大 （4）LALR分析表的能力介于SLR分析表和規(guī)范LR分析表之間，稍加努力，就可以高效的實現(xiàn)。

12比較LL（K）分析表與LR（K）分析法 共同點：（1）兩者多借助于可能句柄左部的全部符號及向右看K個符號來確定所應(yīng)執(zhí)

行的唯一動作，識別過程嚴格地從左到右掃描，無回溯，效率高。（2）都能及時察覺錯誤2。（3）識別程序都能自動生成。 區(qū)別：（1）兩者都是嚴格地從左到右掃描，名稱中第一個L隱指這點，但LR分析技術(shù)利用的是最右推導(dǎo)（最左歸約），由R隱指，LL（K）分析利用的是最左推導(dǎo)，由第二個L隱指。（2）LL（K）要求文法無左遞歸，滿足無回溯的條件，而LR分析法則無此限制。（3）LL（K）是自上而下構(gòu)造推導(dǎo)的，而LR（K）是自下而上構(gòu)造歸約的。 13語法制導(dǎo)翻譯過程：對單詞符號串進行語法分析，構(gòu)造語法分析樹，構(gòu)造屬性依賴圖，遍歷語法樹并在語法樹各結(jié)點處按語義規(guī)則計算順序。

14靜態(tài)語義檢查：類型檢查，控制流檢查，一致性檢查，相關(guān)名字檢查，名字的作用域分析。

15引入中間代碼的好處：

（1）便于進行與機器無關(guān)的代碼優(yōu)化工作 （2）使編譯程序更容易改變目標機

（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確，以中間語言為界限，編譯前端和后端的接口更清晰。 16編譯程序分類 （1）診斷編譯程序 （2）優(yōu)化編譯程序 （3）交叉編譯程序 （4）可變目標編譯程序

17編譯程序工作過程5個階段及其任務(wù)： （1）詞法分析：任務(wù)是從左到右逐個字符的讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，進而識別一個個單詞。

（2）語法分析：任務(wù)是根據(jù)語法規(guī)則，分析并識別出各種語法成分，并經(jīng)行語法正確性檢查。

（3）語義分析與中間代碼生成：任務(wù)是對識別出的各種語法成分進行語義分析，并產(chǎn)生相應(yīng)的中間代碼。

（4）目標代碼生成：任務(wù)是把中間代碼轉(zhuǎn)換成特定機器上的低級語言代碼。 18編譯程序和解釋程序

（1）編譯程序需要在運行前將源代碼譯成目標代碼，解釋程序接受某個語言的程序并立即運行這個源程序

（2）二者存儲組織有著很大不同，編譯程序處理時存儲區(qū)要存儲編譯用時需要的各種表格；解釋程序?qū)⒎治鼋Y(jié)果存放在源程序區(qū)

（3）編譯程序動態(tài)性很差，可形成永久性可執(zhí)行文件，解釋程序動態(tài)性較好。

19程序性合計語言范型：

（1）強制（命令）式語言：c,fortron,pasal （2）函數(shù)式語言：ML,Lisp

（3）基于規(guī)則（邏輯）的語言：prolog （4）面向?qū)ο笳Z言：Ada,c++,java

1.推導(dǎo)：

—自上而下的語法分析過程

—預(yù)測分析程序，遞歸下降分析法（最左推導(dǎo)）

—注：要求文法是LL(1)文法

2.歸約：

—自下而上的語法分析過程

—簡單優(yōu)先分析法，算符優(yōu)先分析法、LR分析法3

3.自下而上的語法分析過程思想

—自下而上的語法分析過程是一個最左歸約的過程，從輸入串開始。朝著文法的開始符號進行歸約，直到到達文法的開始符號為止的過程 注意：輸入串在這里是指從詞法分析器送來的單詞符號組成的二元式的有限序列 。 即：自左至右把輸入串的符號一個一個移進棧，在移進過程中不斷查看棧頂符號串，一旦形成某個句型的句柄時，就將此句柄用相應(yīng)的產(chǎn)生式左部替換（歸約），若再形成句柄，就繼續(xù)替換，直到棧頂不再形成句柄為止，然后繼續(xù)移進符號，重復(fù)上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為止，這樣就認為識別了一個句子。

1）初態(tài)時棧內(nèi)僅有棧底符“#”，讀頭指在最左邊的單詞符號上 .

2）語法分析程序執(zhí)行的動作：

a)移進：讀入一個單詞并壓入棧內(nèi)，讀頭后移；

b)歸約：檢查棧頂若干個符號能否進行歸約，若能，就以產(chǎn)生式左部替代該符號串，同時輸出產(chǎn)生式編號.

c)識別成功：移進—歸約的結(jié)局是棧內(nèi)只剩下棧底符號和文法開始符號，讀頭也指向語句的結(jié)束符.

d)識別失敗.

令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有 S αAδ且A β

則稱β是句型αβδ相對于非終結(jié)符A的短語。

特別是，如果有 A β

則稱β是句型αβδ相對于規(guī)則A→β的直接短語，一個句型的最左直接短語稱為該句型的句柄。

注： 一個句型的語法樹中任一子樹葉節(jié)點所組成的符號串就是該句型的短語，當子樹中不包含其他更小的子樹時，該子樹結(jié)點所組成的字符串就是該句型的直接（簡單）短語。

素短語： 一個遞歸的定義，至少含有一個終結(jié)符，并且除它自身之外不在含有任何更小的素短語，（所謂最左素短語就是處于句型最左邊的素短語）。

簡單優(yōu)先分析法：1.確定相鄰文法符號之間的優(yōu)先關(guān)系 在句型中，句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級，相同優(yōu)先級用“ ”

由于句柄要先歸約,所以規(guī)定句柄兩端符號的優(yōu)先級要比位于句柄之外的相鄰符號的優(yōu)先級高,優(yōu)先級低于表示為“﹤”,優(yōu)先級高于表示為“ ＞”

某句型中:N1…..Ni-1< Ni …… Nj ＞ Nj+1…..Nn

定義：一個文法G，如果它不含e產(chǎn)生式，也不含任何右部相

同的不同產(chǎn)生式，并且它的任何符號對（X，Y）

X，Y是終結(jié)符或非終結(jié)符 ——或者沒有關(guān)系，

——或者存在優(yōu)先級相同或低于、高于等關(guān)系之一，

則這是一個簡單優(yōu)先文法。

1LR(0) 文法：該文法的以 LR(0) 項目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 中沒有沖突狀態(tài)。

2 SLR(1) 文法：該文法的以 LR(0) 項目集為狀態(tài)的識別規(guī)范句型活前綴的 DFA 中有沖突狀態(tài)，沖突可用 FOLLOW 集解決。

該文法不是 SLR(1) 文法。

因為 FOLLOW(S)={a,b,#} ，所以無法解決沖突

3算符優(yōu)先：（T） (<firstvt（T） lastvt（T）>) （6章）

1.靜態(tài)語義檢查包括： （1）類型檢查 （2）控制流檢查 （3）一致性檢查 （4）相關(guān)名字檢查 （5）名字的作用域分析

2.引入中間代碼的好處：

（1）便于進行與機器無關(guān)的代碼優(yōu)化工作 （2）使編譯程序更容易改變目標機

（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡單

明確，以中間語言為界限，編譯前端和后端的接口更清晰。

（1章） 1.源程序： 用編譯語言或高級語言編寫的程序

目標程序：用目標語言表示的程序

翻譯程序： 將源程序轉(zhuǎn)換為目標程序的程序。

2.編譯程序分類 （1）診斷編譯程序 （2）優(yōu)化編譯程序 （3）交叉編譯程序 （4）可變目標編譯程序

3.編譯程序工作過程5個階段及其任務(wù)： （1）詞法分析：任務(wù)是從左到右逐個字符的讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，進而識別一個個單詞。

（2）語法分析：任務(wù)是根據(jù)語法規(guī)則，分析并識別出各種語法成分，并經(jīng)行語法正確性檢查。

（3）語義分析與中間代碼生成：任務(wù)是對識別出的各種語法成分進行語義分析，并產(chǎn)生相應(yīng)的中間代碼。

（4）目標代碼生成：任務(wù)是把中間代碼轉(zhuǎn)換成特定機器上的低級語言代碼。

4.編譯程序和解釋程序

（1）編譯程序需要在運行前將源代碼譯成目標代碼，解釋程序接受某個語言的程序并立即運行這個源程序

（2）二者存儲組織有著很大不同，編譯程序處理時存儲區(qū)要存儲編譯用時需要的各種表格；解釋程序?qū)⒎治鼋Y(jié)果存放在源程序區(qū)

（3）編譯程序動態(tài)性很差，可形成永久性可執(zhí)行文件，解釋程序動態(tài)性較好。

5.程序性合計語言范型：

（1）強制（命令）式語言：c,fortron,pasal （2）函數(shù)式語言：ML,Lisp

（3）基于規(guī)則（邏輯）的語言：prolog

（4）面向?qū)ο笳Z言：Ada,c++,java

6.構(gòu)造編譯程序必須掌握的三方面內(nèi)容： （1）源程序 （2）目標語言 （3）編譯方法

7.編譯前端和后端

前端：通常指與源程序有關(guān)的編譯部分，包括詞法分析，語法分析，語義分析，特點是與源程序有關(guān)。

后端：與目標機有關(guān)的部分，包括中間代碼生成，代碼優(yōu)化，目標程序生成，特點是與目標機有關(guān)。

1.推導(dǎo)：

—自上而下的語法分析過程

—預(yù)測分析程序，遞歸下降分析法（最左推導(dǎo)）

—注：要求文法是LL(1)文法

2.歸約：

—自下而上的語法分析過程

—簡單優(yōu)先分析法，算符優(yōu)先分析法、LR分析法3

3.自下而上的語法分析過程思想

—自下而上的語法分析過程是一個最左歸約的過程，從輸入串開始。朝著文法的開始符號進行歸約，直到到達文法的開始符號為止的過程 注意：輸入串在這里是指從詞法分析器送來的單詞符號組成的二元式的有限序列 。 即：自左至右把輸入串的符號一個一個移進棧，在移進過程中不斷查看棧頂符號串，一旦形成某個句型的句柄時，就將此句柄用相應(yīng)的產(chǎn)生式左部替換（歸約），若再形成句柄，就繼續(xù)替換，直到棧頂不再形成句柄為止，然后繼續(xù)移進符號，重復(fù)上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為止，這樣就認為識別了一個句子。

1）初態(tài)時棧內(nèi)僅有棧底符“#”，讀頭指在最左邊的單詞符號上 .

2）語法分析程序執(zhí)行的動作：

a)移進：讀入一個單詞并壓入棧內(nèi)，讀頭后移；

b)歸約：檢查棧頂若干個符號能否進行歸約，若能，就以產(chǎn)生式左部替代該符號串，同時輸出產(chǎn)生式編號.

c)識別成功：移進—歸約的結(jié)局是棧內(nèi)只剩下棧底符號和文法開始符號，讀頭也指向語句的結(jié)束符.

d)識別失敗.

令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有 S αAδ且A β

則稱β是句型αβδ相對于非終結(jié)符A的短語。

特別是，如果有 A β

則稱β是句型αβδ相對于規(guī)則A→β

的直接短語，一個句型的最左直接短語稱為該句型的.句柄。

注： 一個句型的語法樹中任一子樹葉節(jié)點所組成的符號串就是該句型的短語，當子樹中不包含其他更小的子樹時，該子樹結(jié)點所組成的字符串就是該句型的直接（簡單）短語。

素短語： 一個遞歸的定義，至少含有一個終結(jié)符，并且除它自身之外不在含有任何更小的素短語，（所謂最左素短語就是處于句型最左邊的素短語）。

簡單優(yōu)先分析法：1.確定相鄰文法符號之間的優(yōu)先關(guān)系 在句型中，句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級，相同優(yōu)先級用“ ”

由于句柄要先歸約,所以規(guī)定句柄兩端符號的優(yōu)先級要比位于句柄之外的相鄰符號的優(yōu)先級高,優(yōu)先級低于表示為“﹤”,優(yōu)先級高于表示為“ ＞”

某句型中:N1..Ni-1< Ni Nj ＞ Nj+1..Nn

定義：一個文法G，如果它不含e產(chǎn)生式，也不含任何右部相

同的不同產(chǎn)生式，并且它的任何符號對（X，Y）

X，Y是終結(jié)符或非終結(jié)符 ——或者沒有關(guān)系，

——或者存在優(yōu)先級相同或低于、高于等關(guān)系之一，

則這是一個簡單優(yōu)先文法。

編譯原理期末總結(jié) [篇3]

1.簡要說明語義分析的基本功能。

答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。

1.編譯方式和解釋方式的根本區(qū)別是什么？

編譯方式：是將源程序經(jīng)編譯得到可執(zhí)行文件后，就可脫離源程序和編譯程序單獨執(zhí)行，所以編譯方式的效率高，執(zhí)行速度快；解釋方式：在執(zhí)行時，必須源程序和解釋程序同時參與才能運行，其不產(chǎn)生可執(zhí)行程序文件，效率低，執(zhí)行速度慢。

2．編譯程序有哪些主要構(gòu)成成分？各自的主要功能是什么？ 編譯程序的主要構(gòu)成成分有：詞法分析程序、語法分析程序、語義分析程序、中間代碼 生成程序、代碼優(yōu)化程序、目標代碼生成程序、表格管理程序及出錯處理程序。 （1）詞法分析程序：從左到右掃描源程序，識別單詞及其有關(guān)屬性； （2）語法分析程序：分析源程序的結(jié)構(gòu), 判別它是否為相應(yīng)程序設(shè)計語言中的一個合法 程序； （3）語義分析程序：審查源程序有無語義錯誤，為代碼生成階段收集類型信息； （4）中間代碼生成程序：將源程序變成一種內(nèi)部表示形式；

3什么是解釋程序？它與編譯程序的主要不同是什么？ 解釋程序接受某個語言的程序并立即運行這個源程序。它的工作模式是一個個的獲取、 分析并執(zhí)行源程序語句，一旦第一個語句分析結(jié)束，源程序便開始運行并且生成結(jié)果，它特 別適合程序員交互方式的工作情況。 而編譯程序是一個語言處理程序，它把一個高級語言程序翻譯成某個機器的匯編或二進 制代碼程序，這個二進制代碼程序再機器上運行以生成結(jié)果。 它們的主要不同在于：解釋程序是邊解釋邊執(zhí)行，解釋程序運行結(jié)束即可得到該程序的 運行結(jié)果， 而編譯程序只是把源程序翻譯成匯編或者二進制程序， 這個程序再執(zhí)行才能得到 程序的運行結(jié)果。 （當然還有其他不同，比如存儲組織方式不同）

什么是句柄？什么是素短語？

一個句型的最左直接短語稱為該句型的句柄。

詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，

并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。

編譯程序的工作分為那幾個階段?

詞法分析、語法分析和語義分析是對源程序進行的分析(稱為編譯程序的前端)， 而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合(稱為

編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標程序。

簡述自下而上的分析方法。

開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。

4．簡述代碼優(yōu)化的目的和意義。

一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目 標程序運行時所需要的時間短，同時所占用的存儲空間少。

LR(0)分析器

每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再

向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否

已在分析棧的頂部形成，從而也就可以確定當前所應(yīng)采取的分析動作 (是 移進還是按某一產(chǎn)生式進行歸約等)。

第四章

1. 設(shè)有如下文法G[S]:

SaABbcd |

AASd |

BSAh | eC |

CSf | Cg |

(1) 求每個產(chǎn)生式的Predict集。

(2) 該文法是否為LL(1)文法？為什么？

答：(1)

Predict(SaABbcd)={a}

Predict(S )={#,d,f,a,h } Predict(AASd)={a,d} Predict(A )={h,a,d,b,e} Predict(BSAh)={a,d,h} Predict(B eC)={e} Predict(B )= Predict(CSf)={a,f} Predict(C Cg)={a,f,g} Predict(C )={g,b} (2)由于Predict(AASd) Predict(A )，所以該文法不是LL(1)文法。

三、 給定文法G[S]：

S→aA|bQ； A→aA|bB|b；B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF F→bD|aE|b

構(gòu)造相應(yīng)的最小的DFA 。

解：先構(gòu)造其NFA： 用子集法將NFA確定化：

將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因為3、4中含有z，所以它們?yōu)榻K態(tài)。

令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b進行分割：

P1＝（｛0,5, 6｝,｛1,2｝,｛3,4｝）再用b進行分割： P2＝（｛0｝,｛5, 6｝,｛1,2｝,｛3,4｝）再用a、b 進行分割，仍不變。 再令｛０｝為A，｛1，2｝為B，｛3，4｝為C，｛5，6｝為D。 最小化為右上圖。

四、對下面的文法G：

S→a | b | （T） T→T，S | S

(1) 消去文法的左遞歸，得到等價的文法G2；

(2) 判斷文法G2是否LL（1）文法，如果是，給出其預(yù)測分析表。（15） G2：

S→a | b | （T）

T→ ST’

T’→，S T’ | ε

A→BCc | gDB

B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c

(1) 計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW集； (2)

是

二、設(shè)={0，1}上的正規(guī)集S由倒數(shù)第二個字符為1的所有字符串組成，請給出該字集對應(yīng)的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的DFA。(8分)

答：

構(gòu)造相應(yīng)的正規(guī)式：(0|1)*1(0|1) (3分) NFA: (2分)

1

編譯原理期末總結(jié) [篇4]

第一章 引論

為什么要用編譯器

與編譯器相關(guān)的程序

翻譯步驟

編譯器中的主要數(shù)據(jù)結(jié)構(gòu)

1、語言處理器

1、簡單的說，一個編譯器就是一個程序，它可以閱讀以某一種語言（源語言）編寫的程序，并把該程序翻譯成一個等價的、用另一種語言（目標語言）編寫的程序。

2、編譯器的重要任務(wù)之一就是報告它在翻譯過程中發(fā)現(xiàn)的源程序中的錯誤。

3、使用編譯器是為了提高編程的速度和準確度。

4、與編譯器相關(guān)的程序：解釋程序（interpreter）、匯編程序（assembler）、連接程序（linker）、裝入程序（loader）、預(yù)處理器（preprocessor）、編輯器（editor）、調(diào)試程序（debugger）、描述器（profiler）、項目管理程序（project manager）。

5、解釋器是另一種常見的語言處理器。它并不通過翻譯的方法生成目標程序。從用戶的角度來看，解釋器直接利用用戶提供的輸入執(zhí)行源程序中指定的操作。

Object Source

Program

Output

6、一個源程序可能被分割成多個模塊，并存放于獨立的文件中。把源程序聚合在一起的任務(wù)有時會由一個被稱為預(yù)處理器（preprocessor）的程序獨立完成。預(yù)處理器還負責把那些稱為宏的縮寫形式轉(zhuǎn)換為源語言的語句。

7、連接器（linker）能夠解決外部內(nèi)存地址的問題。

8、加載器（loader）把所有的可執(zhí)行目標文件放到內(nèi)存中執(zhí)行。

2、一個編譯器的結(jié)構(gòu)

Front end Back end

1、將編譯器看成黑盒，則源程序映射為在語義上等價的目標程序，而這個映射由兩部分組成：分析部分和綜合部分。

2、分析部分把源程序分解成多個組成要素，并在這些要素之上加上語法結(jié)構(gòu)。

3、綜合部分根據(jù)中間表示和符號表中的信息來構(gòu)造用戶期待的目標程序。

4、編譯器的第一個步驟：詞法分析（lexical）或掃描（scanning）。詞法分析器讀入組成源程序的字符流，并且將它們組成有意義的詞素（lexeme）的序列。詞法分析器產(chǎn)生詞法單元（token）。

5、分隔詞素的空格會被詞法分析器忽略掉。

6、編譯器的第二個步驟：語法分析（syntax）或解析（parsing）。語法分析器使用由詞法分析器生成的各個詞法單元的第一個分量來創(chuàng)建樹形的中間表示。

7、語義分析（static semantic analysis）：語義分析器使用語法樹和符號表中的信息來檢查源程序是否和語言定義的語義一致。它同時也收集類型信息，并把這些信息存放在語法樹或符號表中，以便在隨后的中間代碼生成過程中使用。語義分析的一個重要部分是類型檢查（type checking）。編譯器檢查每個運算符是否具有匹配的運算分量。

8、總的說，編譯器的翻譯步驟是：掃描程序----語法分析程序----語義分析程序----源代碼優(yōu)化程序----代碼生成器----目標代碼優(yōu)化程序。

3、編譯器結(jié)構(gòu)中的主要數(shù)據(jù)結(jié)構(gòu)

1、記號（token）

2、語法樹（syntax tree）

3、符號表（symbol table）

4、常數(shù)表（literal table）

5、中間代碼（intermediate code）

6、臨時文件（temporary file）

4、將編譯器分成了只依賴于源語言（前端（ front end））的操作和只依賴于目 標語言（后端（ back end））的操作兩部分。

第二章 詞法分析

掃描處理

正則表達式

有窮自動機

從正則表達式到D FA

利用L e x自動生成掃描程序

1、 Tokens記號標記：identifiers、keywords、integers、floating-point、symbols、strings、comments

1、 使用正則表達式去描述程序語言tokens

2、 一個正則表達式是歸納確定

3、 一個正則表達式R描述一組字符串集合L(R)

4、 L(R) = the language defined by R

5、 所有的token都能用正則表達式表示

2、 正則表達式：

1、 基本正則表達式：他們是字母比哦啊中的單個字符且自身匹配

2、 正則表達式運算：

1、 從各選擇對象中選擇，用元字符“|”表示

2、 連結(jié)，由并置表示（不用元字符）

3、 重復(fù)或“閉包”，由元字符“*”表示

3、從各選擇對象中選擇：

4、連結(jié)：正則表達式r和正則表達式s的連接可寫作rs

5、重復(fù)：正則表達式的重復(fù)有時稱為Kleene閉包（（Kleene）closure），寫作r*

6、運算的優(yōu)先和括號的使用：前面的內(nèi)容忽略了選擇、連接和重復(fù)的優(yōu)先問題。

7、正則表達式的名字：為較長的正則表達式提供一個簡化了的名字很有用處，這樣就不再需要在每次使用正則表達式時書寫常常的表達式本身了。

3、有窮自動機（有窮狀態(tài)機）：是描述（或“機器”）特定類型算法的數(shù)學(xué)方法。

1、確定性有窮自動機：下一個狀態(tài)由當前狀態(tài)和當前輸入字符惟一給出的自動機。

2、非確定性有窮自動機：由它產(chǎn)生的。

4、從正則表達式到DFA

1、構(gòu)造一個個掃描程序的自動過程可分為3步

2、從正則表達式到

NFA

3、從NFA到

DFA

4、將DFA中的狀態(tài)最小化

第三章 上下文無關(guān)文法及分析

分析過程

上下文無關(guān)文法

上下文無關(guān)語言的形式特性

分析樹與抽象語法樹

二義性

1、分析過程：

2、上下文無關(guān)文法：

3、分析樹與抽象語法樹：

4、二義性：

可生成帶有兩個不同分析樹的串的文法稱作二義性文法（ ambiguous grammar） 有兩個解決二義性的基本方法。

其一是：設(shè)置一個規(guī)則，該規(guī)則可在每個二義性情況下指出哪一個分析樹（或語法樹）是正確的。

另一種方法是將文法改變成一個強制正確分析樹的構(gòu)造的格式，這樣就可以解決二義性了。

第四章 自頂向下的分析

使用遞歸下降分析算法進行自頂向下的分析

LL(1)分析

First 集合和F o l l o w集合

1、使用遞歸下降分析算法進行自頂向下的分析

2、LL(1) 分析方法是這樣得名的：第1個“L”指的是由左向右地處理輸入（一些舊式的分析程序慣于自右向左地處理輸入，但現(xiàn)在已不常用了）。第2個“L”指的是它為輸入串描繪出一個最左推導(dǎo)。括號中的數(shù)字1意味著它僅使用輸入中的一個符號來預(yù)測分析的方向。

3、定義：如果文法G相關(guān)的L L ( 1 )分析表的每個項目中至多只有一個產(chǎn)生式，則該文法 就是L L ( 1 )文法(LL(1) grammar)。

【編譯原理期末總結(jié)】相關(guān)文章：

編譯原理學(xué)結(jié)05-31

編譯原理課程的設(shè)計心得體會06-20

編譯原理課程設(shè)計的心得體會06-20

C語言編譯過程總結(jié)詳解04-14

最新C語言編譯過程總結(jié)詳解04-30

美學(xué)原理期末考試答案01-25

2015城市規(guī)劃原理期末試題08-25

C語言條件編譯10-31

C語言的編碼編譯04-14