1、編譯編譯原理原理及及實現實現技術技術課程內容課程內容 介紹編譯器介紹編譯器 基本構造原理基本構造原理 基本實現方法基本實現方法 基本處理技術基本處理技術 介紹理論知識介紹理論知識 形式語言形式語言 自動機理論自動機理論 強調強調 形式化描述形式化描述技術技術 抽象思想抽象思想 強調強調 對編譯原理對編譯原理宏觀理解宏觀理解 對編譯處理技術的對編譯處理技術的宏觀宏觀理解理解課程意義課程意義 掌握編譯程序的構造原理和實現技術。掌握編譯程序的構造原理和實現技術。 深入對程序設計語言的理解；（片面深入對程序設計語言的理解；（片面vsvs全面）全面） 提高軟件開發能力；（同一功能的不同實現）提高軟件開發

2、能力；（同一功能的不同實現） 提高元級程序設計能力；（編譯器的設計實現）提高元級程序設計能力；（編譯器的設計實現） 增強形式化、抽象化能力；（問題形式化）增強形式化、抽象化能力；（問題形式化） 編譯技術的廣泛的應用。編譯技術的廣泛的應用。 嵌入式系統（受限資源利用）嵌入式系統（受限資源利用） ERPERP二次開發（三分之一需要修改）二次開發（三分之一需要修改） 冗余代碼分析（變量調用、閑置函數）冗余代碼分析（變量調用、閑置函數）第一章第一章 編譯引論編譯引論程序設計語言程序設計語言程序設計環境中的編譯器程序設計環境中的編譯器編譯程序的結構編譯程序的結構編譯程序的設計與實現編譯程序的設計與實現1

3、 1 程序設計語言與編譯程序程序設計語言與編譯程序程序語言的發展程序語言的發展高級語言的實現方式高級語言的實現方式1.11.1 程序設計語言的發展程序設計語言的發展機器語言機器語言：能夠被計算機的硬件系統直接執行的：能夠被計算機的硬件系統直接執行的指令程序，如指令程序，如“00010001010001000101”。匯編語言匯編語言：將硬件指令用一些助記符表示，即符：將硬件指令用一些助記符表示，即符號化的機器語言，如號化的機器語言，如“ADDADD，MOVMOV”。高級語言高級語言：從程序員的角度出發，對匯編語言進：從程序員的角度出發，對匯編語言進一步抽象，使用便于理解的一步抽象，使用便于理解

4、的“自然語言自然語言”表述。表述。 機器語言機器語言 匯編語言匯編語言 高級語言高級語言 翻譯程序翻譯程序TranslatorTranslator1.21.2 高級語言的實現方式高級語言的實現方式匯編程序匯編程序AssemblerAssembler編譯程序編譯程序CompilerCompiler1.2.11.2.1 解釋方式解釋方式 解釋方式：解釋方式：接受用程序語言（源語言）編寫的接受用程序語言（源語言）編寫的程序（源程序），然后直接解釋執行源程序。程序（源程序），然后直接解釋執行源程序。解釋器相當于源程序的抽象執行機，是語言的解釋器相當于源程序的抽象執行機，是語言的實現系統。實現系統。 解

5、釋程序解釋程序源程序源程序輸入數據輸入數據計算結果計算結果( (* *. .bas/bas/* *.java).java)1.2.21.2.2 編譯方式編譯方式 編譯方式：編譯方式：源語言為高級語言，目標語言是低源語言為高級語言，目標語言是低級語言（匯編或機器語言）的翻譯程序。級語言（匯編或機器語言）的翻譯程序。 源程序源程序目標程序目標程序( (* *. .C/C/* *.PAS).PAS)( (* *. .OBJ/OBJ/* *.EXE).EXE)編譯程序編譯程序1.2.3 1.2.3 轉換方式轉換方式 轉換方式：轉換方式：將將A A語言程序轉換為語言程序轉換為B B語言程序，用語言程序，

6、用B B語言已有的編譯器去編譯執行。（同級程序語言已有的編譯器去編譯執行。（同級程序設計語言）設計語言） 編譯、解釋編譯、解釋A A語言程序語言程序轉換程序轉換程序B B語言程序語言程序源程序源程序目標程序目標程序( (* *. .C/C/* *.PAS).PAS)( (* *. .OBJ/OBJ/* *.EXE).EXE)解釋程序解釋程序源程序源程序輸入數據輸入數據計算結果計算結果( (* *. .bas/bas/* *.java).java)A A語言程序語言程序轉換程序轉換程序編譯程序編譯程序B B語言程序語言程序2 2 編譯程序和程序設計環境編譯程序和程序設計環境典型典型IDEIDE編

7、譯器在編譯器在IDEIDE中的位置中的位置 編輯器編輯器：除了一般文本編輯器的功能外，還可具除了一般文本編輯器的功能外，還可具有對正在編輯的文本進行分析、提示，能自動地有對正在編輯的文本進行分析、提示，能自動地提供關鍵字和與其匹配的關鍵字提供關鍵字和與其匹配的關鍵字 等功能。等功能。 預處理器預處理器：工作包括刪除源程序中的注釋、執行：工作包括刪除源程序中的注釋、執行宏替換以及包含文件的嵌入等。宏替換以及包含文件的嵌入等。 編譯器編譯器簡約而不簡單簡約而不簡單 連接程序連接程序：將不同的目標文件中編譯或匯編的代：將不同的目標文件中編譯或匯編的代碼集中到一個可執行文件中，并將目標和標準庫碼集中到

8、一個可執行文件中，并將目標和標準庫函數的代碼以及計算機的操作系統提供的資源連函數的代碼以及計算機的操作系統提供的資源連接在一起。接在一起。 裝入程序裝入程序：把程序加載到內存儲器中，以便執行。：把程序加載到內存儲器中，以便執行。 調試程序調試程序：檢查編譯了的程序中的錯誤。：檢查編譯了的程序中的錯誤。 3 3 編譯程序的邏輯結構編譯程序的邏輯結構編譯器的結構編譯器的結構各組成部分的功用各組成部分的功用實例實例編譯器 3.1 3.1 編譯程序的邏輯結構圖編譯程序的邏輯結構圖詞法分析詞法分析語法分析語法分析語義分析語義分析源程序源程序中間代碼生成中間代碼生成中間代碼優化中間代碼優化目標代碼生成目標

9、代碼生成目標程序目標程序出錯處理出錯處理表格管理表格管理 詞法分析詞法分析Lexical Analysis(Scanner/Tokenizer)Lexical Analysis(Scanner/Tokenizer) 掃描源程序的字符串，依循語言的詞法規則，識掃描源程序的字符串，依循語言的詞法規則，識別每一個有集體含義的子串，并將其表示成所謂別每一個有集體含義的子串，并將其表示成所謂的機內表示記號形式（的機內表示記號形式（TokenToken）。 語法分析語法分析 Syntax Analysis(Parser)Syntax Analysis(Parser)依據語言的依據語言的語法規則，將單詞的語

10、法規則，將單詞的TokenToken序列分解成各類序列分解成各類語法短語法短語（可表示為語法樹）語（可表示為語法樹），確定整個輸入串是否構，確定整個輸入串是否構成一個語法上正確的程序。成一個語法上正確的程序。 語義分析語義分析 Semantic AnalysisSemantic Analysis 檢查源程序有無檢查源程序有無語義錯誤，為代碼生成階段收集信息。（類型檢語義錯誤，為代碼生成階段收集信息。（類型檢查、強制類型轉換、下標越界檢查等）查、強制類型轉換、下標越界檢查等） 中間代碼生成中間代碼生成 Intermediate Code Generation Intermediate Code

11、Generation 將源程序轉換成一種稱為中間代碼的內部表示形將源程序轉換成一種稱為中間代碼的內部表示形式。中間代碼是一種式。中間代碼是一種簡單的、含義明確的記號系簡單的、含義明確的記號系統，統，例如四元式（運算符，對象例如四元式（運算符，對象1 1，對象，對象2 2，結，結果）。果）。 中間代碼優化中間代碼優化 Code OptimizationCode Optimization 變換或改造變換或改造中間代碼，生成的目標代碼更為中間代碼，生成的目標代碼更為高效高效，即節省時，即節省時間和空間。間和空間。 目標代碼生成目標代碼生成 Target Code GenerationTarget C

12、ode Generation 中間代中間代碼變換為特定機器上的絕對碼變換為特定機器上的絕對指令代碼指令代碼，或可重定，或可重定位的指令代碼或匯編指令代碼。位的指令代碼或匯編指令代碼。 表格管理表格管理 Table ManagementTable Management 為了合理的管理為了合理的管理（構造、查找、更新（構造、查找、更新）表格（符號表、類型）表格（符號表、類型信息表信息表），設立一些專門子程序稱為表格管），設立一些專門子程序稱為表格管理程序。理程序。 錯誤處理錯誤處理 Error HandlerError Handler 各個階段還存在著錯誤各個階段還存在著錯誤處理模塊，當有錯誤出現

13、時，由相應的錯誤處理處理模塊，當有錯誤出現時，由相應的錯誤處理模塊給出解決方案，使得編譯器能夠繼續進行下模塊給出解決方案，使得編譯器能夠繼續進行下去。去。3.2 Example of a piece of C code: 3.2 Example of a piece of C code: realreal sum, first; sum, first;intint count; count;sum = first + count sum = first + count * * 10; 10; Out of the Out of the scannerscannerrealrealReserve

14、dReservedsumsumIdentifierIdentifierfirstfirstIdentifierIdentifier; ;SemicolonSemicolonintintReservedReservedcountcountIdentifierIdentifiersumsumIdentifierIdentifier= =EqualEqualfirst first IdentifierIdentifier+ +AddAdd Out of the Out of the parserparserAssignmentAssignmentIdentifierIdentifierEqualEq

15、ualExpressionExpressionsumsum= =ExpressionExpressionAddAddExpressionExpressionIdentifierIdentifier+ +IdentifierIdentifierMulMulVariableVariablefirstfirstcountcount* *1010 Out of the Out of the semantic analyzersemantic analyzer= =Id1Id1+ +Id2Id2* *Id3Id3int_to_realint_to_real1010 Out of the Out of t

16、he intermediate code intermediate code generatorgenerator1.1.(int_to_real,10,-,t1)(int_to_real,10,-,t1)2.2.( (* *,id3,t1,t2),id3,t1,t2)3.3.(+,id2,t2,t3)(+,id2,t2,t3)4.4.(=,t3,-,id1)(=,t3,-,id1) Out of the Out of the optimizeroptimizer1.1.( (* *,10.0,id3,t1),10.0,id3,t1)2.2.(+,t1,id2,id1)(+,t1,id2,id

17、1) Out of the Out of the target code generatortarget code generator1.1.MOVMOVid3,id3,R1R12.2.MULMUL#10.0,#10.0,R1R13.3.MOVMOVid2,id2,R2R24.4.ADDADDR2,R2,R1R15.5.MOVMOVR1,R1,id1 id1 4 4 編譯程序的設計與實現編譯程序的設計與實現4.1 4.1 編譯程序設計編譯程序設計 分遍分遍 根據需求一至幾十遍都有根據需求一至幾十遍都有 要點要點 準確理解源語言準確理解源語言 確定對編譯的要求（可能導致過程差異）確定對編譯的要求（可能導致過程差異） 理解目標機（即目標程序的細節）理解目標機（即目標程序的細節） 形式化描述（正則表達式、自動機）形式化描述（正則表達式、自動機） 具體設計具體設計4.2 4.2 實現方法實現方法 轉換法轉換法：將：將A A語言程序轉換成語言程序轉換成B B語言的程序，再利語言的程序，再利用用B B語言的編譯器實現語言的編譯器實現A