ch1編譯原理引論全解

編譯原理計(jì)算機(jī)科學(xué)技術(shù)系李薇livaye@163為什么要學(xué)習(xí)編譯原理必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計(jì)者與計(jì)算機(jī)之間的基本界面。通過學(xué)習(xí)該課程，駕馭編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機(jī)理。能運(yùn)用所學(xué)技術(shù)解決實(shí)際問題，能獨(dú)立編寫一個(gè)小型編譯系統(tǒng)。此外，通過學(xué)習(xí)編譯原理可以更好地理解程序語言的內(nèi)部機(jī)制,從而更好地理解和運(yùn)用程序設(shè)計(jì)語言。能運(yùn)用編譯程序構(gòu)造的原理和技術(shù)完成相關(guān)軟件工具的設(shè)計(jì)和開發(fā)工作。課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法介紹的理論學(xué)問：形式語言和自動(dòng)機(jī)理論、語法制導(dǎo)的定義和屬性文法、類型論等強(qiáng)調(diào)形式描述技術(shù)和自動(dòng)生成技術(shù)課程簡(jiǎn)介先行課程

高等數(shù)學(xué)、Ｃ、離散數(shù)學(xué)、匯編語言、數(shù)據(jù)結(jié)構(gòu)參考資料國(guó)外編譯原理領(lǐng)域內(nèi)的3本權(quán)威書籍：當(dāng)代編譯技術(shù)三大圣經(jīng)！1、龍書（Dragonbook）2、鯨書（Whalebook）

3、虎書（Tigerbook）國(guó)內(nèi)編譯原理領(lǐng)域內(nèi)的權(quán)威書籍：1.陳意云《編譯原理》高等教化出版社2.呂映芝《編譯原理》清華高校教化出版社；3.陳英《編譯原理》清華工高校出版社4.蔣宗禮《編譯原理》高等教化出版社5.劉磊《編譯原理及實(shí)現(xiàn)》機(jī)械工業(yè)出版社

要求及學(xué)習(xí)方法課程特點(diǎn)：理論性強(qiáng)，算法困難平常（20%）無故曠課：－5一本教材，細(xì)致聽課：以講義為主，做適當(dāng)?shù)墓P記細(xì)致完成課堂和課后作業(yè)期末（80%）:閉卷筆試第一章編譯概述駕馭編譯程序中所涉及的有關(guān)名詞術(shù)語2.理解編譯程序總的框架，明確編譯程序工作的基本過程及各階段的基本任務(wù)教學(xué)目標(biāo)1.1.程序的翻譯1.2.編譯的過程1.3.編譯程序的邏輯結(jié)構(gòu)1.4.編譯程序的生成1.5.編譯技術(shù)的應(yīng)用及發(fā)展教學(xué)內(nèi)容1.1

程序的翻譯語言和翻譯：語言是人類溝通思想和信息的工具。如自然語言，世界上存在著很多種語言，各國(guó)之間要溝通信息,就要有各種語言之間的翻譯。計(jì)算機(jī)語言同樣是豐富多彩的。1/13/2023第16頁機(jī)器語言(machinelanguage)C70600000002匯編語言(assemblerlanguage)

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

X=2為什么要運(yùn)用編譯程序？程序語言的分類低級(jí)語言（LowlevelLanguage)機(jī)器語言、匯編語言特點(diǎn)：與特定的機(jī)器有關(guān)，功效高，但運(yùn)用困難、繁瑣、費(fèi)時(shí)、易出錯(cuò)。高級(jí)語言--Fortran、Pascal、C語言等特點(diǎn)：不依靠具體機(jī)器，移植性好、對(duì)用戶要求低、易運(yùn)用、易維護(hù)等。計(jì)算機(jī)硬件只懂自己的指令系統(tǒng)，那么它是如何識(shí)別除機(jī)器語言以外的另一種語言呢？？解決這一問題的方法：翻譯程序?。》g程序翻譯程序：能夠把某一種語言程序（稱為源語言程序）轉(zhuǎn)換成另一種語言程序（稱為目標(biāo)語言程序）的一個(gè)程序，而后者與前者在邏輯上是等價(jià)的。程序翻譯的方式通常有兩種，一種是編譯方式，另一種是說明方式。源程序翻譯程序目標(biāo)程序編譯程序編譯程序：假如一個(gè)翻譯程序的源語言是某種高級(jí)語言，其目標(biāo)語言是相對(duì)于某一計(jì)算機(jī)的匯編語言或機(jī)器語言，則稱這種翻譯程序?yàn)榫幾g程序（或稱為編譯器）。若編譯生成的目標(biāo)程序不是機(jī)器代碼，而是匯編語言程序，則還要增加一個(gè)會(huì)變程序?qū)⑵鋾?huì)變?yōu)闄C(jī)器代碼。源程序（高級(jí)語言編寫）編譯程序目標(biāo)程序（機(jī)器語言或匯編語言編寫）匯編程序假如一個(gè)翻譯程序的源語言是某種匯編語言，其目標(biāo)語言是某一計(jì)算機(jī)的機(jī)器語言，則稱這種翻譯程序?yàn)閰R編程序。源程序（匯編語言編寫）匯編程序目標(biāo)程序（機(jī)器語言編寫）說明程序說明程序:是一種語言處理程序，它以源程序作為輸入，但不產(chǎn)生目標(biāo)代碼，它將源程序中的語句按動(dòng)態(tài)依次，逐句翻譯成課執(zhí)行代碼，一旦具備執(zhí)行條件，則立刻執(zhí)行這一階段代碼得到部分結(jié)果。源程序（高級(jí)語言編寫）解釋程序計(jì)算結(jié)果特點(diǎn)：與編譯系統(tǒng)比較，說明系統(tǒng)較簡(jiǎn)潔、可移植性好，易于查錯(cuò)，但速度慢編譯和說明程序編譯程序的工作相當(dāng)于載翻譯一本原著，計(jì)算機(jī)運(yùn)行編譯后的目標(biāo)程序，相當(dāng)于閱讀一本譯著；而說明程序的工作相當(dāng)于在進(jìn)行同聲翻譯，計(jì)算機(jī)運(yùn)行說明程序，相當(dāng)于我們干脆通過翻譯聽外賓講話。程序的編譯執(zhí)行：輸入數(shù)據(jù)源程序編譯程序運(yùn)行系統(tǒng)目標(biāo)程序程序的說明執(zhí)行：如：BASIC、Prolog，問題：效率低下解釋程序源程序輸入數(shù)據(jù)計(jì)算結(jié)果為什么說明運(yùn)行的工作效率低于編譯方式？？編譯程序與說明程序的差別根本區(qū)分：是否生成目標(biāo)代碼！功能工作結(jié)果實(shí)現(xiàn)技術(shù)上解釋程序源程序的一個(gè)執(zhí)行系統(tǒng)源程序的執(zhí)行結(jié)果執(zhí)行中間代碼編譯程序源程序的一個(gè)轉(zhuǎn)換系統(tǒng)源程序的目標(biāo)代碼把中間代碼轉(zhuǎn)換成目標(biāo)程序“編譯+說明執(zhí)行”系統(tǒng)源程序編譯程序源程序的中間形式輸出數(shù)據(jù)解釋程序輸入數(shù)據(jù)例如Java語言.java

java源程序文件.class二進(jìn)制字節(jié)碼文件Java虛擬機(jī)（JVM)本地計(jì)算機(jī)系統(tǒng)編譯編譯程序在計(jì)算機(jī)系統(tǒng)中的位置編譯程序是一種軟件，是系統(tǒng)軟件。通常認(rèn)為系統(tǒng)軟件是居于計(jì)算機(jī)系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。翻譯程序所處的層次高級(jí)語言語言處理程序操作系統(tǒng)匯編語言計(jì)算機(jī)硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言............幾個(gè)概念宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)目標(biāo)機(jī)：運(yùn)行編譯程序所產(chǎn)生的目標(biāo)代碼的計(jì)算機(jī)交叉編譯程序：一個(gè)編譯程序產(chǎn)生不同于其宿主機(jī)的機(jī)器代碼可變目標(biāo)編譯程序：不須要重寫編譯程序中與機(jī)器無關(guān)的部分就能變更目標(biāo)機(jī)對(duì)編譯程序的一些說明編譯程序?qū)嵸|(zhì)上是一個(gè)翻譯程序，要留意等價(jià)變換本課程的任務(wù)就是講解在這個(gè)轉(zhuǎn)換過程中所涉及到的一些理論和方法，最終，運(yùn)用這些理論和方法，自己編寫一個(gè)小的編譯器轉(zhuǎn)換是一個(gè)總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時(shí)要體現(xiàn)軟件工程中軟件設(shè)計(jì)的原則，自頂向下，逐層分解。編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)困難，實(shí)現(xiàn)編譯器時(shí)必需分步驟分階段實(shí)現(xiàn)。分階段實(shí)現(xiàn)的好處是能夠簡(jiǎn)化程序的設(shè)計(jì)，當(dāng)然也可以不分階段實(shí)現(xiàn)。編譯原理是探討編譯程序設(shè)計(jì)的基本理論、基本概念、基本方法什么是編譯原理1/13/202334編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序，把高級(jí)語言經(jīng)分析翻譯為低級(jí)語言。集成開發(fā)環(huán)境：簡(jiǎn)稱IDE（IntegratedDevelopEnvironment），是用于供應(yīng)程序開發(fā)環(huán)境的應(yīng)用程序，一般包括代碼編輯器、編譯器、調(diào)試器和圖形用戶界面工具。背景：早期程序設(shè)計(jì)的各個(gè)階段都要用不同的軟件來進(jìn)行處理,如先用字處理軟件編輯源程序，再用編譯程序進(jìn)行編譯，然后用鏈接程序進(jìn)行函數(shù)、模塊連接,開發(fā)者必需在幾種軟件間來回切換操作。人們習(xí)慣上常常把IDE稱為編譯器。編譯原理引論35常見語言及其IDE語言IDECTC2.0C++C++Builder,VC++6.0,TC3.0C#VS.NETPascalTurboPascalOOPascalDelphiVBVB6.0(解釋器)JavaEclipse,JBuilder1.2編譯的過程1.編譯程序的工作過程2.編譯器各階段的工作1.編譯程序的工作過程編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。將英文句子“Iwishyousuccess翻譯成中文。兩階段完成翻譯分析：分析單詞：I，wish，you，success分析語法：主語，謂語，賓語，賓補(bǔ)分析語義：我希望你成功綜合：綜合英語的意思、上下文環(huán)境和漢語的表達(dá)習(xí)慣，完成翻譯：祝你成功1.編譯程序的工作過程翻譯外文資料：1、能識(shí)別出句子中的一個(gè)單詞；2、分析句子的語法結(jié)構(gòu)；3、依據(jù)句子的含義進(jìn)行初步翻譯；4、對(duì)譯文進(jìn)行修飾；5、寫出最終的譯文。翻譯外文資料與編譯源程序進(jìn)行類比翻譯外文編譯程序分析識(shí)別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成將編譯過程劃分為5個(gè)基本階段詞法分析語法分析語義分析及中間代碼生成代碼優(yōu)化目標(biāo)代碼生成從概念上來講，一個(gè)編譯程序的整個(gè)工作過程是劃分成階段進(jìn)行的，每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個(gè)階段進(jìn)行的操作在邏輯上是緊密連接在一起的。事實(shí)上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構(gòu)造出來了。1.2編譯的過程1.編譯程序的工作過程2.編譯器各階段的工作2.編譯器各階段的工作(1)詞法分析詞法分析階段是編譯過程的第一個(gè)階段。這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，依據(jù)語言的詞法規(guī)則識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，即單詞。2.編譯器各階段的工作依據(jù)詞法規(guī)則分析和識(shí)別單詞。把須要存放的單詞放到符號(hào)表中，如變量名，標(biāo)號(hào)，常量等。工作依據(jù):源語言的構(gòu)詞規(guī)則(即詞法)，也稱為模式(pattern)。標(biāo)識(shí)符的模式是：以字母開頭的字母數(shù)字序列。例：sum=(10+20)*(num+square);結(jié)果(標(biāo)識(shí)符，sum)(賦值號(hào)，=)(左括號(hào)，()(整常數(shù)，10)(加號(hào)，+)(整常數(shù)，20)(右括號(hào)，))(乘號(hào)，*)(左括號(hào)，()(標(biāo)識(shí)符，num)(加號(hào)，+)(標(biāo)識(shí)符，square)(右括號(hào)，))(分號(hào)，;)詞法分析的功能如下：識(shí)別出源程序中意義獨(dú)立的最小詞法單位—單詞。刪除無用的空格、回車和其他與輸入介質(zhì)有關(guān)的符號(hào)刪除程序員為了提高程序可讀性所加的注釋假如發(fā)覺錯(cuò)誤則報(bào)告出錯(cuò)(2)語法分析依據(jù)語法規(guī)則（即語言的文法），分析并識(shí)別出各種語法成分（如表達(dá)式、語句、函數(shù)等），并進(jìn)行語法正確性檢查。通常將語法分析的結(jié)果表示為語法樹。sum=(10+20)*(num+square);語法分析的功能是進(jìn)行層次分析，把源程序的單詞序列組成語法短語(表示成語法樹)。依據(jù)的是語法規(guī)則。C語言的賦值語句的規(guī)則為：

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

<賦值語句>::=<標(biāo)識(shí)符>“=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>|<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|<標(biāo)識(shí)符>|<整數(shù)>|<實(shí)數(shù)>(3)語義分析及中間代碼生成語義分析階段的任務(wù)是審查源程序有無語義錯(cuò)誤。工作依據(jù)：源語言的語義規(guī)則一個(gè)重要任務(wù)：類型檢查依據(jù)規(guī)則檢查每個(gè)運(yùn)算符及其運(yùn)算對(duì)象是否符合要求；數(shù)組的下標(biāo)是否合法；過程調(diào)用時(shí)，形參與實(shí)參個(gè)數(shù)、類型是否匹配等(3)語義分析及中間代碼生成源程序中有些語法成分，依據(jù)語法規(guī)則去推斷，它是正確的，但它不符合語義規(guī)則。比如運(yùn)用了沒有聲明的變量；或者給一個(gè)過程名賦值；或者調(diào)用函數(shù)時(shí)參數(shù)類型不合適或者參與運(yùn)算的兩個(gè)變量類型不匹配等等。比如下邊的程序片段：

intarr[2],c;

c=arr1*10;其中的賦值語句是符合語法規(guī)則的，但是因?yàn)闆]有聲明變量arr1，而存在語義錯(cuò)。中間代碼生成(可選）所謂“中間代碼”是一種結(jié)構(gòu)簡(jiǎn)潔、含義明確的記號(hào)系統(tǒng)，這種記號(hào)系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，重要的設(shè)計(jì)原則為兩點(diǎn)：一是簡(jiǎn)潔生成；二是簡(jiǎn)潔將它翻譯成目標(biāo)代碼。中間代碼的形式： 四元式、三元式、逆波蘭表示中間代碼(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，⑶)

語法樹(4)中間代碼優(yōu)化(可選）代碼優(yōu)化階段的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行變換或進(jìn)行改造，目的是使生成的目標(biāo)代碼更為高效，即省時(shí)間和省空間。例：sum=(10+20)*(num+square)得到的四元式T1=10+20T2=num+squareT3=T1*T2sum=T3優(yōu)化后T1=num+squareSum=30*T1這只是優(yōu)化工作的兩個(gè)方面，此外諸如公共子表達(dá)式的刪除、強(qiáng)度減弱、循環(huán)優(yōu)化等優(yōu)化工作將在后面的章節(jié)具體介紹。代碼優(yōu)化工作會(huì)降低編譯程序的編譯速度，因此編譯優(yōu)化階段常常作為可選擇階段，編譯程序具有限制機(jī)制以允許用戶在編譯速度和目標(biāo)代碼的質(zhì)量間進(jìn)行權(quán)衡。思索：代碼優(yōu)化能提高編譯程序的運(yùn)行效率嗎？(5)目標(biāo)代碼生成目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的確定指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最終階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個(gè)階段的工作很困難，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間支配以及寄存器和后緩寄存器的調(diào)度等。涉及到的兩個(gè)重要問題：對(duì)程序中運(yùn)用的每個(gè)變量要指定存儲(chǔ)單元對(duì)變量進(jìn)行寄存器支配例：sum=(10+20)*(num+square)得到的優(yōu)化后四元式T1=num+squareSum=30*T1生成如下指令序列：MOVnum,R1MOVsquare,R2ADDR2,R1MUL30,R1MOVR1,sum目標(biāo)代碼可接受如下三種形式之一：(1)具有確定地址的機(jī)器指令代碼。(2)匯編語言形式的目標(biāo)程序。須要經(jīng)過匯編程序匯編，以產(chǎn)朝氣器代碼。(3)可重定位的指令代碼。多數(shù)編譯程序所產(chǎn)生的目標(biāo)代碼都是這種類型。語句sum=(10+20)*(num+square);的翻譯過程編譯過程小結(jié)目標(biāo)代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序S.PO.P上述編譯過程的階段劃分是一種典型的處理模式，事實(shí)上并非全部的編譯程序都包括這樣幾個(gè)階段。有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；有些編譯程序不進(jìn)行優(yōu)化，優(yōu)化階段即可省去;有些最簡(jiǎn)潔的編譯程序只有詞法分析，語法分析；語義分析和目標(biāo)代碼生成。1.3編譯程序的邏輯結(jié)構(gòu)

按邏輯功能不同，可將編譯過程劃分為五個(gè)基本階段，與此相對(duì)應(yīng)，我們將實(shí)現(xiàn)整個(gè)編譯過程的編譯程序劃分為五個(gè)邏輯階段（即五個(gè)邏輯子過程）。每個(gè)階段中都要有：符號(hào)表管理和錯(cuò)誤處理典型的編譯程序具有7個(gè)邏輯部分S.PO.P語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理<1>詞法分析：識(shí)別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標(biāo)識(shí)符、字面量、特殊符號(hào)；<2>語法分析：得到語言結(jié)構(gòu)并以樹的形式表示<3>語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，可修改樹結(jié)構(gòu)；<4>中間代碼生成（可選）：生成一種既接近目標(biāo)語言，又與具體機(jī)器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與說明器可以一樣）<5>中間代碼優(yōu)化（可選）：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化事實(shí)上是一個(gè)等價(jià)變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時(shí)間上都更省、更有效。<6>目標(biāo)代碼生成：不同形式的目標(biāo)代碼－匯編、可重定位、確定機(jī)器指令;<7>符號(hào)表管理：合理組織符號(hào)，便于各階段查找、填寫等；<8>出錯(cuò)處理：錯(cuò)誤的種類－詞法錯(cuò)、語法錯(cuò)、靜態(tài)語義錯(cuò)、動(dòng)態(tài)語義錯(cuò)。符號(hào)表管理編譯程序的一項(xiàng)重要工作：記錄源程序中運(yùn)用的標(biāo)識(shí)符收集每個(gè)標(biāo)識(shí)符的各種屬性信息符號(hào)表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)每個(gè)標(biāo)識(shí)符在表中有一條記錄記錄的域是標(biāo)識(shí)符的屬性對(duì)符號(hào)表結(jié)構(gòu)的要求：應(yīng)允許快速地找到標(biāo)識(shí)符的記錄可在其中存取數(shù)據(jù)標(biāo)識(shí)符的各種屬性是在編譯的各個(gè)不同階段填入符號(hào)表的。聲明語句：floattotal,rate;詞法分析器：float是關(guān)鍵字total、rate是標(biāo)識(shí)符在符號(hào)表中創(chuàng)建這兩個(gè)標(biāo)識(shí)符的記錄語義分析器：total、rate都表示變量float表示這兩個(gè)變量的類型可以把這兩種屬性及存儲(chǔ)支配信息填入符號(hào)表。在語義分析和生成中間代碼時(shí)，還要在符號(hào)表中填入對(duì)這個(gè)float型變量進(jìn)行存儲(chǔ)支配的信息。錯(cuò)誤處理在編譯的每個(gè)階段都可能檢測(cè)到源程序中存在的錯(cuò)誤詞法分析程序可以檢測(cè)出非法字符錯(cuò)誤。語法分析程序能夠發(fā)覺記號(hào)流不符合語法規(guī)則的錯(cuò)誤。語義分析程序試圖檢測(cè)出具有正確的語法結(jié)構(gòu)，但對(duì)所涉及的操作無意義的結(jié)構(gòu)。代碼生成程序可能發(fā)覺目標(biāo)程序區(qū)超出了允許范圍的錯(cuò)誤。處理與復(fù)原推斷位置和性質(zhì)適當(dāng)?shù)膹?fù)原出錯(cuò)處理實(shí)力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個(gè)重要指標(biāo)。編譯有關(guān)的其他概念“遍”前端和后端編譯器掃描的遍數(shù)遍（趟）：是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一遍，并作有關(guān)加工處理，生成新的中間結(jié)果或目標(biāo)程序。例如：詞法分析器對(duì)輸入源程序進(jìn)行第一遍掃描，語法分析進(jìn)行其次遍掃描但一個(gè)階段對(duì)應(yīng)一遍掃描的工作方式是邏輯上的，由于多次掃描的方式須要大量的存儲(chǔ)空間存放中間表示，并且會(huì)增加一些不必要的輸入輸出操作，因此編譯器往往把若干個(gè)階段的工作結(jié)合起來，對(duì)應(yīng)一遍掃描，從而削減對(duì)程序的掃描遍數(shù)。一個(gè)編譯程序應(yīng)分成幾遍，如何劃分，是與源程序、設(shè)計(jì)要求、硬件設(shè)備等諸因素有關(guān)的，因地難于統(tǒng)一劃定。在主存可能的前提下，一般遍數(shù)盡可能少一點(diǎn)為好。但并不是每種語言都可以用單遍編譯程序?qū)崿F(xiàn)。一遍掃描的編譯程序語法分析器取記號(hào)詞法分析器源程序記號(hào)語法成分語義分析及代碼生成目標(biāo)程序返回限制流信息流起先結(jié)束整理目標(biāo)程序多遍編譯程序編譯階段的組合在前面所探討的編譯過程中階段的劃分是編譯程序的邏輯組織。有時(shí)，常常把編譯的過程分為前端(frontend)和后端(backend)，前端的工作主要依靠于源語言而與目標(biāo)機(jī)無關(guān),后端工作依靠于目標(biāo)機(jī)而一般不依靠源語言。依據(jù)編譯程序各部分功能，將編譯程序分成前端和后端前端：通常將與源程序有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成 ---分析部分特點(diǎn)：與源語言有關(guān)后端：與目標(biāo)機(jī)有關(guān)的部分稱為后端。代碼優(yōu)化、代碼生成---綜合部分特點(diǎn)：與目標(biāo)機(jī)有關(guān)編譯程序的前端和后端編譯階段的組合為什么生成中間代碼.javajava源程序文件.class二進(jìn)制字節(jié)碼文件Java虛擬機(jī)（JVM)本地計(jì)算機(jī)系統(tǒng)編譯同一前端+不同后端不同機(jī)器構(gòu)成同一語言的編譯程序例如Java語言

不同前端+同一后端同一機(jī)器生成幾個(gè)語言的編譯程序例如GCC編譯程序集合編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)(續(xù))Token表符號(hào)表常數(shù)表錯(cuò)誤信息語法樹中間代碼表臨時(shí)文件目標(biāo)代碼表1/13/2023第83頁1.4編譯程序的設(shè)計(jì)構(gòu)造編譯程序要駕馭以下幾方面的內(nèi)容：源語言：理解其結(jié)構(gòu)和含義目標(biāo)語言：必需清晰硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等編譯方法1/13/2023第84頁1.4編譯程序的設(shè)計(jì)一般實(shí)現(xiàn)編譯程序的方法有：1.干脆用機(jī)器語言編寫編譯程序2.用匯編語言編寫編譯程序注：編譯程序核心部分常用匯編語言編寫3.用高級(jí)語言編寫編譯程序注：這是普遍接受的方法4.自編譯5.用編譯工具自動(dòng)生成:LEX(詞法分析)與YACC(用于自動(dòng)產(chǎn)生LALR分析表)6.移植（同種語言的編譯程序在不同類型的機(jī)器之間移植）1.4編譯程序的生成早期人們用匯編語言編寫編譯程序，但其效率低，實(shí)現(xiàn)困難，比如FORTRAN語言編譯器18年才完成。特地的編譯編譯工具，可以支持編譯程序某些部分的自動(dòng)生成。比如：LEX和YACC等。說到一個(gè)編譯程序，確定要知道它的源語言是什麼，目標(biāo)語言是什麼，還有它的實(shí)現(xiàn)語言是什麼。常運(yùn)用T型圖來表示一個(gè)編譯程序所涉及的三個(gè)語言。

S：源語言O(shè)：目標(biāo)語言T：編譯程序?qū)崿F(xiàn)語言SOT開發(fā)編譯程序的途徑:自展法工具法自動(dòng)生成法移植法自展法利用A機(jī)器上已有的用A代碼編寫的L1語言的編譯程序，把用L1語言編寫的L2語言的編譯程序進(jìn)行編譯，得到A機(jī)器代碼實(shí)現(xiàn)的L2語言的編譯程序。表示為：L2語言A代碼L1語言L1語言A代碼A代碼L2語言A代碼A代碼或者表示為：L2語言A代碼L1語言L1語言A代碼A代碼L2語言A代碼A代碼問題一：如何干脆在一個(gè)機(jī)器上實(shí)現(xiàn)C語言編譯器？解決：用匯編語言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)用匯編程序處理該程序,得到(P2:可干脆運(yùn)行)用Ｃ子集編制Ｃ語言的編譯程序(P3—人)用P2編譯P3，得到P4自展4.用P2編譯P3，得到P4Ｃ語言機(jī)器語言機(jī)器語言P4Ｃ子集機(jī)器語言機(jī)器語言P2獲得一個(gè)工具Ｃ子集匯編語言機(jī)器語言P01.用匯編語言實(shí)現(xiàn)一個(gè)Ｃ子集的編譯程序(P0—人)匯編語言機(jī)器語言機(jī)器語言Ｃ子集機(jī)器語言機(jī)器語言P1P22.用匯編程序(P1)處理該程序,得到(P2:可干脆運(yùn)行)Ｃ語言Ｃ子集機(jī)器語言P33.用Ｃ子集編制Ｃ語言的編譯程序(P3—人)移植問題二：A機(jī)上有一個(gè)C語言編譯器，是否可利用此編譯器實(shí)現(xiàn)B機(jī)上的C語言編譯器？條件：Ａ機(jī)有Ｃ語言的編譯程序目的：實(shí)現(xiàn)Ｂ機(jī)的Ｃ語言的編譯Ｃ語言A機(jī)器A機(jī)器Ｃ語言B機(jī)器Ｂ機(jī)器要完成的任務(wù)Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器Ｂ機(jī)器Ｃ語言Ｂ機(jī)器Ｂ機(jī)器Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器A機(jī)器Ｃ語言A機(jī)器Ｂ機(jī)器須要編寫的程序1)問題的分析1.(人)用Ｃ語言編制B機(jī)的Ｃ編譯程序P0(C→B)(Ａ機(jī)的C編譯P1)編譯P0，得到在A機(jī)上可運(yùn)行的P2(C→B)Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器A機(jī)器Ｃ語言A機(jī)器Ｂ機(jī)器P0P1P2獲得一個(gè)工具2)問題的解決方法3.(Ａ機(jī)的P2)編譯P0，得到在B機(jī)上可運(yùn)行的P3(C→B)P2Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器Ｂ機(jī)器Ｃ語言Ｂ機(jī)器Ｂ機(jī)器P0P3Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器A機(jī)器Ｃ語言A機(jī)器Ｂ機(jī)器P0P1P2獲得的工具編譯程序移植：用A機(jī)器上的L語言編寫能在機(jī)器B上運(yùn)行的L語言的編譯程序先用L語言編寫出在A機(jī)器上運(yùn)行的產(chǎn)生B機(jī)器代碼的L編譯程序源程序，然后把該程序經(jīng)過A機(jī)器上的L編譯程序編譯后得到能在A機(jī)器上運(yùn)行的產(chǎn)生B機(jī)器代碼的編譯程序，用這個(gè)編譯程序再一次編譯上述源程序。

LBL