編譯原理-1引論

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

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

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

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

5、界符、個個單詞（定義符、標(biāo)識符、運算符、界符、常數(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+ +* * *+ +定義符定義符標(biāo)識符標(biāo)識符分界符分界符運算符運算符 常數(shù)常數(shù)3.3.語法分析語法分析任務(wù)任務(wù)所做轉(zhuǎn)換所做轉(zhuǎn)換依據(jù)依據(jù)語法規(guī)則語

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

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

8、據(jù)依據(jù)語義規(guī)則語義規(guī)則主要理論基礎(chǔ)主要理論基礎(chǔ)屬性文法屬性文法語法范疇語法范疇中間代碼中間代碼對語法分析所識別出的各類語法范疇，分析對語法分析所識別出的各類語法范疇，分析其含義，并進行初步翻譯（產(chǎn)生中間代碼）。其含義，并進行初步翻譯（產(chǎn)生中間代碼）。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)化任務(wù)任務(wù)所做轉(zhuǎn)換所做轉(zhuǎn)換依據(jù)依據(jù)程序等價變換規(guī)則程序等價變換規(guī)則主要理論基礎(chǔ)主要理論基礎(chǔ)數(shù)據(jù)流方程數(shù)據(jù)流方程中間代碼中間代碼中間代碼（優(yōu)化后）中間代碼（優(yōu)化后）對于代碼（主要

13、是中間代碼）進行加工變換，對于代碼（主要是中間代碼）進行加工變換，以期能夠產(chǎn)生更為高效（省時間和空間）的以期能夠產(chǎn)生更為高效（省時間和空間）的目標(biāo)代碼。目標(biāo)代碼。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.目標(biāo)代碼生成目標(biāo)代碼生成任務(wù)任務(wù)所做轉(zhuǎn)換所做轉(zhuǎn)換依據(jù)依據(jù)硬件體系結(jié)構(gòu)、指令系統(tǒng)硬件體系結(jié)構(gòu)、指令系統(tǒng)中間代碼中間代碼目標(biāo)代碼目標(biāo)代碼將中間代碼變換成特定機器上的低級語言代碼將

16、中間代碼變換成特定機器上的低級語言代碼目標(biāo)代碼形式目標(biāo)代碼形式絕對指令、可重定位指令、匯編指令絕對指令、可重定位指令、匯編指令6.6.目標(biāo)代碼生成目標(biāo)代碼生成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)化目標(biāo)代碼生成目標(biāo)代碼生成源程序源程序單詞符號單詞符號中間代碼中間代碼語法單位語法單位目標(biāo)代碼目標(biāo)代碼中間代碼中間代碼出出錯錯處處理理2.2.表格與表格管理表格與表格管理編譯各階段均須維持表格維持表格并進行表格管理表格管理

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

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

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

22、匯編語言構(gòu)造編譯程序（或其核心部分）2. T2. T型圖型圖S SI IT TS S表示源語言表示源語言T T表示目標(biāo)語言表示目標(biāo)語言I I表示編譯程序的實現(xiàn)語言表示編譯程序的實現(xiàn)語言3. 3. 用高級語言用高級語言L L1 1構(gòu)造編譯程序構(gòu)造編譯程序L L1 1A AA AL L2 2L L1 1A AL L2 2A AA A已有用A機器代碼實現(xiàn)的高級語言L1的編譯程序可用高級語言L1編寫另一個高級語言L2的編譯程序?qū)懞玫恼Z言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機器上運行的產(chǎn)生B代碼的L的編譯程序（3）L LL LB B(2)(2)再將(2)用(3)編譯，即可得到B機器上運行的產(chǎn)生B代碼的L的編譯程序（4）至此，將A機器上的L的編譯程序(1)移植為B機器上的L的編譯程序（4）5. 5. 自編譯方式自編譯方式先對語言的核心部分構(gòu)造一個小小的編譯程序（可用低級語言實現(xiàn)）（可用