ch編譯原理引論課件

ch編譯原理引論ch編譯原理引論ch編譯原理引論為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序設計者與計算機之間的根本界面。通過學習該課程，掌握編譯的根本理論、常用的編譯技術，了解編譯過程及編譯系統(tǒng)構造和機理。能運用所學技術解決實際問題，能獨立編寫一個小型編譯系統(tǒng)。此外，通過學習編譯原理可以更好地理解程序語言的內部機制,從而更好地理解和運用程序設計語言。能運用編譯程序構造的原理和技術完成相關軟件工具的設計和開發(fā)工作。ch編譯原理引論ch編譯原理引論ch編譯原理引論為什么要學習1為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序設計者與計算機之間的根本界面。通過學習該課程，掌握編譯的根本理論、常用的編譯技術，了解編譯過程及編譯系統(tǒng)構造和機理。能運用所學技術解決實際問題，能獨立編寫一個小型編譯系統(tǒng)。此外，通過學習編譯原理可以更好地理解程序語言的內部機制,從而更好地理解和運用程序設計語言。能運用編譯程序構造的原理和技術完成相關軟件工具的設計和開發(fā)工作。為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序2課程內容介紹編譯器構造的一般原理和根本實現(xiàn)方法介紹的理論知識：形式語言和自動機理論、語法制導的定義和屬性文法、類型論等強調形式描述技術和自動生成技術課程簡介先行課程高等數(shù)學、Ｃ、離散數(shù)學、匯編語言、數(shù)據構造課程內容課程簡介先行課程3參考資料國外編譯原理領域內的3本權威書籍：當代編譯技術三大圣經！1、龍書〔Dragonbook〕參考資料國外編譯原理領域內的3本權威書籍：當代編譯技術三大42、鯨書〔Whalebook〕

2、鯨書〔Whalebook〕

53、虎書〔Tigerbook〕3、虎書〔Tigerbook〕6國內編譯原理領域內的權威書籍：1.陳意云?編譯原理?高等教育出版社ch編譯原理引論課件72.呂映芝?編譯原理?清華大學教育出版社；ch編譯原理引論課件83.陳英?編譯原理?清華工大學出版社3.陳英?編譯原理?清華工大學出版社94.蔣宗禮?編譯原理?高等教育出版社ch編譯原理引論課件105.劉磊?編譯原理及實現(xiàn)?機械工業(yè)出版社ch編譯原理引論課件11要求及學習方法課程特點：理論性強，算法復雜平時〔20%〕無故曠課：－5一本教材，認真聽課：以講義為主，做適當?shù)墓P記認真完成課堂和課后作業(yè)期末〔80%〕:閉卷筆試要求及學習方法課程特點：理論性強，算法復雜12第一章編譯概述掌握編譯程序中所涉及的有關名詞術語2.理解編譯程序總的框架，明確編譯程序工作的根本過程及各階段的根本任務教學目標第一章編譯概述掌握編譯程序中所涉及的有關名詞術語教學目131.2.編譯的過程1.3.編譯程序的邏輯構造1.4.編譯程序的生成1.5.編譯技術的應用及開展教學內容教學內容14

程序的翻譯語言和翻譯：語言是人類交流思想和信息的工具。如自然語言，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。計算機語言同樣是豐富多彩的。程序的翻譯語言和翻譯：語言是人類交流思想和信息的工具。如1512/9/2022第16頁機器語言(machinelanguage)C70600000002匯編語言(assemblerlanguage)

MOVX,2高級語言(high-levellanguage)

X=2為什么要使用編譯程序？12/9/2022第16頁機器語言(machinelan16程序語言的分類低級語言〔LowlevelLanguage)機器語言、匯編語言特點：與特定的機器有關，成效高，但使用復雜、繁瑣、費時、易出錯。高級語言--Fortran、Pascal、C語言等特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護等。程序語言的分類低級語言〔LowlevelLanguage17計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外的另一種語言呢？？解決這一問題的方法：翻譯程序！！計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外18翻譯程序翻譯程序：能夠把某一種語言程序〔稱為源語言程序〕轉換成另一種語言程序〔稱為目標語言程序〕的一個程序，而后者與前者在邏輯上是等價的。程序翻譯的方式通常有兩種，一種是編譯方式，另一種是解釋方式。源程序翻譯程序目標程序翻譯程序翻譯程序：能夠把某一種語言程序〔稱為源語言程序〕轉換19編譯程序編譯程序：如果一個翻譯程序的源語言是某種高級語言，其目標語言是相對于某一計算機的匯編語言或機器語言，那么稱這種翻譯程序為編譯程序〔或稱為編譯器〕。假設編譯生成的目標程序不是機器代碼，而是匯編語言程序，那么還要增加一個會變程序將其會變?yōu)闄C器代碼。源程序（高級語言編寫）編譯程序目標程序（機器語言或匯編語言編寫）編譯程序編譯程序：如果一個翻譯程序的源語言是某種高級語言，其20匯編程序如果一個翻譯程序的源語言是某種匯編語言，其目標語言是某一計算機的機器語言，那么稱這種翻譯程序為匯編程序。源程序（匯編語言編寫）匯編程序目標程序（機器語言編寫）匯編程序如果一個翻譯程序的源語言是某種匯編語言，其目標語言是21解釋程序解釋程序:是一種語言處理程序，它以源程序作為輸入，但不產生目標代碼，它將源程序中的語句按動態(tài)順序，逐句翻譯成課執(zhí)行代碼，一旦具備執(zhí)行條件，那么立即執(zhí)行這一階段代碼得到局部結果。源程序（高級語言編寫）解釋程序計算結果特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、可移植性好，易于查錯，但速度慢解釋程序解釋程序:是一種語言處理程序，它以源程序作為輸入，22編譯和解釋程序編譯程序的工作相當于載翻譯一本原著，計算機運行編譯后的目標程序，相當于閱讀一本譯著；而解釋程序的工作相當于在進展同聲翻譯，計算機運行解釋程序，相當于我們直接通過翻譯聽外賓講話。編譯和解釋程序23程序的編譯執(zhí)行：輸入數(shù)據源程序編譯程序運行系統(tǒng)目標程序輸入數(shù)據源程序編譯程序運行系統(tǒng)目標程序24程序的解釋執(zhí)行：如：BASIC、Prolog，問題：效率低下解釋程序源程序輸入數(shù)據計算結果為什么解釋運行的工作效率低于編譯方式？？程序的解釋執(zhí)行：解釋程序源程序輸入數(shù)據計算結果為什么解釋運行25編譯程序與解釋程序的差異根本區(qū)別：是否生成目標代碼！功能工作結果實現(xiàn)技術上解釋程序源程序的一個執(zhí)行系統(tǒng)源程序的執(zhí)行結果執(zhí)行中間代碼編譯程序源程序的一個轉換系統(tǒng)源程序的目標代碼把中間代碼轉換成目標程序編譯程序與解釋程序的差異根本區(qū)別：是否生成目標代碼！功能工作26“編譯+解釋執(zhí)行〞系統(tǒng)源程序編譯程序源程序的中間形式輸出數(shù)據解釋程序輸入數(shù)據“編譯+解釋執(zhí)行〞系統(tǒng)源程序編譯程序源程序的中間形式輸出數(shù)據27例如Java語言.java

java源程序文件.class二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯例如Java語言.javajava源程序文件.cl28編譯程序在計算機系統(tǒng)中的位置編譯程序是一種軟件，是系統(tǒng)軟件。通常認為系統(tǒng)軟件是居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。編譯程序在計算機系統(tǒng)中的位置編譯程序是一種軟件，是系統(tǒng)軟件。29翻譯程序所處的層次高級語言語言處理程序操作系統(tǒng)匯編語言計算機硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言............翻譯程序所處的層次高語言處理程序操作系統(tǒng)計算機硬件CCBas30幾個概念宿主機：運行編譯程序的計算機目標機：運行編譯程序所產生的目標代碼的計算機穿插編譯程序：一個編譯程序產生不同于其宿主機的機器代碼可變目標編譯程序：不需要重寫編譯程序中與機器無關的局部就能改變目標機幾個概念宿主機：運行編譯程序的計算機31對編譯程序的一些說明編譯程序實質上是一個翻譯程序，要注意等價變換本課程的任務就是講解在這個轉換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器轉換是一個總體的功能，要抓住總體構造，逐層細分，寫編譯器時要表達軟件工程中軟件設計的原那么，自頂向下，逐層分解。編譯器要完成的轉換任務相當復雜，實現(xiàn)編譯器時必須分步驟分階段實現(xiàn)。分階段實現(xiàn)的好處是能夠簡化程序的設計，當然也可以不分階段實現(xiàn)。對編譯程序的一些說明編譯程序實質上是一個翻譯程序，要注意等價32編譯原理是討論編譯程序設計的根本理論、根本概念、根本方法什么是編譯原理編譯原理是討論編譯程序設計的根本理論、根本概念3312/9/202234編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序，把高級語言經分析翻譯為低級語言。集成開發(fā)環(huán)境：簡稱IDE〔IntegratedDevelopEnvironment〕，是用于提供程序開發(fā)環(huán)境的應用程序，一般包括代碼編輯器、編譯器、調試器和圖形用戶界面工具。背景：早期程序設計的各個階段都要用不同的軟件來進展處理,如先用字處理軟件編輯源程序，再用編譯程序進展編譯，然后用鏈接程序進展函數(shù)、模塊連接,開發(fā)者必須在幾種軟件間來回切換操作。人們習慣上經常把IDE稱為編譯器。12/9/202234編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序34編譯原理引論35常見語言及其IDE語言IDECTC2.0C++C++Builder,VC++6.0,TC3.0C#VS.NETPascalTurboPascalOOPascalDelphiVBVB6.0(解釋器)JavaEclipse,JBuilder編譯原理引論35常見語言及其IDE語言IDECTC2.0C+351.2編譯的過程1.編譯程序的工作過程1.2編譯的過程1.編譯程序的工作過程36編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。將英文句子“Iwishyousuccess翻譯成中文。兩階段完成翻譯

分析：分析單詞：I，wish，you，success分析語法：主語，謂語，賓語，賓補分析語義：我希望你成功

綜合：綜合英語的意思、上下文環(huán)境和漢語的表達習慣，完成翻譯：祝你成功編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。37翻譯外文資料：1、能識別出句子中的一個單詞；2、分析句子的語法構造；3、根據句子的含義進展初步翻譯；4、對譯文進展修飾；5、寫出最后的譯文。翻譯外文資料：38翻譯外文資料與編譯源程序進展類比翻譯外文編譯程序分析識別單詞分析句子根據語義進行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標代碼生成翻譯外文資料與編譯源程序進展類比翻譯外文編譯程序識別單詞詞法39將編譯過程劃分為5個根本階段詞法分析語法分析語義分析及中間代碼生成代碼優(yōu)化目標代碼生成將編譯過程劃分為5個根本階段詞法分析語法分析語義分析及中間代40從概念上來講，一個編譯程序的整個工作過程是劃分成階段進展的，每個階段將源程序的一種表示形式轉換成另一種表示形式，各個階段進展的操作在邏輯上是嚴密連接在一起的。事實上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構造出來了。從概念上來講，一個編譯程序的整個工作過程是劃分成階段進展的，411.2編譯的過程1.編譯程序的工作過程1.2編譯的過程1.編譯程序的工作過程42(1)詞法分析詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構成源程序的字符流進展掃描和分解，根據語言的詞法規(guī)那么識別出一個個具有獨立意義的最小語法單位，即單詞。(1)詞法分析43根據詞法規(guī)那么分析和識別單詞。把需要存放的單詞放到符號表中，如變量名，標號，常量等。工作依據:源語言的構詞規(guī)那么(即詞法)，也稱為模式(pattern)。標識符的模式是：以字母開頭的字母數(shù)字序列。根據詞法規(guī)那么分析和識別單詞。44例：sum=(10+20)*(num+square);結果(標識符，sum)(賦值號，=)(左括號，()(整常數(shù)，10)(加號，+)(整常數(shù)，20)(右括號，))(乘號，*)(左括號，()(標識符，num)(加號，+)(標識符，square)(右括號，))(分號，;)例：結果45詞法分析的功能如下：識別出源程序中意義獨立的最小詞法單位—單詞。刪除無用的空格、回車和其他與輸入介質有關的符號刪除程序員為了提高程序可讀性所加的注釋如果發(fā)現(xiàn)錯誤那么報告出錯詞法分析的功能如下：46(2)語法分析根據語法規(guī)那么〔即語言的文法〕，分析并識別出各種語法成分〔如表達式、語句、函數(shù)等〕，并進展語法正確性檢查。通常將語法分析的結果表示為語法樹。(2)語法分析47sum=(10+20)*(num+square);sum=(10+20)*(num+square);48語法分析的功能是進展層次分析，把源程序的單詞序列組成語法短語(表示成語法樹)。依據的是語法規(guī)那么。C語言的賦值語句的規(guī)那么為：

單詞序列sum=(10+20)*(num+square);之所以能表示成上圖的語法樹，依據的是賦值語句和表達式的語法規(guī)那么。

<賦值語句>::=<標識符>“=〞<表達式><表達式>::=<表達式>“+〞<表達式>|<表達式>“*〞<表達式><表達式>::=“(〞<表達式>“)〞|<標識符>|<整數(shù)>|<實數(shù)>語法分析的功能是進展層次分析，把源程序的單詞序列組成語法短49(3)語義分析及中間代碼生成語義分析階段的任務是審查源程序有無語義錯誤。工作依據：源語言的語義規(guī)那么一個重要任務：類型檢查根據規(guī)那么檢查每個運算符及其運算對象是否符合要求；數(shù)組的下標是否合法；過程調用時，形參與實參個數(shù)、類型是否匹配等(3)語義分析及中間代碼生成50(3)語義分析及中間代碼生成源程序中有些語法成分，按照語法規(guī)那么去判斷，它是正確的，但它不符合語義規(guī)那么。比方使用了沒有聲明的變量；或者給一個過程名賦值；或者調用函數(shù)時參數(shù)類型不適宜或者參加運算的兩個變量類型不匹配等等。比方下邊的程序片段：

intarr[2],c;

c=arr1*10;其中的賦值語句是符合語法規(guī)那么的，但是因為沒有聲明變量arr1，而存在語義錯。(3)語義分析及中間代碼生成51中間代碼生成(可選〕所謂“中間代碼〞是一種構造簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設計為多種多樣的形式，重要的設計原那么為兩點：一是容易生成；二是容易將它翻譯成目標代碼。中間代碼的形式： 四元式、三元式、逆波蘭表示中間代碼生成(可選〕52中間代碼(intermediateCode)例:sum=(10+20)*(num+square);后綴表示(逆波蘭Anti-PolishNotation)sum1020+numsquare+*=前綴表示(波蘭PolishNotation)=sum*+1020+numsquare

四元式表示(三地址碼)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3，，sum)

三元式表示(+，10，20)(+，num，square)(*，⑴，⑵)(=，sum，⑶)

語法樹中間代碼(intermediateCode)后綴表示(逆波53(4)中間代碼優(yōu)化(可選〕代碼優(yōu)化階段的任務是對前階段產生的中間代碼進展變換或進展改造，目的是使生成的目標代碼更為高效，即省時間和省空間。(4)中間代碼優(yōu)化(可選〕54例：sum=(10+20)*(num+square)得到的四元式T1=10+20T2=num+squareT3=T1*T2sum=T3優(yōu)化后T1=num+squareSum=30*T1例：sum=(10+20)*(num+square)得到55這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削弱、循環(huán)優(yōu)化等優(yōu)化工作將在后面的章節(jié)詳細介紹。代碼優(yōu)化工作會降低編譯程序的編譯速度，因此編譯優(yōu)化階段常常作為可選擇階段，編譯程序具有控制機制以允許用戶在編譯速度和目標代碼的質量間進展權衡。這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削56思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？57(5)目標代碼生成目標代碼生成階段的任務是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)構造和指令含義有關，這個階段的工作很復雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據類型變量的存儲空間分配以及存放器和后緩存放器的調度等。涉及到的兩個重要問題：對程序中使用的每個變量要指定存儲單元對變量進展存放器分配(5)目標代碼生成58例：sum=(10+20)*(num+square)得到的優(yōu)化后四元式T1=num+squareSum=30*T1生成如下指令序列：MOVnum,R1MOVsquare,R2ADDR2,R1MUL30,R1MOVR1,sum例：sum=(10+20)*(num+square)得到59目標代碼可采用如下三種形式之一：(1)具有絕對地址的機器指令代碼。(2)匯編語言形式的目標程序。需要經過匯編程序匯編，以產生機器代碼。(3)可重定位的指令代碼。多數(shù)編譯程序所產生的目標代碼都是這種類型。目標代碼可采用如下三種形式之一：60語句sum=(10+20)*(num+square);的翻譯過程語句sum=(10+20)*(num+square);的翻譯61編譯過程小結目標代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序S.PO.P編譯過程小結目標代碼代碼優(yōu)化語義分析語法分析詞法分析S.PO62上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的編譯程序都包括這樣幾個階段。有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；有些編譯程序不進展優(yōu)化，優(yōu)化階段即可省去;有些最簡單的編譯程序只有詞法分析，語法分析；語義分析和目標代碼生成。上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的631.3編譯程序的邏輯構造按邏輯功能不同，可將編譯過程劃分為五個根本階段，與此相對應，我們將實現(xiàn)整個編譯過程的編譯程序劃分為五個邏輯階段〔即五個邏輯子過程〕。每個階段中都要有：符號表管理和錯誤處理1.3編譯程序的邏輯構造按邏輯功能不同，可將編譯過程64典型的編譯程序具有7個邏輯局部語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯誤處理符號表管理典型的編譯程序具有7個邏輯局部語義分析及生成中間代碼程序代碼65<1>詞法分析：識別單詞，至少分以下幾大類：關鍵字〔保存字〕、標識符、字面量、特殊符號；<2>語法分析：得到語言構造并以樹的形式表示<3>語義分析：考察構造正確的句子是否語義合法，可修改樹構造；<4>中間代碼生成〔可選〕：生成一種既接近目標語言，又與具體機器無關的表示，便于優(yōu)化與代碼生成；〔到目前為止，編譯器與解釋器可以一致〕<1>詞法分析：識別單詞，至少分以下幾大類：關鍵字〔保存字66<5>中間代碼優(yōu)化〔可選〕：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時間上都更省、更有效。<6>目標代碼生成：不同形式的目標代碼－匯編、可重定位、絕對機器指令;<7>符號表管理：合理組織符號，便于各階段查找、填寫等；<8>出錯處理：錯誤的種類－詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。<5>中間代碼優(yōu)化〔可選〕：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化67符號表管理編譯程序的一項重要工作：記錄源程序中使用的標識符收集每個標識符的各種屬性信息符號表是由假設干記錄組成的數(shù)據構造每個標識符在表中有一條記錄記錄的域是標識符的屬性對符號表構造的要求：應允許快速地找到標識符的記錄可在其中存取數(shù)據標識符的各種屬性是在編譯的各個不同階段填入符號表的。符號表管理編譯程序的一項重要工作：68聲明語句：floattotal,rate;詞法分析器：float是關鍵字total、rate是標識符在符號表中創(chuàng)立這兩個標識符的記錄語義分析器：total、rate都表示變量float表示這兩個變量的類型可以把這兩種屬性及存儲分配信息填入符號表。在語義分析和生成中間代碼時，還要在符號表中填入對這個float型變量進展存儲分配的信息。聲明語句：floattotal,rate;詞法分析器：69錯誤處理在編譯的每個階段都可能檢測到源程序中存在的錯誤詞法分析程序可以檢測出非法字符錯誤。語法分析程序能夠發(fā)現(xiàn)記號流不符合語法規(guī)那么的錯誤。語義分析程序試圖檢測出具有正確的語法構造，但對所涉及的操作無意義的構造。代碼生成程序可能發(fā)現(xiàn)目標程序區(qū)超出了允許范圍的錯誤。處理與恢復判斷位置和性質適當?shù)幕謴统鲥e處理能力的優(yōu)劣是衡量編譯程序質量好壞的一個重要指標。錯誤處理在編譯的每個階段都可能檢測到源程序中存在的錯誤70編譯有關的其他概念“遍〞前端和后端編譯有關的其他概念“遍〞71編譯器掃描的遍數(shù)遍〔趟〕：是對源程序或源程序的中間結果從頭到尾掃描一遍，并作有關加工處理，生成新的中間結果或目標程序。例如：詞法分析器對輸入源程序進展第一遍掃描，語法分析進展第二遍掃描但一個階段對應一遍掃描的工作方式是邏輯上的，由于屢次掃描的方式需要大量的存儲空間存放中間表示，并且會增加一些不必要的輸入輸出操作，因此編譯器往往把假設干個階段的工作結合起來，對應一遍掃描，從而減少對程序的掃描遍數(shù)。編譯器掃描的遍數(shù)遍〔趟〕：是對源程序或源程序的中間結果從頭到72一個編譯程序應分成幾遍，如何劃分，是與源程序、設計要求、硬件設備等諸因素有關的，因地難于統(tǒng)一劃定。在主存可能的前提下，一般遍數(shù)盡可能少一點為好。但并不是每種語言都可以用單遍編譯程序實現(xiàn)。一個編譯程序應分成幾遍，如何劃分，是與源程序、設計要求、硬件73一遍掃描的編譯程序語法分析器取記號詞法分析器源程序記號語法成分語義分析及代碼生成目標程序返回控制流信息流開場完畢整理目標程序一遍掃描的編譯程序語法分析器取記號詞法分析器源程序記號語法成74多遍編譯程序多遍編譯程序75編譯階段的組合在前面所討論的編譯過程中階段的劃分是編譯程序的邏輯組織。有時，常常把編譯的過程分為前端(frontend)和后端(backend)，前端的工作主要依賴于源語言而與目標機無關,后端工作依賴于目標機而一般不依賴源語言。編譯階段的組合在前面所討論的編譯過程中階段的劃分是編譯程序的76根據編譯程序各局部功能，將編譯程序分成前端和后端前端：通常將與源程序有關的編譯局部稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成 ---分析局部特點：與源語言有關后端：與目標機有關的局部稱為后端。代碼優(yōu)化、代碼生成---綜合局部特點：與目標機有關編譯程序的前端和后端根據編譯程序各局部功能，將編譯程序分成前端和后端前端：通77編譯階段的組合編譯階段的組合78為什么生成中間代碼為什么生成中間代碼79.javajava源程序文件.class二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯同一前端+不同后端不同機器構成同一語言的編譯程序例如Java語言.javajava源程序文件.class二進制80

不同前端+同一后端同一機器生成幾個語言的編譯程序例如GCC編譯程序集合不同前端+同一后端同一機器生成幾個語言的編譯程序例81編譯程序中的主要數(shù)據構造(續(xù))Token表符號表常數(shù)表錯誤信息語法樹中間代碼表臨時文件目標代碼表編譯程序中的主要數(shù)據構造(續(xù))Token表語法樹中間代碼表8212/9/2022第83頁1.4編譯程序的設計構造編譯程序要掌握以下幾方面的內容：源語言：理解其構造和含義目標語言：必須清楚硬件的系統(tǒng)構造和指令的格式等編譯方法12/9/2022第83頁1.4編譯程序的設計構造編譯程序8312/9/2022第84頁1.4編譯程序的設計一般實現(xiàn)編譯程序的方法有：注：編譯程序核心局部常用匯編語言編寫注：這是普遍采用的方法5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產生LALR分析表)6.移植〔同種語言的編譯程序在不同類型的機器之間移植〕12/9/2022第84頁1.4編譯程序的設計一般實現(xiàn)編譯841.4編譯程序的生成早期人們用匯編語言編寫編譯程序，但其效率低，實現(xiàn)困難，比方FORTRAN語言編譯器18年才完成。專門的編譯編譯工具，可以支持編譯程序某些局部的自動生成。比方：LEX和YACC等。1.4編譯程序的生成早期人們用匯編語言編寫編譯程序，但其85說到一個編譯程序，一定要知道它的源語言是什麼，目標語言是什麼，還有它的實現(xiàn)語言是什麼。常使用T型圖來表示一個編譯程序所涉及的三個語言。

S：源語言O：目標語言T：編譯程序實現(xiàn)語言SOT說到一個編譯程序，一定要知道它的源語言是什麼，目標語言是什86開發(fā)編譯程序的途徑:自展法工具法自動生成法移植法開發(fā)編譯程序的途徑:87自展法自展法88利用A機器上已有的用A代碼編寫的L1語言的編譯程序，把用L1語言編寫的L2語言的編譯程序進展編譯，得到A機器代碼實現(xiàn)的L2語言的編譯程序。表示為：L2語言A代碼L1語言L1語言A代碼A代碼L2語言A代碼A代碼利用A機器上已有的用A代碼編寫的L1語言的編譯程序，把用L189或者表示為：L2語言A代碼L1語言L1語言A代碼A代碼L2語言A代碼A代碼或者表示為：L2語言A代碼L1語言L1語言A代碼A代碼L2語90問題一：如何直接在一個機器上實現(xiàn)C語言編譯器？解決：用匯編語言實現(xiàn)一個Ｃ子集的編譯程序(P0—人)用匯編程序處理該程序,得到(P2:可直接運行)用Ｃ子集編制Ｃ語言的編譯程序(P3—人)用P2編譯P3，得到P4自展問題一：如何直接在一個機器上實現(xiàn)C語言編譯器？自展914.用P2編譯P3，得到P4Ｃ語言機器語言機器語言P4Ｃ子集機器語言機器語言P2獲得一個工具Ｃ子集匯編語言機器語言P01.用匯編語言實現(xiàn)一個Ｃ子集的編譯程序(P0—人)匯編語言機器語言機器語言Ｃ子集機器語言機器語言P1P22.用匯編程序(P1)處理該程序,得到(P2:可直接運行)Ｃ語言Ｃ子集機器語言P33.用Ｃ子集編制Ｃ語言的編譯程序(P3—人)4.用P2編譯P3，得到P4Ｃ語言機器語言機器語言P4Ｃ子92移植問題二：A機上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)B機上的C語言編譯器？條件：Ａ機有Ｃ語言的編譯程序目的：實現(xiàn)Ｂ機的Ｃ語言的編譯Ｃ語言A機器A機器Ｃ語言B機器Ｂ機器要完成的任務移植問題二：A機上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)93Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器Ｂ機器Ｃ語言Ｂ機器Ｂ機器Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器A機器Ｃ語言A機器Ｂ機器需要編寫的程序1)問題的分析Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器Ｂ機器Ｃ語言Ｂ機器Ｂ機器Ｃ語言941.(人)用Ｃ語言編制B機的Ｃ編譯程序P0(C→B)(Ａ機的C編譯P1)編譯P0，得到在A機上可運行的P2(C→B)Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器A機器Ｃ語言A機器Ｂ機器P0P1P2獲得一個工具2)問題的解決方法1.(人)用Ｃ語言編制B機的Ｃ編譯程序P0(C→B)Ｃ語言953.(Ａ機的P2)編譯P0，得到在B機上可運行的P3(C→B)P2Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器Ｂ機器Ｃ語言Ｂ機器Ｂ機器P0P3Ｃ語言Ｃ語言Ｂ機器Ｃ語言Ａ機器A機器Ｃ語言A機器Ｂ機器P0P1P2獲得的工具3.(Ａ機的P2)編譯P0，得到在B機上可運行的P3(C→B96編譯程序移植：用A機器上的L語言編寫能在機器B上運行的L語言的編譯程序先用L語言編寫出在A機器上運行的產生B機器代碼的L編譯程序源程序，然后把該程序經過A機器上的L編譯程序編譯后得到能在A機器上運行的產生B機器代碼的編譯程序，用這個編譯程序再一次編譯上述源程序。

編譯程序移植：用A機器上的L語言編寫能在機器B上運行的L語言97LBLLBLLAALBALBBLBLLBLLAALBALBB98LBLLAALBALBLLBALBBLBLLAALBALBLLBALBB99本機編譯器的利用問題三：A機上有一個C語言編譯器，現(xiàn)要實現(xiàn)一個新語言NEW的編譯器？能利用穿插編譯技術么？用C編寫NEW的編譯，并用C編譯器編譯它NEW語言Ｃ語言A機器Ｃ語言Ａ機器A機器NEW語言A機器A機器P0P1P2本機編譯器的利用問題三：A機上有一個C語言編譯器，現(xiàn)要實現(xiàn)1001.5編譯技術的應用及開展應用：大局部軟件工具的開發(fā)，都要使用編譯技術和方法語法制導的構造化編輯器Turbo-Edit、editplus和Ultraedit等程序格式化工具軟件測試工具靜態(tài)分析器：不可能執(zhí)行的代碼、定義后未引用的變量動態(tài)測試工具：運行后與期望結果比較程序理解工具：確定調用關系，畫出流程圖高級語言的翻譯工具1.5編譯技術的應用及開展應用：大局部軟件工具的開發(fā)，都101語法制導的構造化編輯器具有通常的正文編輯和修改功能能象編譯程序那樣對源程序進展分析，把恰當?shù)膶哟螛嬙旒釉诔绦蛏稀？梢员ＷC源程序無語法錯誤有統(tǒng)一的可讀性好的程序格式構造化編輯器能夠執(zhí)行一些對編制源程序有用的附加任務，如：檢查用戶的輸入是否正確自動提供關鍵字從BEGIN或左括號跳到與其相匹配的END或右括號語法制導的構造化編輯器具有通常的正文編輯和修改功能102程序格式化工具讀入并分析源程序使程序構造變得清晰可讀，如：用縮排方式表示語句的嵌套層次構造用一種專門的字型表示注釋等程序格式化工具讀入并分析源程序103軟件測試工具靜態(tài)測試動態(tài)測試——動態(tài)測試器——靜態(tài)測試器讀入源程序在不運行該程序的情況下對其進展分析，以發(fā)現(xiàn)程序中潛在的錯誤或異常。不可能執(zhí)行到的死代碼未定義就引用的變量試圖使用一個實型變量作為指針等。利用測試用例實際執(zhí)行程序記錄程序的實際執(zhí)行路線將實際運行結果與期望結果進展比較，以發(fā)現(xiàn)程序中的錯誤或異常。軟件測試工具靜態(tài)測試——動態(tài)測試器——靜態(tài)測試器讀入源程序利104程序理解工具對源程序進展分析確定各模塊間的調用關系記錄程序數(shù)據的靜態(tài)屬性和構造屬性畫出控制流程圖程序理解工具對源程序進展分析105練習1、判斷正誤(1)編譯程序的五個組成局部缺一不可。(2)高級語言程序到低級語言程序的轉換是基于語義的等價變換。(3)含有優(yōu)化局部的編譯程序的執(zhí)行效率高。(4)因為編譯程序和解釋程序具有不同的功能，所以他們的實現(xiàn)技術也完全不同。(5)編譯程序和解釋程序的根本區(qū)別在于解釋程序對源程序并沒有真正的進展翻譯。(6)無論一遍掃描的編譯器還是多遍掃描的編譯器都要對源程序掃描一遍。練習1、判斷正誤106練習2、對以下錯誤信息，請指出可能是編譯的哪個階段〔詞法分析、語法分析、語義分析、代碼生成〕報告的?！?〕else沒有匹配的if〔2〕數(shù)組下標越界〔3〕使用的函數(shù)沒有定義〔4〕在數(shù)中出現(xiàn)非數(shù)字字符〔5〕零作除數(shù)練習2、對以下錯誤信息，請指出可能是編譯的哪個階段〔詞法分107 謝謝大家！ 謝謝大家！108ch編譯原理引論ch編譯原理引論ch編譯原理引論為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序設計者與計算機之間的根本界面。通過學習該課程，掌握編譯的根本理論、常用的編譯技術，了解編譯過程及編譯系統(tǒng)構造和機理。能運用所學技術解決實際問題，能獨立編寫一個小型編譯系統(tǒng)。此外，通過學習編譯原理可以更好地理解程序語言的內部機制,從而更好地理解和運用程序設計語言。能運用編譯程序構造的原理和技術完成相關軟件工具的設計和開發(fā)工作。ch編譯原理引論ch編譯原理引論ch編譯原理引論為什么要學習109為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序設計者與計算機之間的根本界面。通過學習該課程，掌握編譯的根本理論、常用的編譯技術，了解編譯過程及編譯系統(tǒng)構造和機理。能運用所學技術解決實際問題，能獨立編寫一個小型編譯系統(tǒng)。此外，通過學習編譯原理可以更好地理解程序語言的內部機制,從而更好地理解和運用程序設計語言。能運用編譯程序構造的原理和技術完成相關軟件工具的設計和開發(fā)工作。為什么要學習編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構成程序110課程內容介紹編譯器構造的一般原理和根本實現(xiàn)方法介紹的理論知識：形式語言和自動機理論、語法制導的定義和屬性文法、類型論等強調形式描述技術和自動生成技術課程簡介先行課程高等數(shù)學、Ｃ、離散數(shù)學、匯編語言、數(shù)據構造課程內容課程簡介先行課程111參考資料國外編譯原理領域內的3本權威書籍：當代編譯技術三大圣經！1、龍書〔Dragonbook〕參考資料國外編譯原理領域內的3本權威書籍：當代編譯技術三大1122、鯨書〔Whalebook〕

2、鯨書〔Whalebook〕

1133、虎書〔Tigerbook〕3、虎書〔Tigerbook〕114國內編譯原理領域內的權威書籍：1.陳意云?編譯原理?高等教育出版社ch編譯原理引論課件1152.呂映芝?編譯原理?清華大學教育出版社；ch編譯原理引論課件1163.陳英?編譯原理?清華工大學出版社3.陳英?編譯原理?清華工大學出版社1174.蔣宗禮?編譯原理?高等教育出版社ch編譯原理引論課件1185.劉磊?編譯原理及實現(xiàn)?機械工業(yè)出版社ch編譯原理引論課件119要求及學習方法課程特點：理論性強，算法復雜平時〔20%〕無故曠課：－5一本教材，認真聽課：以講義為主，做適當?shù)墓P記認真完成課堂和課后作業(yè)期末〔80%〕:閉卷筆試要求及學習方法課程特點：理論性強，算法復雜120第一章編譯概述掌握編譯程序中所涉及的有關名詞術語2.理解編譯程序總的框架，明確編譯程序工作的根本過程及各階段的根本任務教學目標第一章編譯概述掌握編譯程序中所涉及的有關名詞術語教學目1211.2.編譯的過程1.3.編譯程序的邏輯構造1.4.編譯程序的生成1.5.編譯技術的應用及開展教學內容教學內容122

程序的翻譯語言和翻譯：語言是人類交流思想和信息的工具。如自然語言，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。計算機語言同樣是豐富多彩的。程序的翻譯語言和翻譯：語言是人類交流思想和信息的工具。如12312/9/2022第124頁機器語言(machinelanguage)C70600000002匯編語言(assemblerlanguage)

MOVX,2高級語言(high-levellanguage)

X=2為什么要使用編譯程序？12/9/2022第16頁機器語言(machinelan124程序語言的分類低級語言〔LowlevelLanguage)機器語言、匯編語言特點：與特定的機器有關，成效高，但使用復雜、繁瑣、費時、易出錯。高級語言--Fortran、Pascal、C語言等特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護等。程序語言的分類低級語言〔LowlevelLanguage125計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外的另一種語言呢？？解決這一問題的方法：翻譯程序??！計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外126翻譯程序翻譯程序：能夠把某一種語言程序〔稱為源語言程序〕轉換成另一種語言程序〔稱為目標語言程序〕的一個程序，而后者與前者在邏輯上是等價的。程序翻譯的方式通常有兩種，一種是編譯方式，另一種是解釋方式。源程序翻譯程序目標程序翻譯程序翻譯程序：能夠把某一種語言程序〔稱為源語言程序〕轉換127編譯程序編譯程序：如果一個翻譯程序的源語言是某種高級語言，其目標語言是相對于某一計算機的匯編語言或機器語言，那么稱這種翻譯程序為編譯程序〔或稱為編譯器〕。假設編譯生成的目標程序不是機器代碼，而是匯編語言程序，那么還要增加一個會變程序將其會變?yōu)闄C器代碼。源程序（高級語言編寫）編譯程序目標程序（機器語言或匯編語言編寫）編譯程序編譯程序：如果一個翻譯程序的源語言是某種高級語言，其128匯編程序如果一個翻譯程序的源語言是某種匯編語言，其目標語言是某一計算機的機器語言，那么稱這種翻譯程序為匯編程序。源程序（匯編語言編寫）匯編程序目標程序（機器語言編寫）匯編程序如果一個翻譯程序的源語言是某種匯編語言，其目標語言是129解釋程序解釋程序:是一種語言處理程序，它以源程序作為輸入，但不產生目標代碼，它將源程序中的語句按動態(tài)順序，逐句翻譯成課執(zhí)行代碼，一旦具備執(zhí)行條件，那么立即執(zhí)行這一階段代碼得到局部結果。源程序（高級語言編寫）解釋程序計算結果特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、可移植性好，易于查錯，但速度慢解釋程序解釋程序:是一種語言處理程序，它以源程序作為輸入，130編譯和解釋程序編譯程序的工作相當于載翻譯一本原著，計算機運行編譯后的目標程序，相當于閱讀一本譯著；而解釋程序的工作相當于在進展同聲翻譯，計算機運行解釋程序，相當于我們直接通過翻譯聽外賓講話。編譯和解釋程序131程序的編譯執(zhí)行：輸入數(shù)據源程序編譯程序運行系統(tǒng)目標程序輸入數(shù)據源程序編譯程序運行系統(tǒng)目標程序132程序的解釋執(zhí)行：如：BASIC、Prolog，問題：效率低下解釋程序源程序輸入數(shù)據計算結果為什么解釋運行的工作效率低于編譯方式？？程序的解釋執(zhí)行：解釋程序源程序輸入數(shù)據計算結果為什么解釋運行133編譯程序與解釋程序的差異根本區(qū)別：是否生成目標代碼！功能工作結果實現(xiàn)技術上解釋程序源程序的一個執(zhí)行系統(tǒng)源程序的執(zhí)行結果執(zhí)行中間代碼編譯程序源程序的一個轉換系統(tǒng)源程序的目標代碼把中間代碼轉換成目標程序編譯程序與解釋程序的差異根本區(qū)別：是否生成目標代碼！功能工作134“編譯+解釋執(zhí)行〞系統(tǒng)源程序編譯程序源程序的中間形式輸出數(shù)據解釋程序輸入數(shù)據“編譯+解釋執(zhí)行〞系統(tǒng)源程序編譯程序源程序的中間形式輸出數(shù)據135例如Java語言.java

java源程序文件.class二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯例如Java語言.javajava源程序文件.cl136編譯程序在計算機系統(tǒng)中的位置編譯程序是一種軟件，是系統(tǒng)軟件。通常認為系統(tǒng)軟件是居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。編譯程序在計算機系統(tǒng)中的位置編譯程序是一種軟件，是系統(tǒng)軟件。137翻譯程序所處的層次高級語言語言處理程序操作系統(tǒng)匯編語言計算機硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言............翻譯程序所處的層次高語言處理程序操作系統(tǒng)計算機硬件CCBas138幾個概念宿主機：運行編譯程序的計算機目標機：運行編譯程序所產生的目標代碼的計算機穿插編譯程序：一個編譯程序產生不同于其宿主機的機器代碼可變目標編譯程序：不需要重寫編譯程序中與機器無關的局部就能改變目標機幾個概念宿主機：運行編譯程序的計算機139對編譯程序的一些說明編譯程序實質上是一個翻譯程序，要注意等價變換本課程的任務就是講解在這個轉換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器轉換是一個總體的功能，要抓住總體構造，逐層細分，寫編譯器時要表達軟件工程中軟件設計的原那么，自頂向下，逐層分解。編譯器要完成的轉換任務相當復雜，實現(xiàn)編譯器時必須分步驟分階段實現(xiàn)。分階段實現(xiàn)的好處是能夠簡化程序的設計，當然也可以不分階段實現(xiàn)。對編譯程序的一些說明編譯程序實質上是一個翻譯程序，要注意等價140編譯原理是討論編譯程序設計的根本理論、根本概念、根本方法什么是編譯原理編譯原理是討論編譯程序設計的根本理論、根本概念14112/9/2022142編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序，把高級語言經分析翻譯為低級語言。集成開發(fā)環(huán)境：簡稱IDE〔IntegratedDevelopEnvironment〕，是用于提供程序開發(fā)環(huán)境的應用程序，一般包括代碼編輯器、編譯器、調試器和圖形用戶界面工具。背景：早期程序設計的各個階段都要用不同的軟件來進展處理,如先用字處理軟件編輯源程序，再用編譯程序進展編譯，然后用鏈接程序進展函數(shù)、模塊連接,開發(fā)者必須在幾種軟件間來回切換操作。人們習慣上經常把IDE稱為編譯器。12/9/202234編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序142編譯原理引論143常見語言及其IDE語言IDECTC2.0C++C++Builder,VC++6.0,TC3.0C#VS.NETPascalTurboPascalOOPascalDelphiVBVB6.0(解釋器)JavaEclipse,JBuilder編譯原理引論35常見語言及其IDE語言IDECTC2.0C+1431.2編譯的過程1.編譯程序的工作過程1.2編譯的過程1.編譯程序的工作過程144編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。將英文句子“Iwishyousuccess翻譯成中文。兩階段完成翻譯

分析：分析單詞：I，wish，you，success分析語法：主語，謂語，賓語，賓補分析語義：我希望你成功

綜合：綜合英語的意思、上下文環(huán)境和漢語的表達習慣，完成翻譯：祝你成功編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。145翻譯外文資料：1、能識別出句子中的一個單詞；2、分析句子的語法構造；3、根據句子的含義進展初步翻譯；4、對譯文進展修飾；5、寫出最后的譯文。翻譯外文資料：146翻譯外文資料與編譯源程序進展類比翻譯外文編譯程序分析識別單詞分析句子根據語義進行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標代碼生成翻譯外文資料與編譯源程序進展類比翻譯外文編譯程序識別單詞詞法147將編譯過程劃分為5個根本階段詞法分析語法分析語義分析及中間代碼生成代碼優(yōu)化目標代碼生成將編譯過程劃分為5個根本階段詞法分析語法分析語義分析及中間代148從概念上來講，一個編譯程序的整個工作過程是劃分成階段進展的，每個階段將源程序的一種表示形式轉換成另一種表示形式，各個階段進展的操作在邏輯上是嚴密連接在一起的。事實上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構造出來了。從概念上來講，一個編譯程序的整個工作過程是劃分成階段進展的，1491.2編譯的過程1.編譯程序的工作過程1.2編譯的過程1.編譯程序的工作過程150(1)詞法分析詞法分析階段是編譯過程的第一個階段。這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構成源程序的字符流進展掃描和分解，根據語言的詞法規(guī)那么識別出一個個具有獨立意義的最小語法單位，即單詞。(1)詞法分析151根據詞法規(guī)那么分析和識別單詞。把需要存放的單詞放到符號表中，如變量名，標號，常量等。工作依據:源語言的構詞規(guī)那么(即詞法)，也稱為模式(pattern)。標識符的模式是：以字母開頭的字母數(shù)字序列。根據詞法規(guī)那么分析和識別單詞。152例：sum=(10+20)*(num+square);結果(標識符，sum)(賦值號，=)(左括號，()(整常數(shù)，10)(加號，+)(整常數(shù)，20)(右括號，))(乘號，*)(左括號，()(標識符，num)(加號，+)(標識符，square)(右括號，))(分號，;)例：結果153詞法分析的功能如下：識別出源程序中意義獨立的最小詞法單位—單詞。刪除無用的空格、回車和其他與輸入介質有關的符號刪除程序員為了提高程序可讀性所加的注釋如果發(fā)現(xiàn)錯誤那么報告出錯詞法分析的功能如下：154(2)語法分析根據語法規(guī)那么〔即語言的文法〕，分析并識別出各種語法成分〔如表達式、語句、函數(shù)等〕，并進展語法正確性檢查。通常將語法分析的結果表示為語法樹。(2)語法分析155sum=(10+20)*(num+square);sum=(10+20)*(num+square);156語法分析的功能是進展層次分析，把源程序的單詞序列組成語法短語(表示成語法樹)。依據的是語法規(guī)那么。C語言的賦值語句的規(guī)那么為：

單詞序列sum=(10+20)*(num+square);之所以能表示成上圖的語法樹，依據的是賦值語句和表達式的語法規(guī)那么。

<賦值語句>::=<標識符>“=〞<表達式><表達式>::=<表達式>“+〞<表達式>|<表達式>“*〞<表達式><表達式>::=“(〞<表達式>“)〞|<標識符>|<整數(shù)>|<實數(shù)>語法分析的功能是進展層次分析，把源程序的單詞序列組成語法短157(3)語義分析及中間代碼生成語義分析階段的任務是審查源程序有無語義錯誤。工作依據：源語言的語義規(guī)那么一個重要任務：類型檢查根據規(guī)那么檢查每個運算符及其運算對象是否符合要求；數(shù)組的下標是否合法；過程調用時，形參與實參個數(shù)、類型是否匹配等(3)語義分析及中間代碼生成158(3)語義分析及中間代碼生成源程序中有些語法成分，按照語法規(guī)那么去判斷，它是正確的，但它不符合語義規(guī)那么。比方使用了沒有聲明的變量；或者給一個過程名賦值；或者調用函數(shù)時參數(shù)類型不適宜或者參加運算的兩個變量類型不匹配等等。比方下邊的程序片段：

intarr[2],c;

c=arr1*10;其中的賦值語句是符合語法規(guī)那么的，但是因為沒有聲明變量arr1，而存在語義錯。(3)語義分析及中間代碼生成159中間代碼生成(可選〕所謂“中間代碼〞是一種構造簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設計為多種多樣的形式，重要的設計原那么為兩點：一是容易生成；二是容易將它翻譯成目標代碼。中間代碼的形式： 四元式、三元式、逆波蘭表示中間代碼生成(可選〕160中間代碼(intermediateCode)例:sum=(10+20)*(num+square);后綴表示(逆波蘭Anti-PolishNotation)sum1020+numsquare+*=前綴表示(波蘭PolishNotation)=sum*+1020+numsquare

四元式表示(三地址碼)(+，10，20，T1)(+，num，square，T2)(*，T1，T2，T3)(=，T3，，sum)

三元式表示(+，10，20)(+，num，square)(*，⑴，⑵)(=，sum，⑶)

語法樹中間代碼(intermediateCode)后綴表示(逆波161(4)中間代碼優(yōu)化(可選〕代碼優(yōu)化階段的任務是對前階段產生的中間代碼進展變換或進展改造，目的是使生成的目標代碼更為高效，即省時間和省空間。(4)中間代碼優(yōu)化(可選〕162例：sum=(10+20)*(num+square)得到的四元式T1=10+20T2=num+squareT3=T1*T2sum=T3優(yōu)化后T1=num+squareSum=30*T1例：sum=(10+20)*(num+square)得到163這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削弱、循環(huán)優(yōu)化等優(yōu)化工作將在后面的章節(jié)詳細介紹。代碼優(yōu)化工作會降低編譯程序的編譯速度，因此編譯優(yōu)化階段常常作為可選擇階段，編譯程序具有控制機制以允許用戶在編譯速度和目標代碼的質量間進展權衡。這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削164思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？165(5)目標代碼生成目標代碼生成階段的任務是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)構造和指令含義有關，這個階段的工作很復雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據類型變量的存儲空間分配以及存放器和后緩存放器的調度等。涉及到的兩個重要問題：對程序中使用的每個變量要指定存儲單元對變量進展存放器分配(5)目標代碼生成166例：sum=(10+20)*(num+square)得到的優(yōu)化后四元式T1=num+squareSum=30*T1生成如下指令序列：MOVnum,R1MOVsquare,R2ADDR2,R1MUL30,R1MOVR1,sum例：sum=(10+20)*(num+square)得到167目標代碼可采用如下三種形式之一：(1)具有絕對地址的機器指令代碼。(2)匯編語言形式的目標程序。需要經過匯編程序匯編，以產生機器代碼。(3)可重定位的指令代碼。多數(shù)編譯程序所產生的目標代碼都是這種類型。目標代碼可采用如下三種形式之一：168語句sum=(10+20)*(num+square);的翻譯過程語句sum=(10+20)*(num+square);的翻譯169編譯過程小結目標代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序S.PO.P編譯過程小結目標代碼代碼優(yōu)化語義分析語法分析詞法分析S.PO170上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的編譯程序都包括這樣幾個階段。有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；有些編譯程序不進展優(yōu)化，優(yōu)化階段即可省去;有些最簡單的編譯程序只有詞法分析，語法分析；語義分析和目標代碼生成。上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的1711.3編譯程序的邏輯構造按邏輯功能不同，可將編譯過程劃分為五個根本階段，與此相對應，我們將實現(xiàn)整個編譯過程的編譯程序劃分為五個邏輯階段〔即五個邏輯子過程〕。每個階段中都要有：符號表管理和錯誤處理1.3編譯程序的邏輯構造按邏輯功能不同，可將編譯過程172典型的編譯程序具有7個邏輯局部語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯誤處理符號表管理典型的編譯程序具有7個邏輯局部語義分析及生成中間代碼程序代碼173<1>詞法分析：識別單詞，至少分以下幾大類：關鍵字〔保存字〕、標識符、字面量、特殊符號；<2>語法分析：得到語言構造并以樹的形式表示<3>語義分析：考察構造正確的句子是否語義合法，可修改樹構造；<4>中間代碼生成〔可選〕：生成一種既接近目標語言，又與具體機器無關的表示，便于優(yōu)化與代碼生成；〔到目前為止，編譯器與解釋器可以一致〕<1>詞法分析：識別單詞，至少分以下幾大類：關鍵字〔保存字174<5>中間代碼優(yōu)化〔可選〕：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時間上都更省、更有效。<6>目標代碼生成：不同形式的目標代碼－匯編、可重定位、絕對機器指令;<7>符號表管理：合理組織符號，便于各階段查找、填寫等；<8>出錯處理：錯誤的種類－詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。<5>中間代碼優(yōu)化〔可選〕：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化175符號表管理編譯程序的一項重要工作：記錄源程序中使用的標識符收集每個標識符的各種屬性信息符號表是由假設干記錄組成的數(shù)據構造每個標識符在表中有一條記錄記錄的域是標識符的屬性對符號表構造的要求：應允許快速地找到標識符的記錄可在其中存取數(shù)據標識符的各種屬性是在編譯的各個不同階段填入符號表的。符號表管理編譯程序的一項重要工作：176聲明語句：floattotal,rate;詞法分析器：float是關鍵字total、rate是標識符在符號表中創(chuàng)立這兩個標識符的記錄語義分析器：total、rate都表示變量float表示這兩個變量的類型可以把這兩種屬性及存儲分配信息填入符號表。在語義分析和生成中間代碼時，還要在符號表中填入對這個float型變量進展存儲分配的信息。聲明語句：floattotal,rate;詞法分析器：177錯誤處理在編譯的每個階段都可能檢測到源程序中存在的錯誤詞法分析程序可以檢測出非法字符錯誤。語法分析程序能夠發(fā)現(xiàn)記號流不符合語法規(guī)那么的錯誤。語義分析程序試圖檢測出具有正確的語法構造，但對所涉及的操作無意義的構造。代碼生成程序可能發(fā)現(xiàn)目標程序區(qū)超出了允許范圍的錯誤。處理與恢復判斷位置和性質適當?shù)幕謴统鲥e處理能力的優(yōu)劣是衡量編譯程序質量好壞的一個重要指標。錯誤處理在編譯的每個階段都可能檢測到源程序中存在的錯誤178編譯有關的其他概念“遍〞前端和后端編譯有關的其他概念“遍〞179編譯器掃描的遍數(shù)遍〔趟〕：是對源程序或源程序的中間結果從頭到尾掃描一遍，并作有關加工處理，生成新的中間結果或目標程序。例如：詞法分析器對輸入源程序進展第一遍掃描，語法分析進展第二遍掃描但一個階段對應一遍掃描的工作方式是邏輯上的，由于屢次掃描的方式需要大量的存儲空間存放中間表示，并且會增加一些不必要的輸入輸出操作，因此編譯器往往把假設干個階段的工作結合起來，對應一遍掃描，從而減少對程序的掃描遍數(shù)。編譯器掃描的遍數(shù)遍〔趟〕：是對源程序或源程序的中間結果從頭到180一個編譯程序應分成幾遍，如何劃分，是與源程序、設計要求、硬件設備等諸因素有關的，因地難于統(tǒng)一劃定。在主存可能的前提下，一般遍數(shù)盡可能少一點為好。但并不是每種語言都可以用單遍編譯程序實現(xiàn)。一個編譯程序應分成幾遍，如何劃分，是與源程序、設計要求、硬件181一遍掃描的編譯程序語法分析器取記號詞法分析器源程序記號語法成分語義分析及代碼生成目標程序返回控制流信息流開場完畢整理目標程序一遍掃描的編譯程序語法分析器取記號詞法分析器源程序記號語法成182多遍編譯程序多遍編譯程序183編譯階段的組合在前面所討論的編譯過程中階段的劃分是編譯程序的邏輯組織。有時，常常把編譯的過程分為前端(frontend)和后端(backend)，前端的工作主要依賴于源語言而與目標機無關,后端工作依賴于目標機而一般不依賴源語言。編譯階段的組合在前面所討論的編譯過程中階段的劃分是編譯程序的184根據編譯程序各局部功能，將編譯程序分成前端和后端前端：通常將與源程序有關的編譯局部稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成 ---分析局部特點：與源語言有關后端：與目標機有關的局部稱為后端。代碼優(yōu)化、代碼生成---綜合局部特點：與目標機有關編譯程序的前端和后端根據編譯程序各局部功能，將編譯程序分成前端和后端前端：通185編譯階段的組合編譯階段的組合186為什么生成中間代碼為什么生成中間代碼187.javajava源程序文件.class二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯同一前端+不同后端不同機器構成同一語言的編譯程序例如Java語言.javajava源程序文件.class二進制188

不同前端+同一后端同一機器生成幾個語言的編譯程序例如GCC編譯程序集合不同前端+同一后端同一機器生成幾個語言的編譯程序例189編譯程序中的主要數(shù)據構造(續(xù))Token表符號表常數(shù)表錯誤信息語法樹中間代碼表臨時文件目標代碼表編譯程序中的主要數(shù)據構造(續(xù))Token表語法樹中間代碼表19012/9/2022第191頁1.4編譯程序的設計構造編譯程序要掌握以下幾方面的內容：源語言：理解其構造和含義目標語言：必須清楚硬件的系統(tǒng)構造和指令的格式等編譯方法12/9/2022第83頁1.4編譯程序的設計構造編譯程序19112/9/2022第192頁1.4編譯程序的設計一般實現(xiàn)編譯程序的方法有：注：編譯程序核心局部常用匯編語言編寫注：這是普遍采用的方法5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產生LALR分析表)6.移植〔同種語言的編譯程序在不同類型的機器之間移植〕12/9/2022第84頁1.4編譯程序的設計一般實現(xiàn)編譯1921.4編譯程序的生成早期人們用匯編語言編寫編譯程序，但其效率低，實現(xiàn)困難，比方FORTRAN語言編譯器18年才完成。專門的編譯編譯工具，可以支持編譯程序某些局部的自動生成。比方：LEX和YACC等。1.4編譯程序的生成早期人們用匯編語言編寫編譯程序，但其193說到一個編譯程序，一定要知道它的源語言是什麼，目標語言是什麼，還有它的實現(xiàn)語言是什麼。常使用T型圖來表示一個編譯程序所涉及的三個語言。

S：源語言O：目標語言T：編譯程序實現(xiàn)語言SOT說到一個編譯程序，一定要知道它的源語言是什麼，目標語言是什194開發(fā)編譯程序