1、計算機編譯原理編譯器與解釋器編譯器與解釋器v編譯器編譯器（編譯程序）：如果源語言是某種高級語言，（編譯程序）：如果源語言是某種高級語言，而目標語言是某種低級語言（匯編語言或機器語而目標語言是某種低級語言（匯編語言或機器語言），這樣的一個翻譯程序就稱為編譯程序。言），這樣的一個翻譯程序就稱為編譯程序。v 解釋器解釋器（解釋程序）：這是另外一種類型的翻譯（解釋程序）：這是另外一種類型的翻譯程序，在翻譯過程中它按照高級語言源程序在計算程序，在翻譯過程中它按照高級語言源程序在計算機上執行的動態順序對源程序的語句逐條翻譯（解機上執行的動態順序對源程序的語句逐條翻譯（解釋），邊解釋邊執行直至結束，它不產生

2、目標程序，釋），邊解釋邊執行直至結束，它不產生目標程序，它的工作結果就是源程序的執行結果，這樣的一個它的工作結果就是源程序的執行結果，這樣的一個翻譯程序就稱為解釋程序。翻譯程序就稱為解釋程序。編譯器與解釋器編譯器與解釋器例5 假設有源程序：read(x); write(x=, x);read(x);write(“x=”,x);目標程序目標程序3x=3編譯器解釋器read(x);write(“x=”,x);3x=3編譯器與解釋器編譯器與解釋器v特點：特點：1 1編譯器：工作效率高，即時間快、空間省；交互編譯器：工作效率高，即時間快、空間省；交互性與動態特性差、可移植性差。大多數性與動態特性差、可

3、移植性差。大多數PLPL采用此種方采用此種方法翻譯；法翻譯；2 2解釋器：工作效率低，即時間慢、空間費；交互解釋器：工作效率低，即時間慢、空間費；交互性與動態特性好、可移植性好。早期的性與動態特性好、可移植性好。早期的BasicBasic和現在和現在的的JavaJava等。等。v基本功能基本功能：二者相同；：二者相同；v所采用的技術所采用的技術：從翻譯的角度來講，兩種方式所涉：從翻譯的角度來講，兩種方式所涉及的原理、方法、技術相似。及的原理、方法、技術相似。編譯器編譯器v根據不同的用途和側重，編譯程序還可進一步分類。根據不同的用途和側重，編譯程序還可進一步分類。專門用于幫助程序開發和調試的編譯

4、程序稱為專門用于幫助程序開發和調試的編譯程序稱為診斷編診斷編譯程序譯程序（Diagnostic CompilerDiagnostic Compiler）；著重于提高目標）；著重于提高目標代碼效率的編譯程序叫代碼效率的編譯程序叫優化編譯程序優化編譯程序（Optimizing Optimizing CompilerCompiler）。）。v現在很多編譯程序同時提供了調試、優化等多種功現在很多編譯程序同時提供了調試、優化等多種功能，用戶可以通過能，用戶可以通過“開關開關”進行選擇。運行編譯程序進行選擇。運行編譯程序的計算機稱的計算機稱宿主機宿主機，運行編譯程序所產生目標代碼的，運行編譯程序所產生目標

5、代碼的計算機稱計算機稱目標機目標機。如果一個編譯程序產生不同于其宿。如果一個編譯程序產生不同于其宿主機的機器代碼，則稱它為主機的機器代碼，則稱它為交叉編譯程序交叉編譯程序(Cross (Cross Compiler)Compiler)。如果不需重寫編譯程序中與機器無關的。如果不需重寫編譯程序中與機器無關的部分就能改變目標機，則稱該編譯程序為部分就能改變目標機，則稱該編譯程序為可變目標編可變目標編譯程序譯程序（Retargetable CompilerRetargetable Compiler）。）。編譯的階段編譯的階段v編譯器從邏輯上可編譯器從邏輯上可以分成若干階段，以分成若干階段，每個階段把

6、源程序每個階段把源程序從一種表示變換成從一種表示變換成另一種表示。另一種表示。詞 法 分 析語 法 分 析語 義 分 析中 間 代 碼 生 成代 碼 優 化目 標 代 碼 生 成源 程 序目 標 代 碼符號表管理出錯處理編譯的階段編譯的階段v把英文翻譯為中文把英文翻譯為中文 識別出句子中的一個個單詞；識別出句子中的一個個單詞；分析句子的語法結構；分析句子的語法結構；根據句子的含義進行初步翻譯；根據句子的含義進行初步翻譯；對譯文進行修飾；對譯文進行修飾；寫出最后的譯文。寫出最后的譯文。 詞法分析詞法分析語法分析語法分析中間代碼中間代碼產生產生優化優化目標代碼目標代碼產生產生詞法分析詞法分析v任務

7、任務: : 輸入源程序，對構成源程序的字符串進行掃輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單詞符號。描和分解，識別出一個個單詞符號。v依循的原則：構詞規則依循的原則：構詞規則v描述工具：正規式和有限自動機描述工具：正規式和有限自動機 。詞法分析詞法分析詞法分析器詞法分析器 id, 1 = id, 2 + id, 3 60 position = initial + rate 60符符 號號 表表 positioninitialrate. . . . . . .123語法分析語法分析v任務任務: :在詞法分析的基礎上，根據語言的語法規則在詞法分析的基礎上，根據語言的語法規則把單

8、詞符號串分解成各類語法單位。如程序、語句、把單詞符號串分解成各類語法單位。如程序、語句、表達式等。表達式等。v依循的原則：語法規則依循的原則：語法規則v描述工具：上下文無關文法描述工具：上下文無關文法v詞法分析是一種線性分析，而語法分析是一種層次詞法分析是一種線性分析，而語法分析是一種層次結構分析。結構分析。 語法分析語法分析v表達式的語法特征：表達式的語法特征：任何一個標識符任何一個標識符都是表達式都是表達式任何一個數都是任何一個數都是表達式表達式如果如果e e1 1和和e e2 2都是都是表達式，那么表達式，那么ve e1 + 1 + e e2 2ve e1 1 * * e e2 2 v(

9、 (e e1)1)也都是表達式也都是表達式表達式表達式表達式表達式表達式表達式標識符標識符表達式表達式表達式表達式(initial)標識符標識符(rate)數數(60)*+initial + rate * * 60分析樹分析樹語法分析語法分析語法分析器語法分析器 id, 1 = id, 2 + id, 3 60 = + 60 id, 1 id, 2 id, 3 符符 號號 表表 positioninitialrate. . . . . . .123語法樹語法樹語義分析語義分析v任務：任務：v依循的原則：語義規則依循的原則：語義規則v語義分析的一個重要部分是類型檢查，編譯語義分析的一個重要部分是

10、類型檢查，編譯器檢查每個算符的運算對象，看它們的類型器檢查每個算符的運算對象，看它們的類型是否適當。如：實數作為數組下標，報錯；是否適當。如：實數作為數組下標，報錯；整數和實數進行運算時，將整數轉變為實數。整數和實數進行運算時，將整數轉變為實數。語義分析語義分析語義分析器語義分析器 = + 60 id, 1 id, 2 id, 3 = + Inttoreal id, 1 id, 2 id, 3 60 符符 號號 表表 positioninitialrate. . . . . . .123中間代碼生成中間代碼生成v任務：任務：“翻譯翻譯”僅僅在這里才僅僅在這里才開始涉及到。開始涉及到。 v中間代

11、碼：三元式，四元式，樹形結構等。中間代碼：三元式，四元式，樹形結構等。中間代碼生成中間代碼生成中間代碼生成器中間代碼生成器t1 = inttoreal(60)t2 = id3 t1t3 = id2 + t2id1 = t3 = + inttoreal id, 1 id, 2 id, 3 60 符符 號號 表表 positioninitialrate. . . . . . .123中間代碼生成中間代碼生成v上面的例子表示成四元式：上面的例子表示成四元式：代碼優化代碼優化v任務：對于前階段產生的中間代碼進行加工變換，任務：對于前階段產生的中間代碼進行加工變換，以期在最后階段產生更高效的目標代碼。以

12、期在最后階段產生更高效的目標代碼。v依循的原則：程序的等價變換規則依循的原則：程序的等價變換規則v優化的主要方面有：公共子表達式的提取、循環優優化的主要方面有：公共子表達式的提取、循環優化、刪除無用代碼等等。化、刪除無用代碼等等。代碼優化代碼優化代碼優化器代碼優化器t1 = inttoreal(60)t2 = id3 t1t3 = id2 + t2id1 = t3t1 = id3 * * 60.0id1 = id2 + t1符符 號號 表表 positioninitialrate. . . . . . .123代碼生成代碼生成v任務任務: : 把中間代碼變換成特定機器上的目標代碼。把中間代碼變

13、換成特定機器上的目標代碼。v特點：特點： v目標代碼三種形式目標代碼三種形式: :絕對指令代碼絕對指令代碼: : 可直接運行可直接運行 可重定位指令代碼可重定位指令代碼: : 需要連接裝配（多數）需要連接裝配（多數）匯編指令代碼匯編指令代碼: : 需要進行匯編需要進行匯編代碼生成代碼生成代碼生成器代碼生成器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1t1 = id3 * * 60.0id1 = id2 + t1符符 號號 表表 positioninitialrate. . . . . . .123符號表管理符號表管理

14、v符號表：用來登記源程序中出現的每個名字以及名字的各種符號表：用來登記源程序中出現的每個名字以及名字的各種屬性。例如，一個名字是常量名、變量名，還是過程名等等；屬性。例如，一個名字是常量名、變量名，還是過程名等等；若是變量名，它的類型、所占內存、地址等等。若是變量名，它的類型、所占內存、地址等等。v通常，編譯程序在處理到名字的定義性出現時，要把名字的通常，編譯程序在處理到名字的定義性出現時，要把名字的各種屬性填入到符號表中；當處理到名字的使用性出現時，各種屬性填入到符號表中；當處理到名字的使用性出現時，要對名字的屬性進行查證。要對名字的屬性進行查證。v當掃描器識別出一個名字（標識符）后，它把該

15、名字填入到當掃描器識別出一個名字（標識符）后，它把該名字填入到符號表中。但這時不能完全確定名字的屬性，它的各種屬性符號表中。但這時不能完全確定名字的屬性，它的各種屬性要在后續的各階段才能填入。例如，名字的類型等要在語義要在后續的各階段才能填入。例如，名字的類型等要在語義分析時才能確定，而名字的地址可能要到目標代碼生成才能分析時才能確定，而名字的地址可能要到目標代碼生成才能確定。確定。錯誤診斷和報告錯誤診斷和報告v出錯處理程序：發現源程序中的錯誤，把有關錯誤出錯處理程序：發現源程序中的錯誤，把有關錯誤信息報告給用戶。信息報告給用戶。語法錯誤語法錯誤語義錯誤語義錯誤v好的編譯程序應能最大限度地發現

16、源程序中的各種好的編譯程序應能最大限度地發現源程序中的各種錯誤，準確地指出錯誤的性質和發生錯誤的地點，錯誤，準確地指出錯誤的性質和發生錯誤的地點，并且能將錯誤所造成的影響限制在盡可能小的范圍并且能將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續被編譯下去，以內，使得源程序的其余部分能繼續被編譯下去，以便進一步發現其它可能的錯誤。便進一步發現其它可能的錯誤。階段的分組階段的分組階段與遍是不同的概念。一遍階段與遍是不同的概念。一遍可以由若干段組成，一個階段也可以分若干遍來完成。可以由若干段組成，一個階段也可以分若干遍來完成。編譯器的編寫編譯器的編寫v直接使用匯編語言和程序設計語

17、言；直接使用匯編語言和程序設計語言；v利用編譯器編寫工具：詞利用編譯器編寫工具：詞/ /語法、語法制導翻譯、語法、語法制導翻譯、代碼生成、數據流分析等；代碼生成、數據流分析等；v基于編譯器基礎架構的編譯器構造系統（開放式基于編譯器基礎架構的編譯器構造系統（開放式編譯器，如編譯器，如GCCGCC、SUIFSUIF等）。等）。 GCC Home PageGCC Home Page. . . . Gasta HomepageGasta Homepage. http:/. http:/SUIF Compiler System Home PageSUIF Compiler