編譯是計算機系統軟體的最重要組成部分之一，也是使用者最直接關心的工具之一。編譯原理的整個知識體系是數十年中無數學術精英在形式語義學、計算數學、電腦科學等相關領域探索、積累的結果。整個編譯程式,也是一個完整的系統演算法,將資料結構的理論進一步專一化。
編譯原理的主要內容概括了開發一個編譯程式所需要的基本理論、方法和技術,如詞法分析、語法分析、語義分析、中間程式碼生成、符號表、儲存空間組織、優化和目的碼生成等。隨著編譯技術的發展,加入了屬性文法、語法制導翻譯、面嚮物件語言的編譯、並行編譯等知識。在程式設計和資料結構等課程學習後,學生對較為孤立的演算法有了一定的瞭解,再學習編譯原理,可以較系統地認識程式演算法,培養分析問題和解決問題的能力。
作為授課教師，如何在有限的學時內，使學生理解編譯的基本原理、掌握編譯的基本方法，提高學生的動手能力，使課程的教學效果得到較大改觀，是一個迫切需要解決的課題。課程組以現代教育教學理論為指導，在教學過程中，針對教材選擇、課堂教學、習題指導、答疑討論、網路輔助、教學互動等環節進行綜合探索和創造性的改革與實踐，積累經驗。為學生創造一個全方位立體化的教學環境，滿足各層次學生的需要。
在教學過程中，學生理解和掌握這門課有一定難度，出現這種情況的原因存在以下幾個方面：
(1)編譯程式規模大。由於編譯原理是一個極其複雜的系統，程式規模大，導致不可能在一節課或一段時間講述完，只好將它分解開一部分一部分地研究， 但是這樣容易造成知識體系斷裂。不可能在短時間讓學生對整個編譯系統各部分融會貫通，理清各部分邏輯關係的順序。
(2)理論知識抽象。要完整地構造一個編譯系統並不是一件容易的事情，它不僅需要具有較完備的軟體知識，並需要掌握現有的軟體工具的使用，而且更重要的是要有豐富的實踐經驗，瞭解硬體系統結構和作業系統的功能。這些對於剛學完基礎知識的學生來講，理解難度係數相當大。
(3)演算法的理解和實現。編譯原理這門課包含許多理論知識和演算法，這些理論的學習和理解都存在著一定的難度。其中理論知識包括：詞法分析器的構造，語法中各種分析器（LR, LL,SLR,LALR 等）實現與完成。
針對這些問題，分別採取各種不同的策略，策略包括傳統教學方法和現代教學理論兩方面， 已經應用這些方法於實際教學中，已取得良好的教學效果。
第一、傳統的教學方法是教學成果的精華，如何在現今的教學中靈活應用，
也值得我們討論，我們常用的方法為：比喻式教學方法、問題式教學方法、反思式教學方法。
(1)比喻式教學方法就是用接近我們生活中的例子來近似地表示問題， 使問題更容易理解和解決。一般來說大學生的想象能力，邏輯能力比較強，但由於計算機處理問題的過程與日常處理問題有些不同， 而且計算機領域中涉及到一些概念比較抽象， 所以在講解時打比方，轉換問題的難度， 是常採用的方法。
(2)問題式教學方法可以更好地擴充套件學生的思維，發揮學生學習的遷移。問題式教學一般分四步： 提出問題、引導問題、解決問題、擴充問題。 在分析語法分析器時，首先提出：語法分析的解決問題？常用的語法分析的方法？引導語法分析構造的步驟和過程， 在引導過程中，解決語法構造過程的難點，並且擴充問題到，對於同一種語法在用不同的語法分析器中，將產生的結果和基理。語法分析器，讓學生在分解問題的過程中得到了理解和應用。
(3)反思式教學方法要求教師從學生的角度來考慮問題，講解問題。這種方式可以加強學生和老師之間的互動， 降低學生學習焦慮的情緒，提高教學的效果。
第二、構建多媒體環境下的教學環境，利用現代的教學手段，多媒體設施，電子教案等多種途徑，實現課堂時間的有效化，在傳統的教學模式下，推導理論需要大量的板書，老師忙於講，而學生忙於記筆記，一堂課下來，學生累，老師累， 結果學生不知道具體內容。藉助多媒體，各種演算法的推導一目瞭然，老師的重點放在講解演算法的原理， 理順原理之間的邏輯關係上，學生則側重於理解。具體的做法為向學生提供各類資源庫的網上教學系統，幫助學生理解課堂教學內容。
編譯原理期末總結 [篇2]
1編譯程式： 從高階語言到組合語言或機器語言的翻譯程式
2.源程式：用匯編語言或高階語言編寫的程式
3. 目標程式:用目標語言所表示的程式。 目標語言：介於源語言和機器語言之間的 “中間語言”，也可以是某種機器的機器語言,也可以是 某機器的組合語言。
4 翻譯程式:將源程式轉換為目標程式的程式稱為翻譯程式。
5 賦值語句的語法規則： A::=V=E E::=T|E+T T::=F|T*F F::=V|(E)|C V::=識別符號 C::=常數
6 遍：對源程式（包括源程式中間形式）從頭到尾掃描一次，並做有關的加工處理，生成新的源程式中間形式或目標程式，通常稱之為一遍。
優點：節省記憶體空間，提高目的碼質量，邏輯機構清晰
缺點：編譯時間較長，會增加輸入輸出所消耗的時間，在記憶體許可下少用為妙
7前端：通常將與源程式有關的編譯部分稱為前端。 包括詞法分析，語法分析，語義分析，等分析部分
後端：與目標機有關的部分稱為後端。包括中間程式碼生成，程式碼優化，目標程式生成等綜合部分
8編譯程式構成部分以及功能： （1）詞法分析（掃描器）：輸入源程式，對構成源程式的字串進行掃描和分解，識別出一個個的單詞及其有關屬性，並轉換成屬性字。（2）語法分析(分析器)：在詞法分析的基礎上，根據語言的語法規則，逐一分析詞法分析時得到的屬性字，檢查語法錯誤，若沒有錯誤，則給出正確的語法結構（如短語、子句、句子、程式段、程式等）。（3）語義分析(語義處理)：語法分析識別出的各類語法範疇，分析其含義,進行和初步翻譯，產生介於原始碼和目的碼之間的一種程式碼“中間程式碼”。或者直接生成目的碼。（4）優化：依據程式的等價變換規則，儘量壓縮
目標程式執行時所需的時間和所佔的儲存空間，以提高目標程式的質量（5）目的碼生成：把經過優化的中間程式碼轉化成特定機器上的低階語言程式碼。
9計算機執行用高階語言編寫的程式途徑有兩種：解釋方式和編譯方式。 根本區別：是否生成了目的碼。 解釋方式下，翻譯程式事先並不對高階語言程式進行徹底翻譯以得到機器程式碼，而是讀入一條語句，就解釋其含義並執行，然後再讀入下一條語句，再解釋執行，即按，源程式中語句的動態順序逐句地進行分析解釋，並立即予以執行。 編譯方式下，翻譯程式先對高階語言程式進行徹底翻譯並生成目的碼，然後再對目的碼進行執行，即對源程式的處理是先翻譯後執行。簡單來說解釋方式不生成目的碼，編譯方式生成目的碼
10編譯程式採用多遍掃描還是單編掃描需要考慮哪些因素 不一定，多遍編譯器結構清晰，構造時間短，執行時需要記憶體少，產生的目的碼質量高，但時間效率低，
應該根據具體情況決（1）語句的大小與結構，（2）機器規模（3）設計目的（4）設計人員的素質及數量。 11 比較LR（0）,SLR（1）,LR（1）和LALR（1）
分析表的優缺點
（1）LR（0）分析表侷限性大，但其構造方法是其他構造方法的基礎
（2）SLR分析表雖然不是對所有文法都存在，但這種分析表狀態少，儲存空間佔用少，較易實現又極有實用價值。
（3）規範LR分析表，即LR（1）分析表，它的，它的分析能力最強，能適用於一大類文法，但是實現代價過高，主要是體積過大 （4）LALR分析表的能力介於SLR分析表和規範LR分析表之間，稍加努力，就可以高效的實現。
12比較LL（K）分析表與LR（K）分析法 共同點：（1）兩者多借助於可能控制代碼左部的全部符號及向右看K個符號來確定所應執
行的唯一動作，識別過程嚴格地從左到右掃描，無回溯，效率高。（2）都能及時察覺錯誤2。（3）識別程式都能自動生成。 區別：（1）兩者都是嚴格地從左到右掃描，名稱中第一個L隱指這點，但LR分析技術利用的是最右推導（最左歸約），由R隱指，LL（K）分析利用的是最左推導，由第二個L隱指。（2）LL（K）要求文法無左遞迴，滿足無回溯的條件，而LR分析法則無此限制。（3）LL（K）是自上而下構造推導的，而LR（K）是自下而上構造歸約的。 13語法制導翻譯過程：對單詞符號串進行語法分析，構造語法分析樹，構造屬性依賴圖，遍歷語法樹並在語法樹各結點處按語義規則計算順序。
14靜態語義檢查：型別檢查，控制流檢查，一致性檢查，相關名字檢查，名字的作用域分析。
15引入中間程式碼的好處：
（1）便於進行與機器無關的程式碼優化工作 （2）使編譯程式更容易改變目標機
（3）使編譯程式的結構在邏輯上更為簡單明確，以中間語言為界限，編譯前端和後端的介面更清晰。 16編譯程式分類 （1）診斷編譯程式 （2）優化編譯程式 （3）交叉編譯程式 （4）可變目標編譯程式
17編譯程式工作過程5個階段及其任務： （1）詞法分析：任務是從左到右逐個字元的讀入源程式，對構成源程式的字元流進行掃描和分解，進而識別一個個單詞。
（2）語法分析：任務是根據語法規則，分析並識別出各種語法成分，並經行語法正確性檢查。
（3）語義分析與中間程式碼生成：任務是對識別出的各種語法成分進行語義分析，併產生相應的中間程式碼。
（4）目的碼生成：任務是把中間程式碼轉換成特定機器上的`低階語言程式碼。 18編譯程式和解釋程式
（1）編譯程式需要在執行前將原始碼譯成目的碼，解釋程式接受某個語言的程式並立即執行這個源程式
（2）二者儲存組織有著很大不同，編譯程式處理時儲存區要儲存編譯用時需要的各種表格；解釋程式將分析結果存放在源程式區
（3）編譯程式動態性很差，可形成永久性可執行檔案，解釋程式動態性較好。
19程式性合計語言範型：
（1）強制（命令）式語言：c,fortron,pasal （2）函式式語言：ML,Lisp
（3）基於規則（邏輯）的語言：prolog （4）面嚮物件語言：Ada,c++,java
1.推導：
—自上而下的語法分析過程
—預測分析程式，遞迴下降分析法（最左推導）
—注：要求文法是LL(1)文法
2.歸約：
—自下而上的語法分析過程
—簡單優先分析法，算符優先分析法、LR分析法3
3.自下而上的語法分析過程思想
—自下而上的語法分析過程是一個最左歸約的過程，從輸入串開始。朝著文法的開始符號進行歸約，直到到達文法的開始符號為止的過程 注意：輸入串在這裡是指從詞法分析器送來的單詞符號組成的二元式的有限序列 。 即：自左至右把輸入串的符號一個一個移進棧，在移進過程中不斷檢視棧頂符號串，一旦形成某個句型的控制代碼時，就將此控制代碼用相應的產生式左部替換（歸約），若再形成控制代碼，就繼續替換，直到棧頂不再形成控制代碼為止，然後繼續移進符號，重複上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為止，這樣就認為識別了一個句子。
1）初態時棧內僅有棧底符“#”，讀頭指在最左邊的單詞符號上 .
2）語法分析程式執行的動作：
a)移進：讀入一個單詞並壓入棧內，讀頭後移；
b)歸約：檢查棧頂若干個符號能否進行歸約，若能，就以產生式左部替代該符號串，同時輸出產生式編號.
c)識別成功：移進—歸約的結局是棧內只剩下棧底符號和文法開始符號，讀頭也指向語句的結束符.
d)識別失敗.
令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有 S αAδ且A β
則稱β是句型αβδ相對於非終結符A的短語。
特別是，如果有 A β
則稱β是句型αβδ相對於規則A→β的直接短語，一個句型的最左直接短語稱為該句型的控制代碼。
注： 一個句型的語法樹中任一子樹葉節點所組成的符號串就是該句型的短語，當子樹中不包含其他更小的子樹時，該子樹結點所組成的字串就是該句型的直接（簡單）短語。
素短語： 一個遞迴的定義，至少含有一個終結符，並且除它自身之外不在含有任何更小的素短語，（所謂最左素短語就是處於句型最左邊的素短語）。
簡單優先分析法：1.確定相鄰文法符號之間的優先關係 在句型中，控制代碼內各相鄰符號之間具有相同的優先順序，相同優先順序用“ ”
由於控制代碼要先歸約,所以規定控制代碼兩端符號的優先順序要比位於控制代碼之外的相鄰符號的優先順序高,優先順序低於表示為“﹤”,優先順序高於表示為“ ＞”
某句型中:N1…-1< Ni …… Nj ＞ Nj+1…
定義：一個文法G，如果它不含e產生式，也不含任何右部相
同的不同產生式，並且它的任何符號對（X，Y）
X，Y是終結符或非終結符 ——或者沒有關係，
——或者存在優先順序相同或低於、高於等關係之一，
則這是一個簡單優先文法。
1LR(0) 文法：該文法的以 LR(0) 專案集為狀態的識別規範句型活字首的 DFA 中沒有衝突狀態。
2 SLR(1) 文法：該文法的以 LR(0) 專案集為狀態的識別規範句型活字首的 DFA 中有衝突狀態，衝突可用 FOLLOW 集解決。
該文法不是 SLR(1) 文法。
因為 FOLLOW(S)={a,b,#} ，所以無法解決衝突
3算符優先：（T） (<firstvt（T） lastvt（T）>) （6章）
1.靜態語義檢查包括： （1）型別檢查 （2）控制流檢查 （3）一致性檢查 （4）相關名字檢查 （5）名字的作用域分析
2.引入中間程式碼的好處：
（1）便於進行與機器無關的程式碼優化工作 （2）使編譯程式更容易改變目標機
（3）使編譯程式的結構在邏輯上更為簡單
明確，以中間語言為界限，編譯前端和後端的介面更清晰。
（1章） 1.源程式： 用編譯語言或高階語言編寫的程式
目標程式：用目標語言表示的程式
翻譯程式： 將源程式轉換為目標程式的程式。
2.編譯程式分類 （1）診斷編譯程式 （2）優化編譯程式 （3）交叉編譯程式 （4）可變目標編譯程式
3.編譯程式工作過程5個階段及其任務： （1）詞法分析：任務是從左到右逐個字元的讀入源程式，對構成源程式的字元流進行掃描和分解，進而識別一個個單詞。
（2）語法分析：任務是根據語法規則，分析並識別出各種語法成分，並經行語法正確性檢查。
（3）語義分析與中間程式碼生成：任務是對識別出的各種語法成分進行語義分析，併產生相應的中間程式碼。
（4）目的碼生成：任務是把中間程式碼轉換成特定機器上的低階語言程式碼。
4.編譯程式和解釋程式
（1）編譯程式需要在執行前將原始碼譯成目的碼，解釋程式接受某個語言的程式並立即執行這個源程式
（2）二者儲存組織有著很大不同，編譯程式處理時儲存區要儲存編譯用時需要的各種表格；解釋程式將分析結果存放在源程式區
（3）編譯程式動態性很差，可形成永久性可執行檔案，解釋程式動態性較好。
5.程式性合計語言範型：
（1）強制（命令）式語言：c,fortron,pasal （2）函式式語言：ML,Lisp
（3）基於規則（邏輯）的語言：prolog
（4）面嚮物件語言：Ada,c++,java
6.構造編譯程式必須掌握的三方面內容： （1）源程式 （2）目標語言 （3）編譯方法
7.編譯前端和後端
前端：通常指與源程式有關的編譯部分，包括詞法分析，語法分析，語義分析，特點是與源程式有關。
後端：與目標機有關的部分，包括中間程式碼生成，程式碼優化，目標程式生成，特點是與目標機有關。
1.推導：
—自上而下的語法分析過程
—預測分析程式，遞迴下降分析法（最左推導）
—注：要求文法是LL(1)文法
2.歸約：
—自下而上的語法分析過程
—簡單優先分析法，算符優先分析法、LR分析法3
3.自下而上的語法分析過程思想
—自下而上的語法分析過程是一個最左歸約的過程，從輸入串開始。朝著文法的開始符號進行歸約，直到到達文法的開始符號為止的過程 注意：輸入串在這裡是指從詞法分析器送來的單詞符號組成的二元式的有限序列 。 即：自左至右把輸入串的符號一個一個移進棧，在移進過程中不斷檢視棧頂符號串，一旦形成某個句型的控制代碼時，就將此控制代碼用相應的產生式左部替換（歸約），若再形成控制代碼，就繼續替換，直到棧頂不再形成控制代碼為止，然後繼續移進符號，重複上面的過程直到棧頂只剩下文法的開始符號，輸入串讀完為止，這樣就認為識別了一個句子。
1）初態時棧內僅有棧底符“#”，讀頭指在最左邊的單詞符號上 .
2）語法分析程式執行的動作：
a)移進：讀入一個單詞並壓入棧內，讀頭後移；
b)歸約：檢查棧頂若干個符號能否進行歸約，若能，就以產生式左部替代該符號串，同時輸出產生式編號.
c)識別成功：移進—歸約的結局是棧內只剩下棧底符號和文法開始符號，讀頭也指向語句的結束符.
d)識別失敗.
令G是一個文法，S是文法的開始符號，假定αβδ是文法G的一個句型，如果有 S αAδ且A β
則稱β是句型αβδ相對於非終結符A的短語。
特別是，如果有 A β
則稱β是句型αβδ相對於規則A→β
的直接短語，一個句型的最左直接短語稱為該句型的控制代碼。
注： 一個句型的語法樹中任一子樹葉節點所組成的符號串就是該句型的短語，當子樹中不包含其他更小的子樹時，該子樹結點所組成的字串就是該句型的直接（簡單）短語。
素短語： 一個遞迴的定義，至少含有一個終結符，並且除它自身之外不在含有任何更小的素短語，（所謂最左素短語就是處於句型最左邊的素短語）。
簡單優先分析法：1.確定相鄰文法符號之間的優先關係 在句型中，控制代碼內各相鄰符號之間具有相同的優先順序，相同優先順序用“ ”
由於控制代碼要先歸約,所以規定控制代碼兩端符號的優先順序要比位於控制代碼之外的相鄰符號的優先順序高,優先順序低於表示為“﹤”,優先順序高於表示為“ ＞”
某句型中:-1< Ni Nj ＞ Nj+
定義：一個文法G，如果它不含e產生式，也不含任何右部相
同的不同產生式，並且它的任何符號對（X，Y）
X，Y是終結符或非終結符 ——或者沒有關係，
——或者存在優先順序相同或低於、高於等關係之一，
則這是一個簡單優先文法。
編譯原理期末總結 [篇3]
1.簡要說明語義分析的基本功能。
答：語義分析的基本功能包括: 確定型別、型別檢查、語義處理和某些靜態語義檢 查。
1.編譯方式和解釋方式的根本區別是什麼？
編譯方式：是將源程式經編譯得到可執行檔案後，就可脫離源程式和編譯程式單獨執行，所以編譯方式的效率高，執行速度快；解釋方式：在執行時，必須源程式和解釋程式同時參與才能執行，其不產生可執行程式檔案，效率低，執行速度慢。
2．編譯程式有哪些主要構成成分？各自的主要功能是什麼？ 編譯程式的主要構成成分有：詞法分析程式、語法分析程式、語義分析程式、中間程式碼 生成程式、程式碼優化程式、目的碼生成程式、表格管理程式及出錯處理程式。 （1）詞法分析程式：從左到右掃描源程式，識別單詞及其有關屬性； （2）語法分析程式：分析源程式的結構, 判別它是否為相應程式設計語言中的一個合法 程式； （3）語義分析程式：審查源程式有無語義錯誤，為程式碼生成階段收集型別資訊； （4）中間程式碼生成程式：將源程式變成一種內部表示形式；
3什麼是解釋程式？它與編譯程式的主要不同是什麼？ 解釋程式接受某個語言的程式並立即執行這個源程式。它的工作模式是一個個的獲取、 分析並執行源程式語句，一旦第一個語句分析結束，源程式便開始執行並且生成結果，它特 別適合程式設計師互動方式的工作情況。 而編譯程式是一個語言處理程式，它把一個高階語言程式翻譯成某個機器的彙編或二進 制程式碼程式，這個二進位制程式碼程式再機器上執行以生成結果。 它們的主要不同在於：解釋程式是邊解釋邊執行，解釋程式執行結束即可得到該程式的 執行結果， 而編譯程式只是把源程式翻譯成彙編或者二進位制程式， 這個程式再執行才能得到 程式的執行結果。 （當然還有其他不同，比如儲存組織方式不同）
什麼是控制代碼？什麼是素短語？
一個句型的最左直接短語稱為該句型的控制代碼。
詞法分析 詞法分析的主要任務是從左向右掃描每行源程式的符號，按照詞法規則 從構成源程式的字串中識別出一個個具有獨立意義的最小語法單位，
並轉換成統一的內部表示(token)，送給語法分析程式。
編譯程式的工作分為那幾個階段?
詞法分析、語法分析和語義分析是對源程式進行的分析(稱為編譯程式的前端)， 而中間程式碼生成、程式碼優化和程式碼生成三個階段合稱為對源程式進行綜合(稱為
編譯程式的後端)，它們從源程式的中間表示建立起和源程式等價的目標程式。
簡述自下而上的分析方法。
開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節點。
4．簡述程式碼優化的目的和意義。
一種等價變換，在保證變換前後程式碼執行結果相同的前提下，儘量使目 標程式執行時所需要的時間短，同時所佔用的儲存空間少。
LR(0)分析器
每一步，只須根據分析棧當前已移進和歸約出的全部文法符號，並至多再
向前檢視0個輸入符號，就能確定相對於某一產生式左部符號的控制代碼是否
已在分析棧的頂部形成，從而也就可以確定當前所應採取的分析動作 (是 移進還是按某一產生式進行歸約等)。
第四章
1. 設有如下文法G[S]:
SaABbcd |
AASd |
BSAh | eC |
CSf | Cg |
(1) 求每個產生式的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 )={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
構造相應的最小的DFA 。
解：先構造其NFA： 用子集法將NFA確定化：
將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因為3、4中含有z，所以它們為終態。
令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）文法，如果是，給出其預測分析表。（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) 計算該文法的每一個非終結符的FIRST集和FOLLOW集； (2)
是
二、設={0，1}上的正規集S由倒數第二個字元為1的所有字串組成，請給出該字集對應的正規式，並構造一個識別該正規集的DFA。(8分)
答：
構造相應的正規式：(0|1)*1(0|1) (3分) NFA: (2分)
1
編譯原理期末總結 [篇4]
第一章 引論
為什麼要用編譯器
與編譯器相關的程式
翻譯步驟
編譯器中的主要資料結構
1、語言處理器
1、簡單的說，一個編譯器就是一個程式，它可以閱讀以某一種語言（源語言）編寫的程式，並把該程式翻譯成一個等價的、用另一種語言（目標語言）編寫的程式。
2、編譯器的重要任務之一就是報告它在翻譯過程中發現的源程式中的錯誤。
3、使用編譯器是為了提高程式設計的速度和準確度。
4、與編譯器相關的程式：解釋程式（interpreter）、彙編程式（assembler）、連線程式（linker）、裝入程式（loader）、前處理器（preprocessor）、編輯器（editor）、除錯程式（debugger）、描述器（profiler）、專案管理程式（project manager）。
5、直譯器是另一種常見的語言處理器。它並不通過翻譯的方法生成目標程式。從使用者的角度來看，直譯器直接利用使用者提供的輸入執行源程式中指定的操作。
Object Source
Program
Output
6、一個源程式可能被分割成多個模組，並存放於獨立的檔案中。把源程式聚合在一起的任務有時會由一個被稱為前處理器（preprocessor）的程式獨立完成。前處理器還負責把那些稱為巨集的縮寫形式轉換為源語言的語句。
7、聯結器（linker）能夠解決外部記憶體地址的問題。
8、載入器（loader）把所有的可執行目標檔案放到記憶體中執行。
2、一個編譯器的結構
Front end Back end
1、將編譯器看成黑盒，則源程式對映為在語義上等價的目標程式，而這個對映由兩部分組成：分析部分和綜合部分。
2、分析部分把源程式分解成多個組成要素，並在這些要素之上加上語法結構。
3、綜合部分根據中間表示和符號表中的資訊來構造使用者期待的目標程式。
4、編譯器的第一個步驟：詞法分析（lexical）或掃描（scanning）。詞法分析器讀入組成源程式的字元流，並且將它們組成有意義的詞素（lexeme）的序列。詞法分析器產生詞法單元（token）。
5、分隔詞素的空格會被詞法分析器忽略掉。
6、編譯器的第二個步驟：語法分析（syntax）或解析（parsing）。語法分析器使用由詞法分析器生成的各個詞法單元的第一個分量來建立樹形的中間表示。
7、語義分析（static semantic analysis）：語義分析器使用語法樹和符號表中的資訊來檢查源程式是否和語言定義的語義一致。它同時也收集型別資訊，並把這些資訊存放在語法樹或符號表中，以便在隨後的中間程式碼生成過程中使用。語義分析的一個重要部分是型別檢查（type checking）。編譯器檢查每個運算子是否具有匹配的運算分量。
8、總的說，編譯器的翻譯步驟是：掃描程式----語法分析程式----語義分析程式----原始碼優化程式----程式碼生成器----目的碼優化程式。
3、編譯器結構中的主要資料結構
1、記號（token）
2、語法樹（syntax tree）
3、符號表（symbol table）
4、常數表（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、 連結，由並置表示（不用元字元）
3、 重複或“閉包”，由元字元“*”表示
3、從各選擇物件中選擇：
4、連結：正則表示式r和正則表示式s的連線可寫作rs
5、重複：正則表示式的重複有時稱為Kleene閉包（（Kleene）closure），寫作r*
6、運算的優先和括號的使用：前面的內容忽略了選擇、連線和重複的優先問題。
7、正則表示式的名字：為較長的正則表示式提供一個簡化了的名字很有用處，這樣就不再需要在每次使用正則表示式時書寫常常的表示式本身了。
3、有窮自動機（有窮狀態機）：是描述（或“機器”）特定型別演算法的數學方法。
1、確定性有窮自動機：下一個狀態由當前狀態和當前輸入字元惟一給出的自動機。
2、非確定性有窮自動機：由它產生的。
4、從正則表示式到DFA
1、構造一個個掃描程式的自動過程可分為3步
2、從正則表示式到
NFA
3、從NFA到
DFA
4、將DFA中的狀態最小化
第三章 上下文無關文法及分析
分析過程
上下文無關文法
上下文無關語言的形式特性
分析樹與抽象語法樹
二義性
1、分析過程：
2、上下文無關文法：
3、分析樹與抽象語法樹：
4、二義性：
可生成帶有兩個不同分析樹的串的文法稱作二義性文法（ ambiguous grammar） 有兩個解決二義性的基本方法。
其一是：設定一個規則，該規則可在每個二義性情況下指出哪一個分析樹（或語法樹）是正確的。
另一種方法是將文法改變成一個強制正確分析樹的構造的格式，這樣就可以解決二義性了。
第四章 自頂向下的分析
使用遞迴下降分析演算法進行自頂向下的分析
LL(1)分析
First 集合和F o l l o w集合
1、使用遞迴下降分析演算法進行自頂向下的分析
2、LL(1) 分析方法是這樣得名的：第1個“L”指的是由左向右地處理輸入（一些舊式的分析程式慣於自右向左地處理輸入，但現在已不常用了）。第2個“L”指的是它為輸入串描繪出一個最左推導。括號中的數字1意味著它僅使用輸入中的一個符號來預測分析的方向。
3、定義：如果文法G相關的L L ( 1 )分析表的每個專案中至多隻有一個產生式，則該文法 就是L L ( 1 )文法(LL(1) grammar)。
