編譯原理Chap1

1、2022-4-22第 1 頁有了編譯技術(shù)，計算機語言由單一的機器有了編譯技術(shù)，計算機語言由單一的機器語言發(fā)展到現(xiàn)今的數(shù)千種高級語言。語言發(fā)展到現(xiàn)今的數(shù)千種高級語言。 計算機科學(xué)中最成熟的一個分支，集中體現(xiàn)計算機科學(xué)中最成熟的一個分支，集中體現(xiàn)了計算機發(fā)展的成果與精華。了計算機發(fā)展的成果與精華。 計算機軟件學(xué)科理論與實踐相結(jié)合的典范。計算機軟件學(xué)科理論與實踐相結(jié)合的典范。 編譯程序使得多數(shù)計算機用戶不必考慮與編譯程序使得多數(shù)計算機用戶不必考慮與機器有關(guān)的繁瑣細節(jié)，使程序員獨立于機器。機器有關(guān)的繁瑣細節(jié)，使程序員獨立于機器。2022-4-22第 2 頁必修主干課程必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構(gòu)

2、成，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計者與計算機之間的基本界面。程序設(shè)計者與計算機之間的基本界面。為什么要學(xué)習編譯原理為什么要學(xué)習編譯原理2022-4-22第 3 頁課程主要內(nèi)容課程主要內(nèi)容編譯原理編譯原理 = 形式語言理論形式語言理論 + 編譯技術(shù)編譯技術(shù)2022-4-22第 4 頁學(xué)習本課程的基本要求學(xué)習本課程的基本要求2022-4-22第 5 頁編譯原理課程應(yīng)用領(lǐng)域編譯原理課程應(yīng)用領(lǐng)域有窮自動機有窮自動機模式識別模式識別情報檢索情報檢索文本編輯程序文本編輯程序上下文無關(guān)文法上下文無關(guān)文法語法制導(dǎo)翻譯語法制導(dǎo)翻譯建立多種文本處理程序建立多種文本處理程序代碼優(yōu)化技術(shù)代碼優(yōu)化技術(shù)由非結(jié)構(gòu)化到結(jié)構(gòu)化

3、的程序轉(zhuǎn)換由非結(jié)構(gòu)化到結(jié)構(gòu)化的程序轉(zhuǎn)換程序校驗程序校驗2022-4-22第 6 頁2022-4-22第 7 頁用用C語言寫的完整的語言寫的完整的用每一章中學(xué)到的不同技術(shù)分塊建立起來的。用每一章中學(xué)到的不同技術(shù)分塊建立起來的。通過通過TINY 編譯器的建立，從整體上掌握編譯編譯器的建立，從整體上掌握編譯器構(gòu)造的方法。器構(gòu)造的方法。2022-4-22第 8 頁編譯原理課程設(shè)計編譯原理課程設(shè)計2022-4-22第 9 頁課程安排課程安排講課：講課：38學(xué)時學(xué)時實驗：實驗：16學(xué)時學(xué)時(詞法分析、語法分析、語義分析、符號表詞法分析、語法分析、語義分析、符號表) 答疑時間答疑時間周四周四 12:00-1

4、3:00 網(wǎng)絡(luò)中心網(wǎng)絡(luò)中心307聯(lián)系方式聯(lián)系方式史一民史一民 信息科學(xué)與技術(shù)學(xué)院信息科學(xué)與技術(shù)學(xué)院 計算機系計算機系E-mail：課時及答疑課時及答疑2022-4-22第 10 頁第第8-15周周 周一周一3-4節(jié)節(jié)計科樓計科樓 201室室上機實驗安排上機實驗安排2022-4-22第 11 頁課程考核標準課程考核標準2022-4-22第 12 頁 掌握編譯程序中所涉及的有關(guān)名詞術(shù)語掌握編譯程序中所涉及的有關(guān)名詞術(shù)語2.2.理解編譯程序總體框架，明確編譯程序工理解編譯程序總體框架，明確編譯程序工作的基本過程及各階段的基本任務(wù)作的基本過程及各階段的基本任務(wù)教學(xué)目標教學(xué)目標第一章第一章 編譯程序概述

5、編譯程序概述2022-4-22第 13 頁第一章第一章 編譯程序概述編譯程序概述2022-4-22第 14 頁1.1 什么是編譯程序什么是編譯程序程序設(shè)計語言程序設(shè)計語言2022-4-22第 15 頁匯編程序匯編程序把匯編語言書寫的程序翻譯成機器語言程序。把匯編語言書寫的程序翻譯成機器語言程序。編譯程序編譯程序把高級語言書寫的程序翻譯成匯編或目標程序把高級語言書寫的程序翻譯成匯編或目標程序。翻譯程序翻譯程序翻譯程序翻譯程序 將源程序轉(zhuǎn)換為目標程序的程序。將源程序轉(zhuǎn)換為目標程序的程序。匯編程序、編譯程序以及各種變換程序的總稱匯編程序、編譯程序以及各種變換程序的總稱。2022-4-22第 16 頁

6、一種相當復(fù)雜的程序，長度可從一種相當復(fù)雜的程序，長度可從10,00010,000行到行到1,000,0001,000,000行不等。編寫甚至讀懂都非易事。行不等。編寫甚至讀懂都非易事。大多數(shù)的計算機科學(xué)家和專業(yè)人員也從來沒有編寫過大多數(shù)的計算機科學(xué)家和專業(yè)人員也從來沒有編寫過一個完整的編譯器。一個完整的編譯器。任何一個與計算機打交道的專業(yè)人員都應(yīng)掌握編譯器任何一個與計算機打交道的專業(yè)人員都應(yīng)掌握編譯器的基本結(jié)構(gòu)和操作。的基本結(jié)構(gòu)和操作。 高級語言高級語言書寫的程序書寫的程序 編譯程序編譯程序低級語言程序低級語言程序編譯程序編譯程序(compiler)2022-4-22第 17 頁源程序的編譯和

7、運行源程序的編譯和運行源程序源程序目標程序目標程序編譯程序編譯程序或匯編程序或匯編程序輸出數(shù)據(jù)輸出數(shù)據(jù)目標程序目標程序+運行子程序運行子程序輸入數(shù)據(jù)輸入數(shù)據(jù)2022-4-22第 18 頁對源程序進行解釋執(zhí)行的程序。對源程序進行解釋執(zhí)行的程序。類似于口譯，不生成目標代碼類似于口譯，不生成目標代碼l與編譯系統(tǒng)比較的特點：與編譯系統(tǒng)比較的特點：l較簡單較簡單l可移植性好，易于查錯，但速度慢?？梢浦残院?，易于查錯，但速度慢。解釋程序解釋程序（Interpreter）2022-4-22第 19 頁編譯和解釋程序編譯和解釋程序2022-4-22第 20 頁解釋程序和編譯程序的區(qū)別解釋程序和編譯程序的區(qū)別是

8、否生成目標代碼是否生成目標代碼u很多語言如很多語言如BASIC,LISP和和PROLOG等等最初都是解等等最初都是解釋執(zhí)行的，后來也都有了編譯系統(tǒng)。釋執(zhí)行的，后來也都有了編譯系統(tǒng)。uJAVA環(huán)境同時需要解釋和編譯系統(tǒng)的支持。環(huán)境同時需要解釋和編譯系統(tǒng)的支持。 2022-4-22第 21 頁“編譯編譯- -解釋執(zhí)行解釋執(zhí)行”系統(tǒng)系統(tǒng)源程序源程序源程序的中間形式源程序的中間形式輸出數(shù)據(jù)輸出數(shù)據(jù)輸入數(shù)據(jù)輸入數(shù)據(jù)解釋程序解釋程序編譯程序編譯程序2022-4-22第 22 頁Java虛擬機（虛擬機（JVM)本地計算機系統(tǒng)本地計算機系統(tǒng)Java語語言言“編譯編譯- -解釋執(zhí)行解釋執(zhí)行”系系統(tǒng)統(tǒng)編譯程序編譯

9、程序.java Java源程序文件源程序文件.class 二進制字節(jié)碼文件二進制字節(jié)碼文件2022-4-22第 23 頁術(shù)術(shù) 語語宿主機：宿主機：運行編譯程序的計算機。運行編譯程序的計算機。目標機：目標機：運行編譯程序所產(chǎn)生的目標代碼的計算機。運行編譯程序所產(chǎn)生的目標代碼的計算機。源程序源程序 編譯程序編譯程序目標程序目標程序2022-4-22第 24 頁1.2 編譯過程和編譯程序的結(jié)構(gòu)編譯過程和編譯程序的結(jié)構(gòu)翻譯外文資料：翻譯外文資料：1、識別出句子中的單詞；、識別出句子中的單詞；2、分析句子的語法結(jié)構(gòu)；、分析句子的語法結(jié)構(gòu)；3、根據(jù)句子的含義進行初步翻譯；、根據(jù)句子的含義進行初步翻譯；4、

10、對譯文進行修飾；、對譯文進行修飾；5、寫出最后的譯文。、寫出最后的譯文。2022-4-22第 25 頁編譯過程編譯過程詞法分析詞法分析語法分析語法分析語義分析及語義分析及中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成2022-4-22第 26 頁編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu) 中中間間代代碼碼生生成成 詞詞法法分分析析 語語法法分分析析 語語義義分分析析 代代碼碼優(yōu)優(yōu)化化 目目標標代代碼碼生生成成 表格管理表格管理 錯誤處理錯誤處理 2022-4-22第 27 頁1 1、詞法分析、詞法分析字符序列字符序列單詞序列單詞序列具有獨立意義的最小單位具有獨立意義的最小單位202

11、2-4-22第 28 頁詞法分析程序的結(jié)果詞法分析程序的結(jié)果-二元組二元組y = x + r * 62022-4-22第 29 頁begin var sum, first, count:real; sum:= first + count * 102022-4-22第 30 頁2、語法分析、語法分析2022-4-22第 31 頁2. 2. 語法分析語法分析printf(“hello”)；2022-4-22第 32 頁2. 2. 語法分析語法分析賦值語句賦值語句標識符標識符標識符標識符整數(shù)整數(shù)標識符標識符表達式表達式=yx表達式表達式表達式表達式+r6表達式表達式表達式表達式*:=:=+ | *:

12、=() | | | y = x + r * 62022-4-22第 33 頁3. 語義分析語義分析(Semantic Analysis)2022-4-22第 34 頁語義分析任務(wù)舉例語義分析任務(wù)舉例賦值語句賦值語句確定表達式的類型確定表達式的類型自定義函數(shù)自定義函數(shù)分析賦值號左側(cè)是否為變量分析賦值號左側(cè)是否為變量檢查實參和形參個數(shù)、類型檢查實參和形參個數(shù)、類型2022-4-22第 35 頁4.4.中間代碼生成中間代碼生成 (Intermediate Code)逆波蘭（后綴表示）逆波蘭（后綴表示）id1id2id3 * +四元組四元組 ( (* *, ,id2,id3,T1) (+,id1 ,T

13、1 ,T2) 2022-4-22第 36 頁四元式四元式t1、t2、t3為為編譯程序引入的臨時工作單元編譯程序引入的臨時工作單元y = x + r * 62022-4-22第 37 頁5. 代碼優(yōu)化代碼優(yōu)化2022-4-22第 38 頁與機器無關(guān)的優(yōu)化與機器無關(guān)的優(yōu)化5. 代碼優(yōu)化代碼優(yōu)化2022-4-22第 39 頁y = x + r * 62022-4-22第 40 頁6. 目標代碼生成目標代碼生成movr, R1mul#6.0, R1movx, R2addR1, R2movR2, yy = x + r * 62022-4-22第 41 頁7、表格管理、表格管理2022-4-22第 42

14、頁8、錯誤處理、錯誤處理全全 最大限度發(fā)現(xiàn)錯誤最大限度發(fā)現(xiàn)錯誤準準 準確指出錯誤的性質(zhì)和發(fā)生地點準確指出錯誤的性質(zhì)和發(fā)生地點局部化局部化 將錯誤的影響限制在盡可能小的范圍內(nèi)將錯誤的影響限制在盡可能小的范圍內(nèi)若能若能自動校正錯誤自動校正錯誤則更好，但其代價非常高則更好，但其代價非常高2022-4-22第 43 頁1.3 編譯階段的組合編譯階段的組合 與源語言有關(guān)與源語言有關(guān)而與目標機無關(guān)的而與目標機無關(guān)的與目標機有關(guān)，與目標機有關(guān)，而與源語言無關(guān)的。而與源語言無關(guān)的。詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成2022-4-22第 44 頁1.

15、3 編譯階段的組合編譯階段的組合pass：對源程序?qū)υ闯绦蚧蛟闯绦虻闹虚g結(jié)果從頭或源程序的中間結(jié)果從頭到尾掃描一遍，到尾掃描一遍，并作加工處理，生成新的并作加工處理，生成新的中間結(jié)果或目標程序。中間結(jié)果或目標程序。詞法分析詞法分析語法分析語法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成一遍一遍一遍一遍 局部優(yōu)化局部優(yōu)化一遍一遍一遍一遍 全局優(yōu)化全局優(yōu)化核心核心2022-4-22第 45 頁一趟掃描程序與多趟掃描程序一趟掃描程序與多趟掃描程序l程序緊湊程序緊湊l速度快速度快2022-4-22第 46 頁1.4 編譯技術(shù)的發(fā)展和應(yīng)用編譯技術(shù)的發(fā)展和應(yīng)用 1 1 編譯程序的發(fā)

16、展編譯程序的發(fā)展2022-4-22第 47 頁 1 1 編譯程序的發(fā)展編譯程序的發(fā)展2022-4-22第 48 頁 1 1 編譯程序的發(fā)展編譯程序的發(fā)展2022-4-22第 49 頁2 2 推動編譯技術(shù)發(fā)展的因素推動編譯技術(shù)發(fā)展的因素 2022-4-22第 50 頁3 3 研究領(lǐng)域研究領(lǐng)域2022-4-22第 51 頁1.5 編譯程序?qū)崿F(xiàn)的途徑編譯程序?qū)崿F(xiàn)的途徑開發(fā)編譯程序的途徑開發(fā)編譯程序的途徑: 預(yù)處理法預(yù)處理法 移植法移植法() 工具法工具法 理論法理論法2022-4-22第 52 頁 形圖形圖源語言源語言實現(xiàn)語言實現(xiàn)語言目標語言目標語言2022-4-22第 53 頁1 交叉編譯交叉編譯

17、( (Cross Compiling) )（運行編譯程序的計算機（運行編譯程序的計算機）2022-4-22第 54 頁交叉編譯交叉編譯 舉例舉例語言語言語言語言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器(機的機的C編譯編譯P1)編譯編譯P0，得到在，得到在A機上可運行的機上可運行的P2(C 1. (人人)用用 語言編制語言編制B機的編譯程序機的編譯程序P0(C2022-4-22第 55 頁語言語言語言語言機器機器語言語言機器機器3. (機的機的P2)編譯編譯P0，得到在，得到在B機上可運行機上可運行的的P3(C 機器機器語言語言機器機器機器機器交叉編譯交叉編譯 舉例舉例202

18、2-4-22第 56 頁2 編譯程序的自展技術(shù)編譯程序的自展技術(shù)2022-4-22第 57 頁自展自展2022-4-22第 58 頁自展技術(shù)舉例自展技術(shù)舉例CC語言的編譯程序語言的編譯程序2. 用匯編程序用匯編程序(P1)處理該程序處理該程序,得到得到P2 (C子集的編譯子集的編譯程序，可直接運行程序，可直接運行)子集子集匯編語言匯編語言機器語言機器語言匯編語言匯編語言機器語言機器語言機器語言機器語言子集子集機器語言機器語言機器語言機器語言1. 用匯編語言實現(xiàn)一個用匯編語言實現(xiàn)一個 子集的編譯程序子集的編譯程序(P0人人)2022-4-22第 59 頁4. 用用P2編譯編譯P3，得到，得到P4（ C的編譯程序的編譯程序）語言語言子集子集機器語言機器語言子集子集機器語言機器語言機器語言機器語言語言語言機器語言機器語言機器語言機器語言自展技術(shù)舉例自展技術(shù)舉例CC語言的編譯程序語言的編譯程序3. 用用 子集編制子集編制 語言的編譯程序語言的編譯程序(P3人人)C的編譯程序的編譯程序2022-4-22第 60 頁3 利用編譯程序自動生成器利用編譯程序自動生成器詞法規(guī)則說明詞法規(guī)