編譯原理：第一章 編譯引論

1、 課 程 內(nèi) 容第 1 章 編 譯 引 論第 2 章 形式語言與自動機基礎(chǔ)第 3 章 詞法分析 (Lexical Analysis)第 4 章 語法分析(Syntax Analysis) 自上而下分析法第 5 章 語法分析(Syntax Analysis) 自下而上分析法第 6 章 語義分析與中間代碼生成第 7 章 運 行 環(huán) 境第 8 章 代碼優(yōu)化（optimization）1.1 程序設(shè)計語言與編譯程序1.2 編譯程序的表示與分類1.3 編譯程序的結(jié)構(gòu)與組織1.4 語言開發(fā)環(huán)境中的伙伴程序1.5 編譯程序結(jié)構(gòu)的實例模型1.6 編譯程序的構(gòu)造與實現(xiàn) 第一章 編譯引論 Compiler ? 第

2、一章 編譯引論 1.1 程序設(shè)計語言與編譯程序 Compiler ? 借助編譯程序可以執(zhí)行高級語言編寫的程序； 編譯程序是語言處理系統(tǒng) ； 人、機交互的工具; 定義1.1 : 將某一種程序設(shè)計語言寫的程序翻譯成等價的另一種語言的程序的程序, 稱之為編譯程序(compiler) 。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序源語言： (source language) 編寫源程序的語言是源語言。源程序： (source program)被翻譯(編譯）的程序稱為源程序。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序源語言一般是匯編語言或高級程序設(shè)計語言。 Compiler ? 編譯程序是

3、語言處理系統(tǒng) ； 編譯程序是將高級語言翻譯成機器語言的程序； 人、機交互的工具; 定義1.1 : 將某一種程序設(shè)計語言寫的程序翻譯成等價的另一種語言的程序的程序, 稱之為編譯程序(compiler) 。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序源程序目標程序：(target program) 源程序經(jīng)過翻譯（編譯）后生成的程序稱之為目標程序。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序目標語言：(target language) 目標程序的描述語言稱為目標語言。 Compiler ? 編譯程序是語言處理系統(tǒng) ； 編譯程序是將高級語言翻譯成機器語言的程序； 人、機交互的工具; 定義

4、1.1 : 將某一種程序設(shè)計語言寫的程序翻譯成等價的另一種語言的程序的程序, 稱之為編譯程序(compiler) 。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序源程序目標程序 Compiler ? 編譯程序是語言處理系統(tǒng) ； 編譯程序是將高級語言翻譯成機器語言的程序； 人、機交互的工具; 定義1.1 : 將某一種程序設(shè)計語言寫的程序翻譯成等價的另一種語言的程序的程序, 稱之為編譯程序(compiler) 。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序 將源程序翻譯成等價的目標程序的程序, 稱之為編譯程序(compiler) 。 宿主語言： 編譯程序的實現(xiàn)語言。 宿主機（目標機）：

5、編譯程序的運行環(huán)境(運行編譯程序的計算機）。 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序( 3 ) 用戶直接關(guān)心的工具。( 2 ) 軟件學科的重要分支；( 1 ) 人、機交互的基本界面；Compiler源程序目標程序等價變換作用地位 第一章 編譯引論 1.1 程序設(shè)計語言與編譯程序被編譯的程序為A語言程序，編譯的最終結(jié)果為B語言代碼，編寫編譯程序的語言為C語言。那么， 語言是源語言， 語言是宿主語言， 語言是目標語言。 Ch2 形式語言自動機理論基礎(chǔ)ACB1.1 程序設(shè)計語言與編譯程序1.2 編譯程序的表示與分類1.3 編譯程序的結(jié)構(gòu)與組織1.4 語言開發(fā)環(huán)境中的伙伴程序1.5 編譯程序

6、結(jié)構(gòu)的實例模型1.6 編譯程序的構(gòu)造與實現(xiàn) 第一章 編譯引論一. 編譯程序的分類與執(zhí)行模式編譯程序（實現(xiàn)）解釋程序匯編程序編譯程序解釋程序： 接受某語言的源程序?qū)⑵渲苯臃g成目標 代碼且執(zhí)行。編譯程序： 接受某語言的源程序?qū)⑵渲苯臃g成等價 的目標代碼，然后執(zhí)行且允許重復(fù)執(zhí)行。匯編程序： 接受匯編源程序?qū)⑵浞g成等價的機器語 言的目標程序，然后執(zhí)行且允許重復(fù)執(zhí)行。 第一章 編譯引論 1.2 編譯程序的表示與分類 編譯執(zhí)行和解釋執(zhí)行的區(qū)別： 編譯執(zhí)行是由編譯程序生成一個與源程序等價的目標程序，它可以完全取代源程序，該目標程序可以運行任意次。 解釋執(zhí)行不生成目標程序，僅是對源程序逐句解釋逐句執(zhí)行。

7、 編譯執(zhí)行類似于自然語言的筆譯；解釋執(zhí)行類似自然語言的口譯。 第一章 編譯引論 1.2 編譯程序的表示與分類解釋執(zhí)行：編譯執(zhí)行：結(jié)果Compiler源程序目標程序computer運行程序computer數(shù)據(jù)Step 1Step 2 第一章 編譯引論 1.2 編譯程序的表示與分類解釋程序源程序computer結(jié)果數(shù)據(jù)二. 編譯程序的表示 1） 函數(shù)表示 ： T = C（S）T: 目標語言 C: 宿主語言 S: 源語言2） T型圖表示源語言目標語言宿主語言C源目宿3）符號表示 第一章 編譯引論 1.2 編譯程序的表示與分類CCS TCST(體現(xiàn)編譯程序的三個要素) 第一章 編譯引論 1.2 編譯程

8、序的表示與分類 T型圖的組合ABCCXLLABABCCXLLABCCLLAABBX例1.1 : 用T型圖描述將A機器上已經(jīng)存在的L語 言的編譯程序移植到B機器上的過程。 第一章 編譯引論 1.2 編譯程序的表示與分類分析:已知的編譯器:ALA要得到的編譯器:BLB 第一章 編譯引論 1.2 編譯程序的表示與分類 T型圖的組合ABCCXLLABCCLLAABBALABLB已知的編譯器:得到的編譯器:例1.1 : 用T型圖描述將A機器上已經(jīng)存在的L語 言的編譯程序移植到B機器上的過程。LLBStep1:Step2:L B LL A AL B AL B LL B AL B BStep3: 第一章 編

9、譯引論 1.2 編譯程序的表示與分類若目標機指令系統(tǒng)與宿主機的指令系統(tǒng)不同（即運行在宿主機A上的某編譯程序為另一臺機器B生成目標代碼），這樣的編譯器稱為交叉編譯器。 例1.1 : 用T型圖描述將A機器上已經(jīng)存在的L語 言的編譯程序移植到B機器上的過程。 第一章 編譯引論 1.2 編譯程序的表示與分類LLBALALLBALBBLB例1.1 : 用T型圖描述將A機器上已經(jīng)存在的L語 言的編譯程序移植到B機器上的過程。LLBStep1:Step2:L B LL B LL B B 第一章 編譯引論 1.2 編譯程序的表示與分類1.1 程序設(shè)計語言與編譯程序1.2 編譯程序的表示與分類1.3 編譯程序的

10、結(jié)構(gòu)與組織1.4 語言開發(fā)環(huán)境中的伙伴程序1.5 編譯程序結(jié)構(gòu)的實例模型1.6 編譯程序的構(gòu)造與實現(xiàn) 第一章 編譯引論 表 格 管 理 源 語 語 中 代 代 程 法 義 間 生 碼 碼 目標 分處 代 成 優(yōu) 生 序詞法分析析理 碼化 成 程序 出 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分) 1. 詞法分析 (lexical analysis)依次掃描讀入的源程序中的每個字符,識別出源程序中有獨立意義的源語言單詞(屬性字或記號),并用某種特定的數(shù)據(jù)結(jié)構(gòu)進行表示。Scanner源程序L

11、屬性字流L1 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織詞法分析階段是對輸入的符號串形式的源程序進行最初的加工處理。詞法分析實際上是一種線性分析。屬性字的數(shù)據(jù)結(jié)構(gòu):類型標識和內(nèi)碼兩個數(shù)據(jù)項。例1.2: 有如下C代碼行 ： aindex = 12 * 3 ； 詞法分析： ( 1 ) a 標識符 ( 2 ) 左方括號 ( 3 ) index 標識符 ( 4 ) 右方括號 ( 5 ) = 賦值 ( 6 ) 12 整常數(shù) ( 7 ) * 乘號 ( 8 ) 3 整常數(shù) ( 9 ) ; 分號 識別出9個單詞。屬性字流源程序 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 表 格 管 理 源詞 語 中

12、代 代 程 法 義 間 生 碼 碼 目標 分 處 代 成 優(yōu) 生 序析語法分析理 碼化 成 程序 出 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分)2. 語法分析 (Syntax analysis) 語法分析的任務(wù)是依據(jù)語言文本所規(guī)定的語法規(guī)則對詞法分析的結(jié)果(屬性字流)進行語法檢查, 識別出單詞序列所對應(yīng)的語法范疇。通常將語法分析的結(jié)果表示為語法分析樹或抽象語法樹，它是一種層次結(jié)構(gòu)的形式。例1.2中的C語言的賦值表達式語句經(jīng)過語法分析，確認合乎C語言的語法規(guī)則且語法范疇為表達式語句, 產(chǎn)

13、生的語法分析樹形式的語法分析結(jié)果如下圖所示。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織C語句 aindex = 12 * 3 ；的語法分析樹語法范疇 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織常數(shù) 12 常數(shù) 3 標識符a 表達式 * 表達式表達式賦值表達式 數(shù)組元素引用 表達式標識符index 表 格 管 理 源詞 語 代 代 程 法 法 碼 碼 目標 分 分 優(yōu) 生 序析析 語中義間生處代成理碼化 成 程序 出 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分)3. 語義分析 (

14、semantic analysis)與中間代碼生成 語義分析階段的任務(wù)是依據(jù)語言文本限定的語義規(guī)則對語法分析所識別的語法范疇進行語義檢查 和處理, 直至最后翻譯成與其等價的某種中間代碼或 目標代碼。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織語義分析是整個編譯程序完成的最實質(zhì)性的翻譯 任務(wù)。例1.3: 設(shè)有賦值語句 x=(a+b)*c * T1 c T2 = T2 x + a b T1 產(chǎn)生的四元式形式的中間代碼： 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 表 格 管 理 源詞 語 語 中 代 程 法 法 義 間 生 碼 目標 分 分處 代 成 生 序析析理 碼代碼優(yōu)化 成 程序 出

15、 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分)4. 代碼優(yōu)化 (optimization) 代碼優(yōu)化是在不改變源程序語義的基礎(chǔ)上對其進行加工變換, 以期獲得高效的目標代碼。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織代碼優(yōu)化可以在中間代碼或目標代碼級上進行。運行時間的縮短和存貯空間的節(jié)省。例1.4: 設(shè)有語句 for (i=1; i=200; i+) y=y*i+y; x=x1/cos(x2) x=x1/cos(x2)for (i=1; i=200; i+) y=y*i+y; 優(yōu)化后

16、 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 表 格 管 理 源詞 語 語 中 代 程 法 法 義 間 生 碼 目標 分 分處 代 成 優(yōu) 序析析理 碼化 代碼生成 程序 出 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分)5. 目標代碼生成 (code generator) 根據(jù)中間代碼及編譯過程中產(chǎn)生的各種表格的有關(guān)信息,最終生成所期望的目標代碼程序。一般為特定機器的機器語言代碼或匯編語言代碼, 生成中需要充分考慮計算機硬件和軟件所提供的資源, 以生成較高質(zhì)量的目標程序。 第一章 編

17、譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 對例1.2 “aindex = 12 * 3 ；”的語句生成代碼。要考慮怎樣存儲整型數(shù)來為數(shù)組元素的引用生成目標代碼，以假設(shè)的匯編語言描述如下：MOV R0, index ; 索引值賦給寄存器R0MUL R0, 2 ; 存儲按字節(jié)編址，整型數(shù) ; 占2個字節(jié)MOV R1, &a ; &a表示數(shù)組a的基地址ADD R1, R0 ; 計算aindex的地址MOV *R1, 36 ; aindex = 36 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 表 格 管 理 源詞 語 語 中 代 代 程 法 法 義 間 生 碼 碼 目標 分 分處 代 成 優(yōu) 生 序

18、析析理 碼化 成 程序 出 錯 處 理 front end back end ( 分析 )（綜合） 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分) 編譯階段與自然語言的翻譯對比 編 譯 程 序 自 然 語 言 翻 譯詞法分析查字典、識別單詞語法分析分析識別句子產(chǎn)生中間代碼翻譯初稿代碼優(yōu)化對初稿潤色修飾目標代碼生成譯文定稿 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 源詞 語 語 中 代 代 程 法 法 義 間 生 碼 碼 目標 分 分處 代 成 優(yōu) 生 序析析理 碼化 成 程序 表格管理出錯處理 front end back end ( 分析 )（綜合）

19、第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分) 表格管理 編譯程序的公共輔助部分。對源程序中的各種量進行管理，登記在相應(yīng)的表格。編譯程序處理時通過查表得到所需的信息。 出錯處理 編譯程序的公共輔助部分。對源程序中的各種錯誤檢查、定位、定性、報告，并盡可能將錯誤限制在盡可能小的范圍內(nèi)，保障編譯繼續(xù)。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 源詞 語 語 中 代 代 程 法 法 義 間 生 碼 碼 目標 分 分處 代 成 優(yōu) 生 序析析理 碼化 成 程序 表格管理出錯處理 front end back end( 分析 )（綜合） 第一章 編譯引論 1.3

20、編譯程序的結(jié)構(gòu)與組織 編譯程序的邏輯結(jié)構(gòu) (經(jīng)典劃分) 定義1.2 : ( 遍 Pass ) 對源程序或源程序的中間形式從頭到尾掃描一遍，并做有關(guān)的分析加工，生成新的與源程序等價的中間形式或生成目標程序。 遍數(shù)多的優(yōu)點： 1）編譯程序邏輯結(jié)構(gòu)清晰； 2）減少對主存容量的要求； 3）優(yōu)化準備充分等。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織 遍設(shè)置的考慮因素 1） 宿主機存儲容量； 2） 編譯程序功能的強弱； 3） 源語言的繁簡及約束； 4） 優(yōu)化因素； 5） 設(shè)計、實現(xiàn)的環(huán)境、工具及人員因素等。 第一章 編譯引論 1.3 編譯程序的結(jié)構(gòu)與組織1.1 程序設(shè)計語言與編譯程序1.2 編譯程序

21、的表示與分類1.3 編譯程序的結(jié)構(gòu)與組織1.4 語言開發(fā)環(huán)境中的伙伴程序1.5 編譯程序結(jié)構(gòu)的實例模型1.6 編譯程序的構(gòu)造與實現(xiàn) 第一章 編譯引論 一遍掃描的編譯程序結(jié)構(gòu)模型(Pascal編譯器） 第一章 編譯引論 1.4 編譯程序結(jié)構(gòu)的實例模型 語法分析程序源程序語義處理目標程序詞法分析代碼生成 AHPL模擬器（兩遍掃描的編譯程序結(jié)構(gòu)模型） AHPL模擬器 第一遍 第二遍 AHPL 詞法分析語法 操作表 源程序 分析語義處理 （目標程序）模擬結(jié)果代碼生成 第一章 編譯引論 1.4 編譯程序結(jié)構(gòu)的實例模型C源程序詞法分析語法分析語義處理（中間代碼生成）中間代碼代 碼 生 成代 碼 優(yōu) 化目標代碼 （匯編） 匯編代碼 PDP 11 C編譯器結(jié)構(gòu)模型（三遍掃描的編譯程序結(jié)構(gòu)模型） 第一章 編譯引論 1.4 編譯程序結(jié)構(gòu)的實例模型Gcc compiler structureC+source fileC source fileF source fileC+ ParserC Parser語法樹RTL 生成器優(yōu)化器匯編器Fortran Parser寄存器轉(zhuǎn)換語言RTL 表示Assembly