ch1 編譯原理引論

1、編譯原理編譯原理n計算機科學技術(shù)系計算機科學技術(shù)系n李薇李薇為什么要學習編譯原理n必修主干課程必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計者，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計者與計算機之間的基本界面。與計算機之間的基本界面。n通過學習該課程，掌握編譯的基本理論、常用的編譯通過學習該課程，掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機理。能運用技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機理。能運用所學技術(shù)解決實際問題，能所學技術(shù)解決實際問題，能獨立編寫一個小型編譯系獨立編寫一個小型編譯系統(tǒng)統(tǒng)。n此外，通過學習編譯原理可以更好地理解程序語言的此外，通過學習編譯原理可以更好地理解程序語言的

2、內(nèi)部機制內(nèi)部機制, ,從而更好地理解和運用程序設(shè)計語言。能從而更好地理解和運用程序設(shè)計語言。能運用編譯程序構(gòu)造的原理和技術(shù)完成運用編譯程序構(gòu)造的原理和技術(shù)完成相關(guān)軟件工具的相關(guān)軟件工具的設(shè)計和開發(fā)設(shè)計和開發(fā)工作。工作。課程內(nèi)容課程內(nèi)容q介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法q介紹的理論知識：形式語言和自動機理論、語法制導的定義和屬性文法、類型論等q強調(diào)形式描述技術(shù)和自動生成技術(shù)課課 程程 簡簡 介介先行課程先行課程 高等數(shù)學、離散數(shù)學、匯編語言、數(shù)據(jù)結(jié)構(gòu)n 參考資料參考資料n國外編譯原理領(lǐng)域內(nèi)的國外編譯原理領(lǐng)域內(nèi)的3本權(quán)威書籍：當代編譯技術(shù)三大圣經(jīng)！本權(quán)威書籍：當代編譯技術(shù)三大圣經(jīng)！1、龍書（

3、Dragon book）2、鯨書（Whale book）3、虎書（Tiger book）n國內(nèi)編譯原理領(lǐng)域內(nèi)的權(quán)威書籍：國內(nèi)編譯原理領(lǐng)域內(nèi)的權(quán)威書籍： 1. 陳意云陳意云 編譯原理編譯原理高等教育出版社高等教育出版社2. 呂映芝呂映芝 編譯原理編譯原理清華大學教育出版社；清華大學教育出版社；3. 陳英陳英 編譯原理編譯原理清華工大學出版社清華工大學出版社4.蔣宗禮蔣宗禮 編譯原理編譯原理高等教育出版社高等教育出版社5. 劉磊劉磊 編譯原理及實現(xiàn)編譯原理及實現(xiàn)機械工業(yè)出版社機械工業(yè)出版社 課程特點：理論性強，算法復(fù)雜課程特點：理論性強，算法復(fù)雜n平時（平時（20%）q無故曠課：無故曠課：5q一本

4、教材，一本教材，認真聽課認真聽課：以講義為主，做適當?shù)墓P記：以講義為主，做適當?shù)墓P記q認真完成課堂和課后認真完成課堂和課后作業(yè)作業(yè)n期末（期末（80%）:閉卷筆試閉卷筆試第一章第一章 編譯概述編譯概述1.1.掌握編譯程序中所涉及的有關(guān)名詞術(shù)語掌握編譯程序中所涉及的有關(guān)名詞術(shù)語2.2.理解編譯程序總的框架，明確編譯程序工理解編譯程序總的框架，明確編譯程序工作的基本過程及各階段的基本任務(wù)作的基本過程及各階段的基本任務(wù)教學目標教學目標1.1. .程序的翻譯程序的翻譯1.2. 編譯的過程編譯的過程1.3. 編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu)1.4. 編譯程序的生成編譯程序的生成 1.5. 編譯技術(shù)的

5、應(yīng)用及發(fā)展編譯技術(shù)的應(yīng)用及發(fā)展教學內(nèi)容1.1 程序的翻譯程序的翻譯n語言和翻譯語言和翻譯：語言是人類交流思想和信息的工具。如自然語言，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。計算機語言同樣是豐富多彩的。2022年5月8日星期日第16頁n機器語言機器語言 (machine language) C7 06 0000 0002n匯編語言匯編語言 (assembler language) MOV X , 2n高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序？為什么要使用編譯程序？程序語言的分類n低級語言（低級語言（Low lev

6、el Language)q機器語言、匯編語言機器語言、匯編語言q特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、繁瑣、費時、易出錯。繁瑣、費時、易出錯。n高級語言高級語言 n - Fortran、Pascal、C 語言等語言等q特點：不依賴具體機器，移植性好、對用戶要求特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護等。低、易使用、易維護等。n計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外的另一種語言呢？n解決這一問題的方法：翻譯程序！翻譯程序！翻譯程序n翻譯程序：能夠把某一種語言程序（稱為源語言源語言程序）轉(zhuǎn)換成另一種語言程序

7、（稱為目標語言目標語言程序）的一個程序，而后者與前者在邏輯上是等價的。n程序翻譯的方式通常有兩種，一種是編譯方式，另一種是解釋方式。源程序翻譯程序目標程序編譯程序n編譯程序編譯程序：如果一個翻譯程序的源語言源語言是某種高級語言，其目標語言目標語言是相對于某一計算機的匯編語言或機器語言，則稱這種翻譯程序為編譯程序（或稱為編譯器）。n若編譯生成的目標程序不是機器代碼，而是匯編語言程序，則還要增加一個會變程序?qū)⑵鋾優(yōu)闄C器代碼。源程序（高級語言編寫）編譯程序目標程序（機器語言或匯編語言編寫）匯編程序n如果一個翻譯程序的源語言是某種匯編語言，其目標語言是某一計算機的機器語言，則稱這種翻譯程序為匯編程序

8、。源程序（匯編語言編寫）匯編程序目標程序（機器語言編寫）解釋程序n解釋程序解釋程序: 是一種語言處理程序，它以源程序作為輸入，但不產(chǎn)生目標代碼，它將源程序中的語句按動態(tài)順序，逐句翻譯成課執(zhí)行代碼，一旦具備執(zhí)行條件，則立即執(zhí)行這一階段代碼得到部分結(jié)果。源程序（高級語言編寫）解釋程序計算結(jié)果 特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、可移植性好，易于查錯，但速度慢可移植性好，易于查錯，但速度慢n編譯和解釋程序編譯和解釋程序n編譯程序的工作相當于載翻譯一本原著，計算機運行編譯后的目標程序，相當于閱讀一本譯著；而解釋程序的工作相當于在進行同聲翻譯，計算機運行解釋程序，

9、相當于我們直接通過翻譯聽外賓講話。n程序的編譯執(zhí)行：程序的編譯執(zhí)行：輸入數(shù)據(jù)輸入數(shù)據(jù)源程序源程序編譯程序編譯程序運行系統(tǒng)運行系統(tǒng)目標程序目標程序n程序的解釋執(zhí)行：q如：BASIC、Prolog，問題：效率低下解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算結(jié)果為什么解釋運行的工作效率低于編譯方式？為什么解釋運行的工作效率低于編譯方式？編譯程序與解釋程序的差別n根本區(qū)別：是否生成目標代碼！功能功能工作結(jié)果工作結(jié)果實現(xiàn)技術(shù)上實現(xiàn)技術(shù)上解釋解釋程序程序源程序的一個執(zhí)行執(zhí)行系統(tǒng)源程序的執(zhí)行結(jié)果執(zhí)行結(jié)果執(zhí)行中間代碼編譯編譯程序程序源程序的一個轉(zhuǎn)換轉(zhuǎn)換系統(tǒng)源程序的目標代碼目標代碼把中間代碼轉(zhuǎn)換成目

10、標程序“編譯+解釋執(zhí)行”系統(tǒng)源程序源程序編譯程序編譯程序源程序的中間形式輸出數(shù)據(jù)輸出數(shù)據(jù)解釋程序解釋程序輸入數(shù)據(jù)輸入數(shù)據(jù)例如例如Java語言語言.java java源程序文件.class 二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯編譯程序在計算機系統(tǒng)中的位置n編譯程序是一種軟件，是系統(tǒng)軟件。通常認為系統(tǒng)軟件是居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。翻譯程序所處的層次翻譯程序所處的層次高級語言語言處理程序操作系統(tǒng)匯編語言計算機硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言.幾個概念幾個概念n宿主機：運行編

11、譯程序的計算機n目標機：運行編譯程序所產(chǎn)生的目標代碼的計算機n交叉編譯程序：一個編譯程序產(chǎn)生不同于其宿主機的機器代碼n可變目標編譯程序：不需要重寫編譯程序中與機器無關(guān)的部分就能改變目標機對編譯程序的一些說明對編譯程序的一些說明n編譯程序?qū)嵸|(zhì)上是一個翻譯程序翻譯程序，要注意等價等價變換n本課程的任務(wù)任務(wù)就是講解在這個轉(zhuǎn)換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器n轉(zhuǎn)換是一個總體的功能，要抓住總體結(jié)構(gòu)，逐層細分，寫編譯器時要體現(xiàn)軟件工程中軟件設(shè)計的原則軟件設(shè)計的原則，自頂向下，逐層分解。n編譯器要完成的轉(zhuǎn)換任務(wù)相當復(fù)雜，實現(xiàn)編譯器時必須分步驟分階段分步驟分階段

12、實現(xiàn)。分階段實現(xiàn)的好處是能夠簡化簡化程序的設(shè)計程序的設(shè)計，當然也可以不分階段實現(xiàn)。 編譯原理是討論編譯程序設(shè)計的基本理論、基本概念、基本方法 什么是編譯原理什么是編譯原理2022-5-834編譯器和集成開發(fā)環(huán)境n編譯器：即編譯程序，把高級語言經(jīng)分析翻譯為低級語言。編譯器：即編譯程序，把高級語言經(jīng)分析翻譯為低級語言。n集成開發(fā)環(huán)境：簡稱集成開發(fā)環(huán)境：簡稱IDE（Integrated Develop Environment），），是用于提供程序開發(fā)環(huán)境的應(yīng)用程序，一般包括代碼編輯器、編譯是用于提供程序開發(fā)環(huán)境的應(yīng)用程序，一般包括代碼編輯器、編譯器、調(diào)試器和圖形用戶界面工具。器、調(diào)試器和圖形用戶界面

13、工具。q背景：早期程序設(shè)計的各個階段都要用不同的軟件來進行處背景：早期程序設(shè)計的各個階段都要用不同的軟件來進行處理理,如先用字處理軟件編輯源程序，再用編譯程序進行編譯，如先用字處理軟件編輯源程序，再用編譯程序進行編譯，然后用鏈接程序進行函數(shù)、模塊連接然后用鏈接程序進行函數(shù)、模塊連接, 開發(fā)者必須在幾種軟件開發(fā)者必須在幾種軟件間來回切換操作。間來回切換操作。 n人們習慣上經(jīng)常把人們習慣上經(jīng)常把IDE稱為編譯器。稱為編譯器。編譯原理引論35常見語言及其IDE語言IDECTC2.0C+C+ Builder, VC+6.0, TC3.0C#VS.NETPascalTurbo PascalOOPasca

14、lDelphiVBVB6.0 (解釋器)JavaEclipse, JBuilder1.2 編譯的過程編譯的過程n1.編譯程序的工作過程編譯程序的工作過程n2.2.編譯器各階段的工作編譯器各階段的工作1.1.編譯程序的工作過程編譯程序的工作過程n編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。n將英文句子“I wish you success I wish you success 翻譯成中文。n兩階段完成翻譯 分析：分析： 分析單詞：I，wish，you，success 分析語法：主語，謂語，賓語，賓補 分析語義：我希望你成功 綜合：綜合： 綜合英語的意思、上下文環(huán)境和漢語的表達習慣，完成翻

15、譯：祝你成功1.1.編譯程序的工作過程編譯程序的工作過程n翻譯外文資料：q1、能識別出句子中的一個單詞；q2、分析句子的語法結(jié)構(gòu)；q3、根據(jù)句子的含義進行初步翻譯；q4、對譯文進行修飾；q5、寫出最后的譯文。翻譯外文資料與編譯源程序進行類比翻譯外文翻譯外文編譯程序編譯程序分析分析識別單詞識別單詞分析句子分析句子根據(jù)語義進行根據(jù)語義進行初步翻譯初步翻譯詞法分析詞法分析語法分析語法分析語義分析、生成中間代碼語義分析、生成中間代碼綜合綜合修辭加工修辭加工寫出譯文寫出譯文代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成將編譯過程劃分為將編譯過程劃分為5個基本階段個基本階段詞法分析詞法分析語法分析語法分析語義分

16、析及中間代碼生成語義分析及中間代碼生成代碼優(yōu)化代碼優(yōu)化目標代碼生成目標代碼生成n從概念上來講，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個階段進行的操作在邏輯上是緊密連接在一起的。n事實上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構(gòu)造出來了。1.2 編譯的過程編譯的過程n1.編譯程序的工作過程編譯程序的工作過程n2.2.編譯器各階段的工作編譯器各階段的工作2.2.編譯器各階段的工作編譯器各階段的工作(1)(1)詞法分析詞法分析n詞法分析階段是編譯過程的第一個階段。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程

17、序，對構(gòu)成源程序的字符流進行掃描和分解，根據(jù)語言的詞法規(guī)則詞法規(guī)則識別出一個個具有獨立意義的最小語法單位，即單詞。2.2.編譯器各階段的工作編譯器各階段的工作n根據(jù)根據(jù)詞法規(guī)則詞法規(guī)則分析和識別單詞單詞。n把需要存放的單詞放到符號表中，如變量名，標號，常量等。n工作依據(jù):源語言的構(gòu)詞規(guī)則(即詞法)，也稱為模式(pattern)。q標識符的模式是：以字母開頭的字母數(shù)字序列。n例：例：sum=(10+20)*(num+square); 結(jié)果結(jié)果q(標識符，標識符，sum)q(賦值號，賦值號，=)q(左括號，左括號， ( )q(整常數(shù)，整常數(shù)，10)q(加號，加號，+ )q(整常數(shù)，整常數(shù)，20)q

18、(右括號，右括號， ) )q(乘號，乘號，* )q(左括號，左括號， ( )q(標識符，標識符，num)q(加號，加號，+ )q(標識符，標識符，square)q(右括號，右括號， ) )q(分號，分號，; )n詞法分析的功能如下：v識別出源程序中意義獨立的最小詞法單位單詞。v刪除無用的空格、回車和其他與輸入介質(zhì)有關(guān)的符號v刪除程序員為了提高程序可讀性所加的注釋v如果發(fā)現(xiàn)錯誤則報告出錯n(2)(2)語法分析語法分析n根據(jù)根據(jù)語法規(guī)則語法規(guī)則（即語言的文法），分析并識別出（即語言的文法），分析并識別出各種各種語法成分語法成分（如表達式、語句、函數(shù)等），并（如表達式、語句、函數(shù)等），并進行進行語法

19、正確性檢查語法正確性檢查。n通常將語法分析的結(jié)果表示為語法樹。通常將語法分析的結(jié)果表示為語法樹。sum=(10+20)*(num+square);n語法分析的功能是進行層次分析，把源程序的單詞序列組成語法短語(表示成語法樹)。依據(jù)的是語法規(guī)則。C語言的賦值語句的規(guī)則為：nn單詞序列sum=(10+20)*(num+square);之所以能表示成上圖的語法樹，依據(jù)的是賦值語句和表達式的語法規(guī)則。:=“=”:=“+” | “*”:=“(”“)” | | | n(3)語義分析及中間代碼生成語義分析及中間代碼生成n語義分析階段的任務(wù)是審查源程序有無語義錯誤。n工作依據(jù)：源語言的語義規(guī)則n一個重要任務(wù)：

20、類型檢查q根據(jù)規(guī)則檢查每個運算符及其運算對象是否符合要求；q數(shù)組的下標是否合法；q過程調(diào)用時，形參與實參個數(shù)、類型是否匹配等n(3)語義分析及中間代碼生成語義分析及中間代碼生成n源程序中有些語法成分，按照語法規(guī)則去判斷，它是正確的，但它不符合語義規(guī)則。比如使用了沒有聲明的變量；或者給一個過程名賦值；或者調(diào)用函數(shù)時參數(shù)類型不合適或者參加運算的兩個變量類型不匹配等等。n比如下邊的程序片段：int arr2,c;c = arr1 * 10 ;n其中的賦值語句是符合語法規(guī)則的，但是因為沒有聲明變量arr1，而存在語義錯。n中間代碼生成中間代碼生成( (可選）可選）n所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義

21、明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計為多種多樣的形式，重要的設(shè)計原則為兩點：一是容易生成；二是容易將它翻譯成目標代碼。n中間代碼的形式：中間代碼的形式： q四元式、三元式、逆波蘭表示四元式、三元式、逆波蘭表示n中間代碼中間代碼(intermediate Code)n例例:sum=(10+20)*(num+square); n(4) 中間代碼優(yōu)化代碼優(yōu)化( (可選）可選）n代碼優(yōu)化階段的任務(wù)是對前階段產(chǎn)生的中間代碼進行變換或進行改造，目的是使生成的目標代碼更為高效，即省時間和省空間。例：例： sum=(10+20)*(num+square) 得到的四元式得到的四元式nT1=10+20nT2=nu

22、m+squarenT3=T1*T2nsum=T3 優(yōu)化后優(yōu)化后nT1=num+squarenSum=30*T1n這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削弱、循環(huán)優(yōu)化等優(yōu)化工作將在后面的章節(jié)詳細介紹。n代碼優(yōu)化工作會降低編譯程序的編譯速度，因此編譯優(yōu)化階段常常作為可選擇階段，編譯程序具有控制機制以允許用戶在編譯速度和目標代碼的質(zhì)量間進行權(quán)衡。n思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？n(5) (5) 目標代碼生成目標代碼生成n目標代碼生成階段的任務(wù)是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含

23、義有關(guān)，這個階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。n涉及到的兩個重要問題：q對程序中使用的每個變量要指定存儲單元q對變量進行寄存器分配例：例： sum=(10+20)*(num+square) 得到的優(yōu)化后四元式得到的優(yōu)化后四元式nT1=num+squarenSum=30*T1生成如下指令序列：生成如下指令序列：nMOV num, R1nMOV square, R2nADD R2, R1nMUL 30, R1nMOV R1, sum目標代碼可采用如下三種形式之一：(1)具有絕對地址的機器指令代碼。(2)匯編

24、語言形式的目標程序。需要經(jīng)過匯編程序匯編，以產(chǎn)生機器代碼。(3)可重定位的指令代碼。多數(shù)編譯程序所產(chǎn)生的目標代碼都是這種類型。語句sum=(10+20)*(num+square);的翻譯過程編譯過程小結(jié)編譯過程小結(jié)目標代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序S.PO.Pn上述編譯過程的階段劃分是一種典型的處理模式，上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的編譯程序都包括這樣幾個階段。事實上并非所有的編譯程序都包括這樣幾個階段。有些編譯程序并不要中間代碼，即不存在中間代有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；有些編譯程序不進行優(yōu)化，優(yōu)化

25、階碼生成階段；有些編譯程序不進行優(yōu)化，優(yōu)化階段即可省去段即可省去; ;有些最簡單的編譯程序只有詞法分析，有些最簡單的編譯程序只有詞法分析，語法分析；語義分析和目標代碼生成。語法分析；語義分析和目標代碼生成。1.3 編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu) 按邏輯功能不同，可將編譯過程劃分為五個基本階 段，與此相對應(yīng)，我們將實現(xiàn)整個編譯過程的編譯程序劃 分為五個邏輯階段（即五個邏輯子過程）。每個階段中都要有：符號表管理符號表管理和錯誤處理錯誤處理典型的編譯程序具有典型的編譯程序具有7個邏輯部分個邏輯部分S.PO.P語義分析及語義分析及生成中間代碼生成中間代碼程序程序代碼生成程序代碼生成程序代碼優(yōu)化代

26、碼優(yōu)化程序程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理 詞法分析：識別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標識符、字面量、特殊符號； 語法分析：得到語言結(jié)構(gòu)并以樹的形式表示 語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，可修改樹結(jié)構(gòu)； 中間代碼生成（可選）：生成一種既接近目標語言，又與具體機器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致） 中間代碼優(yōu)化（可選）：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時間上都更省、更有效。 目標代碼生成：不同

27、形式的目標代碼匯編、可重定位、絕對機器指令; 符號表管理：合理組織符號，便于各階段查找、填寫等； 出錯處理：錯誤的種類詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。符號表管理n編譯程序的一項重要工作：q記錄源程序中使用的標識符q收集每個標識符的各種屬性信息n符號表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)q每個標識符在表中有一條記錄q記錄的域是標識符的屬性n對符號表結(jié)構(gòu)的要求：q應(yīng)允許快速地找到標識符的記錄q可在其中存取數(shù)據(jù)n標識符的各種屬性是在編譯的各個不同階段填入符號表的。聲明語句：float total, rate;n詞法分析器：qfloat是關(guān)鍵字qtotal、rate是標識符q在符號表中創(chuàng)建這兩個標識符的

28、記錄n語義分析器：qtotal、rate都表示變量qfloat表示這兩個變量的類型q可以把這兩種屬性及存儲分配信息填入符號表。n在語義分析和生成中間代碼時，還要在符號表中填入對這個float型變量進行存儲分配的信息。錯誤處理n在編譯的每個階段都可能檢測到源程序中存在的錯誤q詞法分析程序可以檢測出非法字符錯誤。q語法分析程序能夠發(fā)現(xiàn)記號流不符合語法規(guī)則的錯誤。q語義分析程序試圖檢測出具有正確的語法結(jié)構(gòu)，但對所涉及的操作無意義的結(jié)構(gòu)。q代碼生成程序可能發(fā)現(xiàn)目標程序區(qū)超出了允許范圍的錯誤。n處理與恢復(fù)q判斷位置和性質(zhì)q適當?shù)幕謴?fù)n出錯處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個重要指標。編譯有關(guān)的其他

29、概念n“遍”n前端和后端編譯器掃描的遍數(shù)n遍（趟）遍（趟）：是對源程序或源程序的中間結(jié)果從頭到尾掃描一遍，并作有關(guān)加工處理，生成新的中間結(jié)果或目標程序。n例如：詞法分析器對輸入源程序進行第一遍掃描，語法分析進行第二遍掃描n但一個階段對應(yīng)一遍掃描的工作方式是邏輯上的，由于多次掃描的方式需要大量的存儲空間存放中間表示，并且會增加一些不必要的輸入輸出操作，因此編譯器往往把若干個階段的工作結(jié)合起來，對應(yīng)一遍掃描，從而減少對程序的掃描遍數(shù)。n一個編譯程序應(yīng)分成幾遍，如何劃分，是與源程序、設(shè)計要求、硬件設(shè)備等諸因素有關(guān)的，因地難于統(tǒng)一劃定。n在主存可能的前提下，一般遍數(shù)盡可能少一點為好。但并不是每種語言都

30、可以用單遍編譯程序?qū)崿F(xiàn)。一遍掃描的編譯程序語法分析器語法分析器取記號取記號詞法分析器詞法分析器源程序源程序記號記號語法成分語法成分語義分析及代碼生成語義分析及代碼生成目標程序目標程序返回返回控制流控制流信息流信息流開始開始結(jié)束結(jié)束整理目標程序整理目標程序多遍編譯程序編譯程序總控詞法分析器語法分析器語義分析器中間代碼生成代碼優(yōu)化目標代碼生成源程序中間語言1，表中間語言2，表中間語言3，表中間語言4，表優(yōu)化代碼，表目標代碼符號表管理錯誤處理編譯階段的組合n在前面所討論的編譯過程中階段的劃分是編譯程序的邏輯組織。有時，常常把編譯的過程分為前端前端(front end)和后端后端(back end)，

31、前端的工作主要依賴于源語言而與目標機無關(guān), 后端工作依賴于目標機而一般不依賴源語言。根據(jù)編譯程序各部分功能，將編譯程序分成根據(jù)編譯程序各部分功能，將編譯程序分成前端前端和和后端后端 前端前端：通常將與：通常將與源程序源程序有關(guān)的編譯部分稱為前端。有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成詞法分析、語法分析、語義分析、中間代碼生成 -分析部分分析部分 特點：與特點：與源語言源語言有關(guān)有關(guān) 后端后端：與：與目標機目標機有關(guān)的部分稱為后端。有關(guān)的部分稱為后端。 代碼優(yōu)化、代碼生成代碼優(yōu)化、代碼生成-綜合部分綜合部分 特點：與特點：與目標機目標機有關(guān)有關(guān)編譯程序的前端和后端編

32、譯程序的前端和后端編譯階段的組合編譯階段的組合為什么生成中間代碼為什么生成中間代碼.java java源程序文件源程序文件.class 二進制字節(jié)碼文件二進制字節(jié)碼文件JavaJava虛擬機（虛擬機（JVM)JVM)本地計算機系統(tǒng)本地計算機系統(tǒng)編譯編譯同一前端同一前端+ +不同后端不同后端 不同機器構(gòu)成同一語言的編譯程序不同機器構(gòu)成同一語言的編譯程序例如例如JavaJava語言語言 不同前端不同前端+ +同一后端同一后端 同一機器生成幾個語言的編譯程序同一機器生成幾個語言的編譯程序例如例如GCCGCC 編譯程序集合編譯程序集合編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)編譯程序中的主要數(shù)據(jù)結(jié)構(gòu) (續(xù)續(xù))Token

33、表符號表常數(shù)表錯誤信息語法樹中間代碼表臨時文件目標代碼表2022年5月8日星期日第83頁1.4 1.4 編譯程序的設(shè)計編譯程序的設(shè)計n構(gòu)造編譯程序要掌握以下幾方面的內(nèi)容：q源語言：理解其結(jié)構(gòu)和含義q目標語言：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等q編譯方法2022年5月8日星期日第84頁1.4 1.4 編譯程序的設(shè)計編譯程序的設(shè)計n一般實現(xiàn)編譯程序的方法有：q1.直接用機器語言編寫編譯程序q2.用匯編語言編寫編譯程序n注：編譯程序核心部分常用匯編語言編寫q3.用高級語言編寫編譯程序n注：這是普遍采用的方法q4.自編譯q5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產(chǎn)生LALR分析

34、表)q6.移植（同種語言的編譯程序在不同類型的機器之間移植）1.4 編譯程序的生成編譯程序的生成n早期人們用匯編語言編寫編譯程序，但其效率低，實現(xiàn)困難，比如FORTRAN語言編譯器18年才完成。n專門的編譯編譯工具，可以支持編譯程序某些部分的自動生成。比如：LEX和YACC等。n說到一個編譯程序， 一定要知道它的源語言是什麼，目標語言是什麼，還有它的實現(xiàn)語言是什麼。常使用T型圖來表示一個編譯程序所涉及的三個語言。S：源語言 O：目標語言 T：編譯程序?qū)崿F(xiàn)語言S OTn開發(fā)編譯程序的途徑開發(fā)編譯程序的途徑:n自展法自展法n工具法工具法n自動生成法自動生成法n移植法移植法自展法自展法n利用A機器上

35、已有的用A代碼編寫的L1語言的編譯程序，把用L1語言編寫的L2語言的編譯程序進行編譯，得到A機器代碼實現(xiàn)的L2語言的編譯程序。表示為：L 2 語言A代碼L1語言L 1 語言A代碼A代碼L 2 語言A代碼A代碼n或者表示為：L 2 語言A代碼L1語言L 1 語言A代碼A代碼L 2 語言A代碼A代碼n問題一：如何直接在一個機器上實現(xiàn)問題一：如何直接在一個機器上實現(xiàn)C語言編譯器？語言編譯器？n解決：解決：q用匯編語言實現(xiàn)一個子集的編譯程序用匯編語言實現(xiàn)一個子集的編譯程序(P0人人)q用匯編程序處理該程序用匯編程序處理該程序,得到得到(P2:可直接運行可直接運行)q用子集編制語言的編譯程序用子集編制語

36、言的編譯程序(P3人人)q用用P2編譯編譯P3，得到，得到P4自展4. 用用P2P2編譯編譯P3P3，得到，得到P4P4語言語言機器語言機器語言機器語言機器語言子集子集機器語言機器語言機器語言機器語言子集子集匯編語言匯編語言機器語言機器語言1. 用匯編語言實現(xiàn)一個用匯編語言實現(xiàn)一個 子集的編譯程序子集的編譯程序(P0(P0人人) )匯編語言匯編語言機器語言機器語言機器語言機器語言子集子集機器語言機器語言機器語言機器語言2. 用匯編程序用匯編程序(P1)(P1)處理該程序處理該程序, ,得到得到(P2:(P2:可直接運行可直接運行) )語言語言子集子集機器語言機器語言3. 用子集編制用子集編制

37、語言的編譯程序語言的編譯程序(P3(P3人人) )移植n問題二：問題二：A A機上有一個機上有一個C C語言編譯器，是否可利用此編語言編譯器，是否可利用此編譯器實現(xiàn)譯器實現(xiàn)B B機上的機上的C C語言編譯器？語言編譯器？q條件：機有條件：機有 語言的編譯程序語言的編譯程序q目的：實現(xiàn)目的：實現(xiàn)機的機的語言的編譯語言的編譯語言語言A機器機器A機器機器語言語言B機器機器機器機器要完成的任務(wù)要完成的任務(wù)語言語言語言語言機器機器語言語言機器機器機器機器語言語言機器機器機器機器語言語言語語 言言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器需要編寫的程序需要編寫的程序1)問題的分析1. 1

38、. ( (人人) )用語言編制用語言編制B B機的編譯程序機的編譯程序P0(CP0(C2.2. ( (機的機的C C編譯編譯P1)P1)編譯編譯P0P0，得到在，得到在A A機上可運行的機上可運行的P2(CP2(C語言語言語語 言言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器2)問題的解決辦法3.(3.(機的機的P2)P2)編譯編譯P0P0，得到在，得到在B B機上可運行的機上可運行的P3(CP3(C語言語言語言語言機器機器語言語言機器機器機器機器語言語言機器機器機器機器語言語言語語 言言機器機器語言語言機器機器A機器機器語言語言A機器機器機器機器n編譯程序移植：編譯程序移植：用A機器上的L語言編寫能在機器B上運行的L語言的編譯程序n先用L語言編寫出在A機器上運行的產(chǎn)生B機器代碼的L編譯程序源程序，然后把該程序經(jīng)過A機器上的L編譯程序編譯后得到能在A機器上運行的產(chǎn)生B機器代碼的編譯程序，用這個編譯程序再一次編譯上述源程序。 LBLLBLLAALBALBBLBLLAALBALBLLBALBB本機編譯器的利用n問題三：問題三： A A機上有一個機上有一個C C語言編譯器，現(xiàn)要實現(xiàn)一個新語言編譯器，現(xiàn)要實現(xiàn)一個新語言語言NE