編譯原理-1引論

1、 一. 什么叫編譯程序 二. 編譯過程概述 三. 編譯程序的結構 四. 編譯程序生成 五. 課程學習指導編譯程序編譯程序是系統(tǒng)軟件系統(tǒng)軟件中資格最老的成員之一資格最老的成員之一編譯理論和技術近30年來發(fā)展十分迅速、成熟發(fā)展十分迅速、成熟1.1.編譯程序歷史編譯程序歷史現(xiàn)已形成一套較為系統(tǒng)化的系統(tǒng)化的編譯理論和技術2.2.編譯理論與其他課程關系編譯理論與其他課程關系編譯理論編譯理論自動機和形式語言離散數(shù)學數(shù)據(jù)結構操作系統(tǒng)素材素材基礎基礎控制對象控制對象編譯理論編譯理論 的許多想法和技術可用于一般軟件的設計一般軟件的設計：3.3.編譯理論的應用編譯理論的應用有窮狀態(tài)技術有窮狀態(tài)技術模式識別模式識別

2、情報檢索情報檢索文本編輯程序文本編輯程序上下文無關文法上下文無關文法語法制導翻譯語法制導翻譯建立多種文本處理程序建立多種文本處理程序代碼優(yōu)化技術代碼優(yōu)化技術由非結構化到結構化的程序轉換由非結構化到結構化的程序轉換程序校驗程序校驗翻譯程序（翻譯程序（TranslatorTranslator）是一種程序，其輸入輸入是某種語言某種語言的一系列語句，而其輸出輸出則是另一種語言另一種語言的一系列語句。4.4.翻譯程序翻譯程序源語言程序源語言程序目標語言程序目標語言程序TranslatorTranslator輸入輸入輸出輸出編譯程序（編譯程序（CompilerCompiler）是一種程序。它把用高級語言寫

3、的高級語言寫的源程序源程序作為數(shù)據(jù)接收接收，經過翻譯轉換，產生面向機器的代面向機器的代碼碼作為輸出輸出。這當中代碼還可能要由匯編程序匯編程序或裝配程序裝配程序作進一步加工，得出目標程序目標程序，交給計算機執(zhí)行。5.5.編譯程序編譯程序高級語言源程序高級語言源程序面向機器代碼面向機器代碼CompilerCompiler目標程序代碼目標程序代碼匯編匯編 裝配裝配6.6.翻譯與編譯比較翻譯與編譯比較源語言程序源語言程序目標語言程序目標語言程序轉變?yōu)檗D變?yōu)楦呒壵Z言源程序高級語言源程序面向機器代碼面向機器代碼編譯為編譯為這種變換程序稱為翻譯程序翻譯程序編譯程序編譯程序 有一些限制 （針對輸入、輸出）（針

4、對輸入、輸出）這種變換程序稱為編譯程序編譯程序1.1.編譯過程的組成編譯過程的組成編譯過程編譯過程詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成源程序源程序單詞符號單詞符號中間代碼中間代碼語法單位語法單位目標代碼目標代碼中間代碼（優(yōu)化后）中間代碼（優(yōu)化后）源程序源程序目標代碼目標代碼2.2.詞法分析詞法分析任務任務所做轉換所做轉換依據(jù)依據(jù)構詞規(guī)則構詞規(guī)則主要理論基礎主要理論基礎自動機理論自動機理論源程序字符串源程序字符串單詞符號單詞符號輸入源程序；掃描、分解字符串，識別出一輸入源程序；掃描、分解字符串，識別出一個個單詞（定義符、標識符、運算符、

5、界符、個個單詞（定義符、標識符、運算符、界符、常數(shù)）常數(shù)）2.2.詞法分析詞法分析示例示例FOR K := 1 TO 100FOR K := 1 TO 100 M := I + 10 M := I + 10 * * K K N := J + 10 N := J + 10 * * K KNEXT KNEXT KTOTONEXTNEXTFORFOR K KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +定義符定義符標識符標識符分界符分界符運算符運算符 常數(shù)常數(shù)3.3.語法分析語法分析任務任務所做轉換所做轉換依據(jù)依據(jù)語法規(guī)則語

6、法規(guī)則主要理論基礎主要理論基礎上下文無關文法上下文無關文法單詞符號單詞符號語法單位（語法范疇）語法單位（語法范疇）在詞法分析基礎上，將單詞符號串轉化為語在詞法分析基礎上，將單詞符號串轉化為語法單位（語法范疇）（短語、子句、句子、法單位（語法范疇）（短語、子句、句子、程序段、程序），并確定整個輸入串是否構程序段、程序），并確定整個輸入串是否構成語法上正確的程序。成語法上正確的程序。3.3.語法分析語法分析示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +變量、常數(shù)及其運算結果

7、均是表達式變量、常數(shù)及其運算結果均是表達式表達式表達式表達式表達式表達式表達式表達式表達式表達式表達式表達式表達式賦值句的形式為賦值句的形式為“變量：表達式變量：表達式”賦值句賦值句賦值句賦值句多個賦值句可構成語句塊多個賦值句可構成語句塊語句塊語句塊表達式可作為循環(huán)的初值和終值表達式可作為循環(huán)的初值和終值初值初值終值終值簡單數(shù)值變量可作為循環(huán)的控制變量簡單數(shù)值變量可作為循環(huán)的控制變量控制變量控制變量控制變量控制變量此時可以看出上述結果符合循環(huán)語句此時可以看出上述結果符合循環(huán)語句的語法定義，故語法分析成功完成的語法定義，故語法分析成功完成4.4.中間代碼生成中間代碼生成任務任務所做轉換所做轉換依

8、據(jù)依據(jù)語義規(guī)則語義規(guī)則主要理論基礎主要理論基礎屬性文法屬性文法語法范疇語法范疇中間代碼中間代碼對語法分析所識別出的各類語法范疇，分析對語法分析所識別出的各類語法范疇，分析其含義，并進行初步翻譯（產生中間代碼）。其含義，并進行初步翻譯（產生中間代碼）。4.4.中間代碼生成中間代碼生成示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +(1) ( :=, 1, , K )(1) ( :=, 1, , K )(2) ( j,100, K, )(2) ( j,100, K, )(3)

9、 ( (3) ( * *, 10, K, T, 10, K, T1 1 ) )(8) ( j, , , (2)(8) ( j, , , (2)(7) ( +, K, 1, K )(7) ( +, K, 1, K )(4) ( +, I, T(4) ( +, I, T1 1, M ), M )(9) ( )(9) ( )(9)(9)(5) ( (5) ( * *, 10, K, T, 10, K, T2 2 ) )(6) ( +, J, T(6) ( +, J, T2 2, N ), N )T T1 1T T2 2(1) K := 1(1) K := 1(2) if 100K goto (9)(

10、2) if 100K goto (9)(3) T(3) T1 1 := 10 := 10 * * K K(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(4) M := I + T(4) M := I + T1 1(9)(9)(5) T(5) T2 2 := 10 := 10 * * K K(6) N := J + T(6) N := J + T2 2循環(huán)語句循環(huán)語句出口語句出口語句循環(huán)塊循環(huán)塊STEP 1STEP 1生成四元式生成四元式將四元式重寫為另一種形式的中間代碼將四元式重寫為另一種形式的中間代碼(1) ( :=, 1, , K

11、)(1) ( :=, 1, , K )(2) ( j,100, K, (9)(2) ( j,100, K, (9)(3) ( (3) ( * *, 10, K, T, 10, K, T1 1 ) )(8) ( j, , , (2)(8) ( j, , , (2)(7) ( +, K, 1, K )(7) ( +, K, 1, K )(4) ( +, I, T(4) ( +, I, T1 1, M ), M )(9) ( )(9) ( )(5) ( (5) ( * *, 10, K, T, 10, K, T2 2 ) )(6) ( +, J, T(6) ( +, J, T2 2, N ), N

12、)循環(huán)語句和循環(huán)語句和出口語句出口語句 彼此相連地彼此相連地被定義被定義包括循環(huán)語包括循環(huán)語句開始到有句開始到有同一控制變同一控制變量的第一個量的第一個出口語句的出口語句的那些語句的那些語句的自然序列稱自然序列稱為一循環(huán)塊為一循環(huán)塊塊嵌套不可交叉，塊嵌套不可交叉，嵌套塊控制變量嵌套塊控制變量不可同名不可同名不正確不正確正確嵌套正確嵌套缺省的缺省的 STEP STEP = = STEP 1STEP 15.5.代碼優(yōu)化代碼優(yōu)化任務任務所做轉換所做轉換依據(jù)依據(jù)程序等價變換規(guī)則程序等價變換規(guī)則主要理論基礎主要理論基礎數(shù)據(jù)流方程數(shù)據(jù)流方程中間代碼中間代碼中間代碼（優(yōu)化后）中間代碼（優(yōu)化后）對于代碼（主要

13、是中間代碼）進行加工變換，對于代碼（主要是中間代碼）進行加工變換，以期能夠產生更為高效（省時間和空間）的以期能夠產生更為高效（省時間和空間）的目標代碼。目標代碼。5.5.代碼優(yōu)化代碼優(yōu)化示例示例(1) K := 1(1) K := 1(2) if 100K goto (9)(2) if 100K goto (9)(3) T(3) T1 1 := 10 := 10 * * K K(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(4) M := I + T(4) M := I + T1 1(9)(9)(5) T(5) T2 2 := 10 :

14、= 10 * * K K(6) N := J + T(6) N := J + T2 2(3) K := 1(3) K := 1(4) if 100K goto (9)(4) if 100K goto (9)(8) goto (4)(8) goto (4)(7) K := K + 1(7) K := K + 1(9)(9)(3) T(3) T1 1 := 10 := 10 * * K K(4) M := I + T(4) M := I + T1 1(1) M := I(1) M := I(5) M := M + 10 (5) M := M + 10 (5) T(5) T2 2 := 10 :=

15、10 * * K K(6) N := J + T(6) N := J + T2 2(2) N := J(2) N := J(6) N := N + 10(6) N := N + 10(1) K := 1(1) K := 1(2) if 100K goto (9)(2) if 100K goto (9)(8) goto (2)(8) goto (2)(7) K := K + 1(7) K := K + 1(9)(9)6.6.目標代碼生成目標代碼生成任務任務所做轉換所做轉換依據(jù)依據(jù)硬件體系結構、指令系統(tǒng)硬件體系結構、指令系統(tǒng)中間代碼中間代碼目標代碼目標代碼將中間代碼變換成特定機器上的低級語言代碼將

16、中間代碼變換成特定機器上的低級語言代碼目標代碼形式目標代碼形式絕對指令、可重定位指令、匯編指令絕對指令、可重定位指令、匯編指令6.6.目標代碼生成目標代碼生成LD RLD R1 1, I, IL L2 2: ST R: ST R1 1, M, MLD RLD R2 2, J, JST RST R2 2, N, NLD RLD R0 0, 1, 1L L1 1: CMP 100, R: CMP 100, R0 0J LJ L2 2ADD RADD R1 1, 10, 10ADD RADD R2 2, 10, 10ADD RADD R0 0, 1, 1J LJ L1 1示例示例(8) goto (

17、4)(8) goto (4)(7) K := K + 1(7) K := K + 1(1) M := I(1) M := I(9)(9)(6) N := N + 10(6) N := N + 10(3) K := 1(3) K := 1(2) N := J(2) N := J(5) M := M + 10 (5) M := M + 10 (4) if 100K goto (9)(4) if 100K goto (9)(9)(9)(8) goto (4)(8) goto (4)(7) K := K + 1(7) K := K + 1(1) M := I(1) M := I(6) N := N +

18、 10(6) N := N + 10(3) K := 1(3) K := 1(2) N := J(2) N := J(4) if 100K goto (9)(4) if 100K goto (9)(5) M := M + 10 (5) M := M + 10 1.1.編譯程序總框編譯程序總框表表格格管管理理詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成源程序源程序單詞符號單詞符號中間代碼中間代碼語法單位語法單位目標代碼目標代碼中間代碼中間代碼出出錯錯處處理理2.2.表格與表格管理表格與表格管理編譯各階段均須維持表格維持表格并進行表格管理表格管理

19、建表的技術支持技術支持是數(shù)據(jù)結構數(shù)據(jù)結構表格的分類、結構、處理方法分類、結構、處理方法決定于語言語言及機器機器，還有優(yōu)化措施優(yōu)化措施2.2.表格與表格管理表格與表格管理編譯程序涉及的表格有：符號名表符號名表常量名、變量名、數(shù)組名、過程名、 性質、 引用、定義常數(shù)表常數(shù)表標號表標號表入口名表入口名表過程引用表過程引用表各種類型常數(shù)的值標號的定義和引用情況過程的入口名和入口位置外部過程的名字、引用位置循環(huán)表循環(huán)表等價名表等價名表公用鏈表公用鏈表格式表格式表中間代碼表中間代碼表3.3.出錯處理出錯處理一個好的編譯程序應該：全全 最大限度發(fā)現(xiàn)錯誤準準 準確指出錯誤的性質和發(fā)生地點局部化局部化 將錯誤的

20、影響限制在盡可能小的范圍內若能自動校正錯誤自動校正錯誤則更好，但其代價非常高代價非常高3.3.出錯處理出錯處理源程序中的錯誤通常分為 ：語法錯誤語法錯誤 不符合語法（或詞法）規(guī)則的錯誤語義錯誤語義錯誤 不符合語義規(guī)則的錯誤單詞拼寫錯誤、括號不匹配 .說明錯誤、作用域錯誤、類型不匹配 .4.4.遍遍 遍遍 是對源程序或源程序的中間結果從頭到尾從頭到尾掃描一次掃描一次，并作有關的加工處理加工處理，生成新的中生成新的中間結果或目標程序間結果或目標程序。詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成一遍一遍語法分析器語法分析器處于核心地位處于核心地位一

21、遍一遍 局部優(yōu)化局部優(yōu)化一遍一遍一遍一遍 全局優(yōu)化全局優(yōu)化5.5.編譯前端與后端編譯前端與后端 詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成編譯前端編譯前端主要由與源語言有關與源語言有關但與目標機無關與目標機無關的那些部分組成編譯后端編譯后端包括編譯程序中與目標機有關與目標機有關的那些部分以往以往 編譯程序的構造大多采用機器語言機器語言或匯編語言匯編語言現(xiàn)在現(xiàn)在 編譯程序的構造越來越多采用高級語言高級語言1.1.編譯程序的構造工具編譯程序的構造工具有時為了充分發(fā)揮效率充分發(fā)揮效率或滿足不同需求滿足不同需求，仍然采用 機器語言機器語言或匯編語言

22、匯編語言構造編譯程序（或其核心部分）2. T2. T型圖型圖S SI IT TS S表示源語言表示源語言T T表示目標語言表示目標語言I I表示編譯程序的實現(xiàn)語言表示編譯程序的實現(xiàn)語言3. 3. 用高級語言用高級語言L L1 1構造編譯程序構造編譯程序L L1 1A AA AL L2 2L L1 1A AL L2 2A AA A已有用A機器代碼實現(xiàn)的高級語言L1的編譯程序可用高級語言L1編寫另一個高級語言L2的編譯程序將寫好的語言L2的編譯程序用L1的編譯程序編譯后就可得到用A機器代碼實現(xiàn)的L2編譯程序4. 4. 編譯程序的移植編譯程序的移植L LA AA A(1)(1)L LL LB B(2)(2)L LA AB B(3)(3)已有A機器上的高級 語言L編譯程序（1）L LB BB B(4)(4)用L編寫能在B機器上運行的L的編譯程序（2）將(2)用(1)編譯，得到A機器上運行的產生B代碼的L的編譯程序（3）L LL LB B(2)(2)再將(2)用(3)編譯，即可得到B機器上運行的產生B代碼的L的編譯程序（4）至此，將A機器上的L的編譯程序(1)移植為B機器上的L的編譯程序（4）5. 5. 自編譯方式自編譯方式先對語言的核心部分構造一個小小的編譯程序（可用低級語言實現(xiàn)）（可用