第一章編譯概述

1

編譯原理與技術(shù)2課程內(nèi)容簡介

介紹編譯器(編譯程序)構(gòu)造的原理和實現(xiàn)方法理論知識包括：詞法分析方法（形式語言和自動機理論）、語法分析方法（自頂向下、自底向上）、語義分析（語法制導(dǎo)的定義和屬性文法）、代碼優(yōu)化等強調(diào)形式化描述技術(shù)（涉及到很多數(shù)學(xué)定義）最終目的是要求掌握涉及編譯器的算法的核心思想，不偏向于某種源語言或某個目標(biāo)機器3學(xué)習(xí)意義

理解高級程序語言的運行機制編譯器的設(shè)計原理和實現(xiàn)技術(shù)具有通用性（符號處理技術(shù)以及各類分析算法）培養(yǎng)“計算機思維”：計算機怎么解決問題？

如何讓計算機幫助我們？計算機專業(yè)特有課程其他專業(yè)的考研科目4考研試題舉例（1）1、試寫出一個上下文無關(guān)文法G,它能產(chǎn)生配對的圓括號串(例如,(),(()),()(())等,甚至包含0對括號).使用文法G給出輸入串(())()#的自上而下分析過程。

5考研試題舉例（2）有如下一個C語言程序，實現(xiàn)了m和2的n次方的乘積運算,試給出運行時整個棧的內(nèi)容。棧內(nèi)數(shù)據(jù)區(qū)的活動記錄結(jié)構(gòu)如圖所示.

┌──────┐┌─────┐

│函數(shù)f返回值││返回結(jié)果值│

├──────┤├─────┤

│局部變量區(qū)││局部變量區(qū)│

├──────┤├─────┤

│全局變量區(qū)││形參單元區(qū)│

├──────┤├─────┤

│主程序main││返回地址│

│數(shù)據(jù)區(qū)│├─────┤

└──────┘│

基SP

│

├─────┤

│函數(shù)數(shù)據(jù)區(qū)│

└─────┘

考研試題舉例（2）續(xù)intm;intn;

intf(n)

{intc;

if(n==0)c=m;

elsec=f(n-1)*2;

returnc;

}

voidmain()

{intn=2;

m=5;

printf("%d\n",f(n));

}67學(xué)習(xí)要求先修課程：

某一門高級程序設(shè)計語言、高等數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、匯編語言、離散數(shù)學(xué)本課程學(xué)習(xí)方法：勤畫圖既涉及算法，又聯(lián)系到程序設(shè)計語言，注重聯(lián)想考核方式：平時30%+期末考試70%8編譯原理呂映芝張素琴等清華大學(xué)出版社

程序設(shè)計語言編譯原理陳火旺等

國防工業(yè)出版社編譯原理及編譯程序構(gòu)造秦振松等東南大學(xué)出版社參考書籍參考書籍龍書Compilers:Principles,Techniques,andTools作者：AlfredV.Aho,RaviSethi,JeffreyD.Ullman.

鯨書AdvancedCompilerDesignandImplementation作者：StevenS.Muchnick虎書ModernCompilerImplementationinJava/C++/ML,SecondEdition作者：AndrewW.Appel,MaiaGinsburg9教學(xué)內(nèi)容目錄編譯基本概念形式語言描述詞法分析與有限自動機自頂向下的語法分析自底向上的語法分析語義分析與目標(biāo)代碼生成中間代碼與代碼優(yōu)化10第一章編譯概述1.1編譯程序的基本概念1.2編譯程序的邏輯結(jié)構(gòu)1.3編譯程序的構(gòu)造1.4編譯技術(shù)的應(yīng)用1.5編譯技術(shù)的發(fā)展1.6解釋系統(tǒng)的定義11什么是編譯程序(compiler)？定義：一個語言翻譯程序作用：是把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標(biāo)語言)書寫的等價的程序.12為什么需要編譯(compiler)？？？13程序是按一定規(guī)則書寫的一系列的符號串序列。程序設(shè)計語言是人工設(shè)計的、用來書寫程序的符號語言。程序設(shè)計語言：從低級到高級分為三類機器語言匯編語言高級程序設(shè)計語言知識回顧：14

機器語言程序100058201020C(1020)=>reg2100459201024C(reg2)～C(1024)100847C01014當(dāng)<=時goto1014100C50201028C(reg2)=>1028101047F0101Cgoto101C101458201024C(1024)=>reg2101850201028C(reg2)=>1028101C…15

匯編語言程序

L2，xx=>reg2C2，yreg2(x)～yBNGLESS當(dāng)<=時gotoLESSST2，maxreg2(x)=>maxBEXITgotoEXITLESSL2，yy=>reg2ST2，maxreg2(y)=>maxEXIT高級程序設(shè)計語言程序

if(x>y)max=x;elsemax=y;Q：編寫好的程序能直接在計算機上執(zhí)行么？？？A：除非是機器語言編寫的程序，否則就是

雞同鴨講，對牛彈琴，計算機無法理解、

識別指令，因此無法執(zhí)行程序。PS：

1）會用機器語言編寫程序的程序猿已經(jīng)

絕種2）沒必要使用低級語言編程

1617

編譯器匯編器裝配連接編輯

源程序

目標(biāo)匯編程序

可重定位機器代碼

絕對機器碼可重定位目標(biāo)文件庫語言處理過程18編譯器的功能：

擔(dān)任翻譯、糾錯角色

高級語言書寫的程序編譯程序低級語言書寫的程序出錯信息19專業(yè)術(shù)語編譯程序、編譯器(compiler)編譯程序接受輸入的源語言(源程序)(source

language)(source

program)編譯程序輸出的目標(biāo)語言(目標(biāo)程序)(objectortargetlanguage)(objectortargetprogram)編譯程序的實現(xiàn)語言

(implementationlanguage)SOISTI20TheroleofacompilerinasystemKernelOSKernelOSShellDBMSApplicationProgramsACompiler編譯器的角色：

21編譯器的性質(zhì)：從軟件的角度語言處理軟件：

把高級語言書寫的各種程序處理成可在計算機上執(zhí)行的程序系統(tǒng)軟件：

居于計算機系統(tǒng)中最靠近硬件的一層，其他應(yīng)用軟件必須要通過系統(tǒng)軟件才能發(fā)揮作用。編譯系統(tǒng)和操作系統(tǒng)與具體的應(yīng)用領(lǐng)域無關(guān)，所以都是系統(tǒng)軟件221.2編譯過程和編譯程序的結(jié)構(gòu)編譯邏輯過程詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成23英譯漢與編譯的類比1.識別出句子中的一個個單詞2.分析句子的語法結(jié)構(gòu)3.分析句子的語義4.初步翻譯5.譯文修飾6.寫出最后譯文1.詞法分析2.語法分析3.語義分析4.中間代碼生成5.優(yōu)化6.目標(biāo)代碼生成24編譯程序總體結(jié)構(gòu)中間代碼目標(biāo)代碼生成器代碼優(yōu)化器語義分析中間代碼生成器語法分析器表格管理出錯處理中間代碼目標(biāo)代碼語法單位單詞符號詞法分析器源程序25一、詞法分析從左至程右解析源程序(字符流)識別出單詞token詞法分析器（掃描器LexicalAnalyzer）：1）從左到右掃描源程序（字符串序列）并將該字符串

轉(zhuǎn)換成單詞(記號串—Token）2）查詞法錯誤并進行標(biāo)識符登記

（符號表格管理）輸入：源程序（字符串）輸出：二元組(類型碼，屬性值)26

詞法分析舉例：

從左往右詞法分析pascal語句

輸入：position:=initial+rate*60;

單詞類型（類型碼）單詞值標(biāo)識符1(id1) position運算符(賦值符號):=標(biāo)識符2(id2) initial運算符(加號) +標(biāo)識符3(id3) rate運算符(乘號) *整型常量 60分界符 ；輸出27詞法分析舉例：一個C源程序片斷：inta;

a=a+2;單詞類型

單詞值關(guān)鍵字int標(biāo)識符(變量名)

a分界符；標(biāo)識符(變量名)

a運算符(賦值號)=標(biāo)識符(變量名)a運算符(加號) +整型常量 2分界符 ；輸出28總結(jié)conclusion:詞法分析(lexicalanalysisorscanning)--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.單詞---token保留字、關(guān)鍵字---reservedword/keyword標(biāo)識符---identifier(user-definedname)29二、語法分析語法分析器(SyntaxAnalyzer、Parser解析器）：依據(jù)源程序語言的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹)，將詞組成各類語法成分：表達式、短語、語句、子程序…構(gòu)造語法分析樹指出語法錯誤指導(dǎo)語義翻譯（作為語義分析的基礎(chǔ)）輸入：Token序列輸出：語法成分->表達式、短語、語句、子程序30語法分析舉例：position:=initial+rate*60根據(jù)pascal語法規(guī)則進行語法分析<賦值表達式>::=<標(biāo)識符>“:=”<表達式>

<表達式>::=<表達式>“+”<表達式><表達式>::=<表達式>“*”<表達式><表達式>::=“(”<表達式>“)”

<表達式>::=<標(biāo)識符><表達式>::=<整數(shù)>

<表達式>::=<實數(shù)>

::=可以解釋為由。。。組成或者定義成。。。。31

賦值表達式標(biāo)識符表達式表達式+表達式表達式標(biāo)識符整數(shù)標(biāo)識符:=表達式*32C語句：res=fact*(term1+term2);根據(jù)C語法規(guī)則進行語法分析<賦值語句>::=<標(biāo)識符>“=”<表達式>“；”<表達式>::=<表達式>“+”<表達式>

<表達式>::=<表達式>“*”<表達式><表達式>::=“(”<表達式>“)”<表達式>::=<標(biāo)識符><表達式>::=<整數(shù)>

<表達式>::=<實數(shù)>33C語句：res=fact*(term1+term2);*；賦值語句表達式=）（fact表達式res表達式表達式表達式表達式+term1term234總結(jié)conclusion:語法分析(syntaxanalysisorparsing)Thepurposeofsyntaxanalysisistodeterminethesourceprogram’sphrasestructure.

Thisprocessisalsocalledparsing.Thesourceprogramisparsedtocheckwhetheritconformstothesourcelanguage’ssyntaxandtoconstructasuitablerepresentationofitsphrasestructure：語法樹(推導(dǎo)樹)(parsetreeorderivationtree).35三、語義分析功能：分析由語法分析器識別出的語法成分的語義語義審查(靜態(tài)語義)獲取標(biāo)識符的語義屬性：類型、作用域等，填充符號表格語義檢查：運算的合法性、取值范圍、類型匹配、類型轉(zhuǎn)換、上下文的相關(guān)性等子程序的靜態(tài)綁定：代碼的相對地址變量的靜態(tài)綁定：數(shù)據(jù)的相對地址36語義分析（基于語法樹）

position:=initial+rate*60;

假設(shè)initial、rate是double類型

60:=+*Id1positionId2initialId3rate類型轉(zhuǎn)換37總結(jié)conclusion:語義分析(semanticanalysis)Theparsedprogramisfurtheranalyzedtodeterminewhetherit

conformstothesourcelanguage’scontextualconstraints:scoperules,typerulese.g.Torelateeachappliedoccurrenceofanidentifierinthesourceprogramtothecorrespondingdeclaration.38四、中間代碼生成源程序的另一種表示方式三元式、四元式、波蘭式、逆波蘭式簡單規(guī)范與機器無關(guān)易于優(yōu)化與轉(zhuǎn)換成目標(biāo)代碼39例:源代碼id1+id2*id3后綴表示(逆波蘭Anti-PolishNotation)id1id2id3*

+前綴表示(波蘭PolishNotation)+id1*id2id3四元式表示(三地址碼)1(*,id2,id3,T1)2(+,id1,T1,T2)

三元式表示1(*,id2,id3)2(+,id1,(1))40四元式中間代碼：id1:=id2+id3*60

假設(shè)id1，id2，id3都是double類型(1) (inttoreal, 60 - t1 )(2) (* , id3 t1 t2 )(3) (+ , id2 t2 t3 )(4) (:= , t3 - id1 )41總結(jié)conclusion:

中間代碼生成(intermediatecodegeneration)Wewantthisrepresentationtobeeasytogenerate,easytotranslateintothetargetprogram.Therepresentationcanhaveavarietyofforms,butacommononeiscalledthree-addresscodeor4-tuplecode.42五、代碼優(yōu)化目的：提高運行速度（節(jié)省時間）和節(jié)省存儲空間

43代碼優(yōu)化例子：源代碼優(yōu)化t1=b*ct1=b*ct2=t1+0t2=t1+t1t3=b*ca=t2t4=t2+t3a=t4a=2*b*c44代碼優(yōu)化例子：中間代碼優(yōu)化id1:=id2+id3*60(1) (inttoreal 60 - t1 )(2) (*id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1 )

(1)(* id3 60.0 t1 )(2)(+id2 t1 id1 )45與機器無關(guān)的優(yōu)化局部優(yōu)化常量合并：常數(shù)運算在編譯期間完成，如8+9*4，包括const符號常量公共子表達式的提?。ǚ种ЫY(jié)構(gòu)、循環(huán)結(jié)構(gòu)）:

基本塊內(nèi)循環(huán)優(yōu)化強度削減用較快的操作代替較慢的操作比如+代替*代碼外提將循環(huán)不變計算移出循環(huán)46與機器有關(guān)的優(yōu)化寄存器的利用將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù)體系結(jié)構(gòu)MIMD、SIMD、SPMD、向量機、流水機、多核存儲策略根據(jù)算法訪存的要求安排：Cache、并行存儲體系——減少訪問沖突任務(wù)劃分按運行的算法及體系結(jié)構(gòu)，劃分子任務(wù)(MPMD)47總結(jié)conclusion:代碼優(yōu)化(Intermediatecodeoptimization）1）Theoptimizeracceptsinputintheintermediaterepresentationandoutputaversionstillintheintermediaterepresentation.2）compilerattemptstoproducethesmallest,fastestandmostefficientrunningresultbyapplyingvarioustechniques.48六、目標(biāo)代碼生成將中間代碼轉(zhuǎn)換成目標(biāo)機上的機器指令代碼或匯編代碼。目標(biāo)代碼的多種形式具有絕對地址的機器指令模塊結(jié)構(gòu)的機器指令（需要鏈接程序）匯編語言形式的目標(biāo)匯編程序49目標(biāo)代碼生成舉例(* , id3 60.0 t1 )(+ , id2 t1 id1 )movfid3,R2mulf #60.0,R2movfid2,R1addf R2,R1movfR1,id150編譯過程：51表處理詞法分析源程序目標(biāo)程序錯誤處理語法分析語義分析目標(biāo)代碼生成前端后端中間代碼優(yōu)化中間代碼生成52Structureofacompiler53前端與后端前端與源語言有關(guān)、與目標(biāo)機器無關(guān)的部分詞法分析、語法分析、語義分析與中間代碼生成、與機器無關(guān)的代碼優(yōu)化后端與目標(biāo)機器有關(guān)的部分與機器有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成54符號表管理記錄源程序中使用的各種符號和名字收集每個名字的各種屬性信息類型、作用域、分配存儲信息管理各種符號表（常數(shù)、標(biāo)號、變量、函數(shù)、結(jié)構(gòu)……），登記、查找源程序中出現(xiàn)的符號和編譯程序生成的符號，為編譯的各個階段提供信息。輔助語法檢查、語義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種查、填表技術(shù)（數(shù)據(jù)結(jié)構(gòu)）55出錯處理

進行各種錯誤的檢查、報告、糾正以及相應(yīng)的續(xù)編譯處理（如：錯誤的定位與局部化）詞法：拼寫錯誤……語法：語句結(jié)構(gòu)、表達式結(jié)構(gòu)……語義：類型不匹配……56程序錯誤語法錯誤語義錯誤運行57編譯程序結(jié)構(gòu)(components)設(shè)計詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標(biāo)代碼生成程序符號表管理程序出錯處理程序58根據(jù)系統(tǒng)資源的狀況、運行目標(biāo)的要求等，將一個編譯程序設(shè)計成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。每遍的工作由從外存上獲得的前一遍的中間結(jié)果開始（對于第一遍而言，從外存上獲得源程序），完成有關(guān)工作之后,把結(jié)果記錄于外存。既可以將幾個不同階段合為一遍，也可以把一個階段的工作分為若干遍。遍（Pass）編譯程序的架構(gòu)設(shè)計591）一遍的編譯程序

即對源程序進行一遍掃描，就完成編譯程序的各項任務(wù)。該編譯程序的核心是不產(chǎn)生中間代碼。

工作過程如下：①當(dāng)語法分析器需要讀進一個新的單詞符號時，就調(diào)用詞法分析器，詞法分析器從源程序中依次讀入字符，并組合成單詞符號，把其送回語法分析器；②當(dāng)語法分析器識別出一個語法短語時，就調(diào)用語義分析程序進行語義分析，并生成目標(biāo)程序；③當(dāng)源程序處理完后，轉(zhuǎn)善后處理，即整理目標(biāo)程序（如優(yōu)化等），并停機。詞法分析器語法分析器整理目標(biāo)程序停機語義分析及代碼生成取單詞返回單詞語法成分返回源程序目標(biāo)代碼編譯程序的架構(gòu)設(shè)計602）多遍編譯程序把編譯的5個階段應(yīng)完成的工作分遍來做，每一遍完成一個或相連幾個階段的工作。源程序詞法分析程序語法分析程序語義分析程序代碼優(yōu)化程序目標(biāo)代碼生成程序目標(biāo)程序表格處理程序出錯處理程序編譯總控程序中間語言1，表中間語言2，表中間語言3，表優(yōu)化代碼，表工作過程如下：編譯程序的主程序調(diào)用詞法分析器掃描源程序，并將它轉(zhuǎn)換成一種內(nèi)部表示，稱為中間語言1，同時產(chǎn)生有關(guān)的一些表，然后主程序再調(diào)用語法分析器，它以中間代碼1為輸入，進行語法分析，產(chǎn)生中間語言2……最后主程序調(diào)用目標(biāo)代碼生成器，把輸入的中間代碼轉(zhuǎn)換為等價的目標(biāo)代碼。61編譯程序分遍的優(yōu)缺點優(yōu)點：1.首先，減少對內(nèi)存容量的要求，分遍后，在編譯時以遍為單位分別調(diào)入編譯程序，各遍編譯程序在內(nèi)存中可以相互覆蓋；2.其次，可使各編譯程序功能獨立、單純，相互聯(lián)系簡單，編譯程序結(jié)構(gòu)清晰；3.再次，能夠?qū)崿F(xiàn)充分地優(yōu)化工作，以獲得高質(zhì)量的目標(biāo)程序；4.最后，通過分遍將編譯程序的前端和后端分開，為編譯程序的移植創(chuàng)造條件。缺點：增加了不少重復(fù)性工作，比如每一遍都有讀符號、送符號等工作，這就降低了編譯的效率。62編譯階段和運行階段內(nèi)存存儲結(jié)構(gòu)

編譯時運行時符號表中間代碼緩沖區(qū)目標(biāo)代碼緩沖區(qū)目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)源程序緩沖區(qū)63編譯程序選擇什么語言來編寫？設(shè)計目標(biāo)目標(biāo)程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強，可靠性強。可移植性，可擴充性。641.以匯編語言和機器語言為工具來構(gòu)造優(yōu)點:可以針對具體的機器，充分發(fā)揮計算機的系統(tǒng)功能。生成的目標(biāo)程序效率高。缺點:程序難讀、難寫、易出錯、難維護、生成編譯程序的效率低。652.高級語言書寫用已有高級語言實現(xiàn)其它高級語言的編譯程序:例如用C寫PASCAL語言的編譯器，然后編譯優(yōu)點:程序易讀、易理解、容易維護、生產(chǎn)編譯程序的效率高。缺點:難以充分發(fā)揮計算機的系統(tǒng)功能，生成的目標(biāo)程序效率低。663.利用工具，編譯程序自動生成LEX

詞法分析程序產(chǎn)生器YACC語法分析程序產(chǎn)生器編譯程序自動產(chǎn)生器L語言的語法描述語義描述目標(biāo)語言或機器描述L語言的編譯程序671.4編譯技術(shù)的發(fā)展功能：集成開發(fā)環(huán)境下實現(xiàn)編譯程序?qū)崿F(xiàn)方式手工機器語言匯編語言高級程序設(shè)計語言自動構(gòu)造工具lexyaccgcc68編譯程序的語言范型語言范型(paradigms)命令式(imperativelanguage)應(yīng)用式(applicative)基于規(guī)則的（rule-based）面向?qū)ο蟮模╫bject-oriented）69編譯程序的執(zhí)行環(huán)境批處理環(huán)境：將源程序作為整體處理排除程序錯誤不能接受任何外部幫助交互環(huán)境：解釋增量式編譯嵌入式系統(tǒng)環(huán)境：交叉編譯分布并行環(huán)境：并行編譯集成式開發(fā)環(huán)境：獨立編譯設(shè)計時同時考慮編譯和調(diào)試70集成化的程序開發(fā)環(huán)境程序開發(fā)環(huán)境編輯程序編譯程序連接程序調(diào)試工具。。。它將相互獨立的程序設(shè)計工具集成起來，以便為程序員提供完整的、一體化的支持，從而進一步提高程序開發(fā)效率改善程序質(zhì)量。如Visualstudio.NetMyEclipse等

711.5

編譯技術(shù)的應(yīng)用語法制導(dǎo)的結(jié)構(gòu)化編輯器程序格式化工具軟件測試工具程序理解工具高級語言的翻譯工具……72編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編譯器程序分析工具靜態(tài)分析動態(tài)分析度量工具結(jié)構(gòu)度量模塊接口復(fù)雜度

c分析工具(sourceinsight)廣泛的語言領(lǐng)域數(shù)據(jù)庫系統(tǒng)查詢腳本語言置標(biāo)語言(SGML.HTML.XML)73源程序輸入數(shù)據(jù)計算結(jié)果解釋程序1.6解釋系統(tǒng)（解釋程序）74高級語言解釋系統(tǒng)(interpreter)功能：讓計算機執(zhí)行高級語言與編譯程序的不同1）不生成目標(biāo)代碼2）能支持交互環(huán)境源程序

初始數(shù)據(jù)解釋程序計算結(jié)果75對比編譯程序與解釋程序編譯程序：直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。如：……

b:=2;a:=b+2;編譯程序

writea;……解釋程序直接將4的值輸出（顯示）Int2StbLdbadd2Sta生成代碼76解釋系統(tǒng)存儲結(jié)構(gòu)解釋程序源程序符號表緩沖區(qū)(輸入輸出)棧區(qū)77編譯和解釋的區(qū)別：目標(biāo)程序源程序編譯程序初始數(shù)據(jù)計算結(jié)果源程序解釋程序初始數(shù)據(jù)計算結(jié)果語法的表示方法：78?口語?語法圖

?BNF表示法

79語法圖：函數(shù)定義函數(shù)首部函數(shù)體函數(shù)首部函數(shù)值類型函數(shù)名（參數(shù)表列）

函數(shù)體{說明部分控制部分}80巴科斯范式（BackusNourForm或BackusNormalForm，簡記為