《編譯原理》第一章 cha1 引論

1第一章引論1.1編譯程序和解釋程序1.2編譯過程和編譯程序的結構（重點）1.2.1編譯過程概述1.2.2編譯程序結構1.2.3編譯階段的組合1.3編譯程序在其他軟件中的應用1.4程序設計語言范型1.5編譯程序實現(xiàn)途徑（可略）本章練習作業(yè)課程目錄21.1什么是編譯程序p1編譯程序的必要性計算機是當代科學發(fā)展的重要工具，已滲入到各個行業(yè)乃至家庭生活中要讓計算機為人類工作服務，就必須建立人與計算機之間的信息交流但計算機只認識由“0”和“1”構成的機器語言，每臺機器都有自己獨特的指令系統(tǒng)，即機器語言最早的程序就是用8進制和16進制碼的機器語言書寫的3編譯程序的必要性（續(xù)）用機器語言書寫程序，不僅不易學，而且可調(diào)試性、可讀性、可維護性和結構性都很差，開發(fā)時間也很長因此，先后出現(xiàn)了用于源程序設計的語言：基于助記符的匯編語言接近人類自然語言的高級程序設計語言編譯程序最初的定義是把一種高級語言設計的源程序(面向人的)翻譯成另一種等價的低級程序設計語言(面向硬件的)即機器語言或匯編語言4程序設計語言源程序的執(zhí)行方式程序設計語言源程序的執(zhí)行基本有兩種方式翻譯使用翻譯程序，將源程序翻譯成為低級語言目標程序，然后執(zhí)行目標程序解釋

使用解釋程序，對源程序逐個語句邊解釋邊執(zhí)行可比喻為譯文—目標程序翻譯—筆譯(產(chǎn)生譯文，可進行優(yōu)化，一次翻譯過后，多次使用)解釋—口譯(不產(chǎn)生譯文，交互方便，節(jié)省空間，對重復部分要反復解釋，效率低）5翻譯程序和解釋程序圖解源程序(源語言)翻譯程序目標程序(目標語言)源程序(源語言)解釋程序輸入輸出共同點：都需進行詞法、語法和語義分析6程序設計語言源程序的執(zhí)行方式例假設有源程序：read(x);write("x=",x);read(x);write("x=",x);目標程序目標程序3X=3read(x);write("x=",x);翻譯程序解釋程序3X=37翻譯程序的分類翻譯程序按所處理源語言不同分為兩種

編譯程序

匯編程序高級語言源程序(*.C/*.PAS)編譯程序匯編或機器語言目標程序(*.OBJ/*.EXE)匯編語言源程序(*.ASM)匯編程序機器語言目標程序(*.EXE)8編譯程序和解釋程序p8最主要區(qū)別是否生成目標程序運行時的存儲分配源程序緩沖區(qū)名字表目標代碼緩沖區(qū)編譯程序用中間表示及各種表格目標代碼區(qū)數(shù)據(jù)區(qū)解釋系統(tǒng)源程序工作單元及名字表標號表緩沖區(qū)（輸入輸出）棧區(qū)編譯程序編譯時和運行時存儲區(qū)內(nèi)容解釋程序存儲區(qū)內(nèi)容9編譯程序和解釋程序Basic、Lisp、Sql解釋程序、Unix命令語言解釋程序及很多腳本語言Javascript等都解釋執(zhí)行的。C、C++、Pascal等語言是編譯執(zhí)行的。Java語言的處理環(huán)境既有編譯程序，也有解釋程序，見圖1.5(p9)Java→編譯程序→Bytecode→解釋程序10高級語言程序

的處理過程P1需預處理的源程序預處理程序源程序編譯程序目標匯編程序匯編程序可再裝配的機器代碼裝配/連接-編譯程序可再裝配目標文件絕對機器代碼章節(jié)目錄111.2.1編譯過程概述p2編譯過程可分為下面5個階段詞法分析語法分析語義分析和中間代碼生成優(yōu)化目標代碼生成表格管理和錯誤處理12第一階段詞法分析p2任務輸入源程序(字符串)根據(jù)語言的詞法規(guī)則對構成源程序的字符串進行掃描和分解識別出一個個的單詞單詞內(nèi)部表示形式二元式(class,value)

單詞類型單詞值例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;…}輸出結果

classvalue

保留字main界符-左括號(界符-右括號)界符-左花括號{保留字float標識符1-id1sum…

算符-乘號*整數(shù)10…

13第二階段語法分析p3

任務輸入單詞符號串根據(jù)語言的語法規(guī)則對單詞符號串進行掃描和分解識別出各類語法單位程序語言的語法單位表達式、語句和程序等例X1=Y+10*Z;C語言賦值語句構成規(guī)則<賦值語句>→<標識符>=<表達式>;定義為<表達式>→<表達式>+<表達式><表達式>→<表達式>*<表達式><表達式>→<標識符>X1,Y,Z<表達式>→<常數(shù)>10可以構成語法單位的單詞符號語法單位表達式Y,10,Z,10*Z

賦值語句X1=Y+10*Z;語法單位內(nèi)部表示語法樹

14語法單位的內(nèi)部表示：語法樹例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;…}<賦值語句>→<標識符>=<表達式>;<表達式>→<表達式>+<表達式><表達式>→<表達式>*<表達式><表達式>→<標識符><表達式>→<常數(shù)>賦值語句的語法樹<賦值語句><標識符>=<表達式>;sum<表達式>+<表達式><標識符>first<表達式>*<表達式><標識符>count<常數(shù)>1015第三階段語義分析與中間代碼產(chǎn)生p4任務輸入各類語法范疇根據(jù)語言的語義規(guī)則，分析其含義，并進行初步翻譯產(chǎn)生中間代碼結構簡單、含義明確的記號系統(tǒng)介于高級語言與低級語言之間，與目標機無關便于優(yōu)化、移植，容易生成目標代碼形式有：三元式、四元式、樹結構等。16中間代碼生成舉例中間代碼生成（四元式）

例：語義分析將

sum=first+count*10；翻譯成如下的四元式序列：(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,_,sum)其中，Ti為語義分析程序為存放中間結果而生成的臨時變量例某C語言源程序main(){floatsum,first,count;

…sum=first+count*10;

…}17第四階段優(yōu)化p5任務輸入中間代碼進行等價變換輸出更高效的中間代碼目的用以提高目標代碼的時、空效率也就是希望完成同樣功能的程序，代碼優(yōu)化后比優(yōu)化前運行的時間短，占用的存儲空間少有時二者不能同時達到，需根據(jù)實際情況取舍18優(yōu)化舉例優(yōu)化前

(1)(inttofloat,10,_，T1)(2)(*,count，T1，T2)(3)(+,first，T2，T3)(4)(=,T3,-,sum)優(yōu)化后

常數(shù)直接代入(*,count,10.0,T1)節(jié)省臨時變量(+,first,T1,sum)

優(yōu)化后有兩條代碼整數(shù)轉換成實數(shù)在編譯時完成臨時變量只用了一個T119第五階段目標代碼生成p5任務輸入優(yōu)化后的中間代碼變換成特定機器上的低級語言代碼，實現(xiàn)最后的翻譯產(chǎn)生目標代碼特點依賴與機器硬件系統(tǒng)通常使用匯編語言作為目標程序的實現(xiàn)語言20目標代碼生成舉例為了生成高效的目標代碼，需要了解機器指令系統(tǒng)和可用計算機資源，假設有兩個可用寄存器R0和R1優(yōu)化后中間代碼(1)(*,count,10.0,T1)(2)(+,first,T1,sum）生成的目標代碼序列(1)LDR0,count

count值送R0(2)MULR0,#10.0

計算count*10.0存于R0(3)LDR1,first

first值送R1(4)ADDR1，R0

計算first+T1存于R121表格管理(符號表管理)任務在完成以上5個過程的同時必須隨時對符號表進行管理記錄源程序中使用的名字收集每個名字的各種屬性信息如類型、作用域、存儲分配信息等例count變量類型float

first變量類型float地址22出錯處理任務發(fā)現(xiàn)源程序中的錯誤檢查詞法、語法和語義中的錯誤(靜態(tài))編譯程序的處理能力，如存儲空間越界(動態(tài))報告出錯信息和位置處理和恢復章節(jié)目錄231.2.2編譯程序的結構p6詞法分析程序語法分析程序語義分析程序與中間代碼產(chǎn)生器優(yōu)化器目標代碼生成器表格管理出錯處理7個或8個部分組成24編譯程序

結構框圖P6源程序字符串詞法分析器單詞符號語法分析器語法單位語義分析程序語法樹中間代碼生成器四元式代碼優(yōu)化程序四元式目標代碼生成器匯編語言或機器語言目標程序信息表格管理程序錯誤檢查和處理程序章節(jié)目錄251.2.3編譯階段的組合p6

前端完成分析工作(與機器無關)詞法分析語法分析語義分析后端完成綜合工作(與機器相關)優(yōu)化：改善目標代碼質(zhì)量目標代碼生成前端源程序中間代碼后端目標代碼目的便于移植前端和后端的概念26遍的概念p6遍從頭到尾對源程序及其內(nèi)部表示掃描一次，并作有關的加工處理遍輸入文件輸出文件從源程序掃描是第一遍輸入每前一遍的輸出是后一遍的輸入分遍的原則按實際情況而定多遍（結構清晰、少占內(nèi)存、讀寫次數(shù)多，耗時）一遍（多占內(nèi)存，速度快）章節(jié)目錄271.3編譯程序在其它軟件中的應用p8語言的結構化編輯器（提示輸入關鍵字、完成括號匹配等）語言程序的調(diào)試工具程序格式化工具（以清晰可讀方式打印程序）軟件測試工具：如FORTRAN，C的靜態(tài)和動態(tài)測試工具（可測試程序語句的覆蓋率、路徑覆蓋率等，都需要編譯技術）高級程序設計語言的轉換工具程序理解工具（OlinkC\C++數(shù)據(jù)流分析

、EclipseTptp性能分析工具）網(wǎng)絡中的協(xié)議數(shù)據(jù)庫系統(tǒng)中各種命令語言的翻譯28

編譯程序在系統(tǒng)軟件中的所在層裸機操作系統(tǒng)語言處理系統(tǒng)應用軟件層章節(jié)目錄1.4程序設計語言范型p1029強制式語言ImperativeFORTRAN、BASIC、Pascal、C函數(shù)式語言

FunctionalLISP、ML邏輯式語言LogicalProlog面向對象語言

Object-OrientedSmalltalk、C++、Java、Ada章節(jié)目錄301.5編譯程序的實現(xiàn)途徑p302應考慮開發(fā)周期、目標程序的效率、可移植性、可調(diào)試性、可維護性和可擴充性等構造方式手工構造用機器語言、匯編語言或高級程序設計語言書寫自動構造工具Lex，Yacc分別是詞法和語法分析器的生成器移植方式目標程序用中間語言自展方式(自編譯方式)用T型圖表示31T型圖STI源語言目標語言編譯程序實現(xiàn)語言含義S語言源程序I語言實現(xiàn)編譯程序

T語言目標程序32編譯程序設計舉例已知A機器上C語言編譯程序CAAC語言編譯程序要求用C語言編寫PASCAL語言A機器編譯程序PLAAPASCAL語言編譯程序最初用C語言編寫PLACC語言編寫的PASCAL語言編譯程序CAAAPLA所求PASCAL語言編譯程序33編譯程序設計L1AA已知A機器上有L1

語言編譯程序要求用L1語言編寫L2語言的A機器編譯程序L2AAL2AL1L1AAL2AA所求L2語言編譯程序34PC機器上C語言編譯程序自展設計實現(xiàn)目標CPCPC步驟1(1)先對C語言核心部分C1構造

PC編譯程序，用低級語言實現(xiàn)C1PCPC(2)再用C1編寫含C更多語言成分的C2的PC編譯程序C2PCC1(3)最后用C2編寫

C語言的PC編譯程序CPCC2其中C1是C2的子集，C2是C的子集35PC機器上C語言編譯程序自展設計實現(xiàn)目標CPCPC步驟2構造C2的PC編譯程序C2PCC1C1PCPCC2PCPC步驟3構造C的PC編譯程序CPCC2C2PCPCCPCPC合并步驟2，3C2PCC1C1PCPC①②③④⑤36L語言編譯程序移植設計已知A機器高級語言L編譯程序要求B機器高級語言L的編譯程序已知LAA實現(xiàn)目標LBB①LAA②LBL用L語言編寫的L→B的編譯程序③LBA用A機器語言實現(xiàn)的L→B的編譯程序④LBL用L語言編寫的L→B編譯程序翻譯⑤LBB用B機器語言實現(xiàn)的L→B的編譯程序章節(jié)目錄37編譯程序的分類p1診斷型編譯程序(DiagnosticCompiler)專門用于幫助程序開發(fā)和調(diào)試著重提高目標代碼效率優(yōu)化型編譯程序(OptimizingCompiler)提供調(diào)試、優(yōu)化等功能，用戶進行選擇使用交叉型編譯程序(CrossCompiler)產(chǎn)生不同于其宿主機的目標機機器代碼運行編譯程序的機器運行所產(chǎn)生目標代碼的機器可變目標型編譯程序(RetargetableCompiler)不需重寫編譯程序中與機器無關的部分就能改變目標機章節(jié)目錄38本章練習

1、編譯程序的結構可以分成以下7個模塊