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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1編譯程序： 從高級(jí)語(yǔ)言到匯編語(yǔ)言或機(jī)器語(yǔ)言的翻譯程序

2.源程序：用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15引入中間代碼的好處：

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

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

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

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

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

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

（1）編譯程序需要在運(yùn)行前將源代碼譯成目標(biāo)代碼，解釋程序接受某個(gè)語(yǔ)言的程序并立即運(yùn)行這個(gè)源程序

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

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

19程序性合計(jì)語(yǔ)言范型：

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

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

1.推導(dǎo)：

—自上而下的語(yǔ)法分析過程

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

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

2.歸約：

—自下而上的語(yǔ)法分析過程

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

3.自下而上的語(yǔ)法分析過程思想

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

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

2）語(yǔ)法分析程序執(zhí)行的動(dòng)作：

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

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

c)識(shí)別成功：移進(jìn)—?dú)w約的結(jié)局是棧內(nèi)只剩下棧底符號(hào)和文法開始符號(hào)，讀頭也指向語(yǔ)句的結(jié)束符.

d)識(shí)別失敗.

令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有 S αAδ且A β

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

特別是，如果有 A β

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

注： 一個(gè)句型的語(yǔ)法樹中任一子樹葉節(jié)點(diǎn)所組成的符號(hào)串就是該句型的短語(yǔ)，當(dāng)子樹中不包含其他更小的子樹時(shí)，該子樹結(jié)點(diǎn)所組成的字符串就是該句型的直接（簡(jiǎn)單）短語(yǔ)。

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

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

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

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

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

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

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

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

則這是一個(gè)簡(jiǎn)單優(yōu)先文法。

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

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

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

因?yàn)?FOLLOW(S)={a,b,#} ，所以無(wú)法解決沖突

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

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

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

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

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

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

（1章） 1.源程序： 用編譯語(yǔ)言或高級(jí)語(yǔ)言編寫的程序

目標(biāo)程序：用目標(biāo)語(yǔ)言表示的程序

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

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

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

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

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

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

4.編譯程序和解釋程序

（1）編譯程序需要在運(yùn)行前將源代碼譯成目標(biāo)代碼，解釋程序接受某個(gè)語(yǔ)言的程序并立即運(yùn)行這個(gè)源程序

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

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

5.程序性合計(jì)語(yǔ)言范型：

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

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

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

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

7.編譯前端和后端

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

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

1.推導(dǎo)：

—自上而下的語(yǔ)法分析過程

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

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

2.歸約：

—自下而上的語(yǔ)法分析過程

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

3.自下而上的語(yǔ)法分析過程思想

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

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

2）語(yǔ)法分析程序執(zhí)行的動(dòng)作：

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

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

c)識(shí)別成功：移進(jìn)—?dú)w約的結(jié)局是棧內(nèi)只剩下棧底符號(hào)和文法開始符號(hào)，讀頭也指向語(yǔ)句的結(jié)束符.

d)識(shí)別失敗.

令G是一個(gè)文法，S是文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有 S αAδ且A β

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

特別是，如果有 A β

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

的直接短語(yǔ)，一個(gè)句型的最左直接短語(yǔ)稱為該句型的.句柄。

注： 一個(gè)句型的語(yǔ)法樹中任一子樹葉節(jié)點(diǎn)所組成的符號(hào)串就是該句型的短語(yǔ)，當(dāng)子樹中不包含其他更小的子樹時(shí)，該子樹結(jié)點(diǎn)所組成的字符串就是該句型的直接（簡(jiǎn)單）短語(yǔ)。

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

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

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

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

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

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

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

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

則這是一個(gè)簡(jiǎn)單優(yōu)先文法。

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

1.簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。

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

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

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

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

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

什么是句柄？什么是素短語(yǔ)？

一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。

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

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

編譯程序的工作分為那幾個(gè)階段?

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

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

簡(jiǎn)述自下而上的分析方法。

開始符號(hào)；或者說(shuō)從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。

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

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

LR(0)分析器

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

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

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

第四章

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

SaABbcd |

AASd |

BSAh | eC |

CSf | Cg |

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

(2) 該文法是否為L(zhǎng)L(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表示。因?yàn)?、4中含有z，所以它們?yōu)榻K態(tài)。

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

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

四、對(duì)下面的文法G：

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

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

(2) 判斷文法G2是否LL（1）文法，如果是，給出其預(yù)測(cè)分析表。（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) 計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集； (2)

是

二、設(shè)={0，1}上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(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、語(yǔ)言處理器

1、簡(jiǎn)單的說(shuō)，一個(gè)編譯器就是一個(gè)程序，它可以閱讀以某一種語(yǔ)言（源語(yǔ)言）編寫的程序，并把該程序翻譯成一個(gè)等價(jià)的、用另一種語(yǔ)言（目標(biāo)語(yǔ)言）編寫的程序。

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

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

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

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

Object Source

Program

Output

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

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

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

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

Front end Back end

1、將編譯器看成黑盒，則源程序映射為在語(yǔ)義上等價(jià)的目標(biāo)程序，而這個(gè)映射由兩部分組成：分析部分和綜合部分。

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

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

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

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

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

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

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

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

1、記號(hào)（token）

2、語(yǔ)法樹（syntax tree）

3、符號(hào)表（symbol table）

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

5、中間代碼（intermediate code）

6、臨時(shí)文件（temporary file）

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

第二章 詞法分析

掃描處理

正則表達(dá)式

有窮自動(dòng)機(jī)

從正則表達(dá)式到D FA

利用L e x自動(dòng)生成掃描程序

1、 Tokens記號(hào)標(biāo)記：identifiers、keywords、integers、floating-point、symbols、strings、comments

1、 使用正則表達(dá)式去描述程序語(yǔ)言tokens

2、 一個(gè)正則表達(dá)式是歸納確定

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

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

5、 所有的token都能用正則表達(dá)式表示

2、 正則表達(dá)式：

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

2、 正則表達(dá)式運(yùn)算：

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

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

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

3、從各選擇對(duì)象中選擇：

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

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

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

7、正則表達(dá)式的名字：為較長(zhǎng)的正則表達(dá)式提供一個(gè)簡(jiǎn)化了的名字很有用處，這樣就不再需要在每次使用正則表達(dá)式時(shí)書寫常常的表達(dá)式本身了。

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

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

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

4、從正則表達(dá)式到DFA

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

2、從正則表達(dá)式到

NFA

3、從NFA到

DFA

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

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

分析過程

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

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

分析樹與抽象語(yǔ)法樹

二義性

1、分析過程：

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

3、分析樹與抽象語(yǔ)法樹：

4、二義性：

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

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

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

第四章 自頂向下的分析

使用遞歸下降分析算法進(jìn)行自頂向下的分析

LL(1)分析

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

1、使用遞歸下降分析算法進(jìn)行自頂向下的分析

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

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

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

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

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

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

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

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

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

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

C語(yǔ)言條件編譯10-31

C語(yǔ)言的編碼編譯04-14