編譯原理 第1章 編譯系統(tǒng)概述

第1章編譯系統(tǒng)概述1.1 程序設計語言的發(fā)展1.2 基本術語解釋1.3 編譯過程概述1.4 出錯處理1.5 編譯程序的前端和后端1.6 編譯程序的實現(xiàn)方式1.1 程序設計語言的發(fā)展匯編語言(AssembleLanguage)機器語言(MachineLanguage)程序設計語言(ProgrammingLanguage)例計算表達式3*16+2的值，實現(xiàn)該計算的機器語言程序、匯編語言程序和程序設計語言（C語言）程序如下所示。目標計算機的系統(tǒng)結構和匯編語言的使用方法詳見本書第7章。22038210260261011000f000LoadR0,3MulR0,10LoadR1,2AddR0,R1WriteR0Haltvoidmain(void){cout<<3*16+2;}注：10表示16㈠機器語言機器指令集合稱為機器語言。機器指令即二進制數(shù)，通常由若干字節(jié)構成。①優(yōu)點計算機可直接識別執(zhí)行可充分利用硬件特性②缺點可讀性差指令系統(tǒng)隨機種而異由于機器指令直接或間接含有絕對地址，增加或減少一條指令，可能會引起多條指令的修改。編程者需協(xié)調內存的使用所以，機器語言形式的程序編制和維護困難，限制了計算機的推廣和應用。㈡匯編語言用記憶符取代二進制位，存儲地址和匯編語句的序號可用符號名表示。①優(yōu)點用符號取代二進制數(shù)，提高了程序的可理解性。性能較好的匯編語言，可用符號名來表示存儲地址和匯編語句序號，這樣避免了在匯編語句中絕對地址的出現(xiàn)。可充分利用硬件特性所以，匯編語言在一定程度上降低了程序編制和維護的難度。②缺點匯編語句和機器指令基本上是一對一的，所以匯編語言的編程效率并沒有質的提高。和機器語言一樣，匯編語言依附于目標計算機。需匯編程序，將匯編語言譯成機器語言。㈢程序設計語言程序設計語言又稱高級語言。程序設計語言接近于英語，相當于工程語言。目前計算機系統(tǒng)一般含有多個程序設計語言的翻譯程序（例VC、VB等），甚至對同一個程序設計語言配備了多個不同性能的翻譯程序，供用戶選擇使用。①優(yōu)點獨立于具體計算機，面向過程（函數(shù)）或對象。程序設計語言接近于英語，可理解性好。數(shù)據(jù)類型豐富，各種功能的語句齊備，一條語句至少相當于幾十條匯編語句。所以，程序設計語言極大地提高了編程效率，大幅度地降低了編程難度。②缺點需翻譯程序，將高級語言譯成機器語言或匯編語言。對硬件操作困難，高級語言通常提供匯編語言接口。1.2基本術語解釋㈠源語言和源程序(SourceLanguageandSourceProgram)

用程序設計語言書寫的程序，稱為源程序，該程序設計語言稱為源語言。源程序通常用編緝程序輸入，用字符(ASCII碼)表示，以文本文件形式存儲。㈡文本文件(TextFile)

文本文件的內容由94個圖形字符‘!’-‘~’(33-126)和4個控制字符換行(10)、回車(13)、空格(32)、TAB(9)構成，文本文件又稱為ASCII碼文件，擴展名通常為TXT，文件尾用控制字符EOF(26)指示。當換行和回車二個控制字符從文本文件讀入內存，在C語言中是用一個字符（換行）表示。㈢目標語言和目標程序(TargetLanguageandTargetProgram)目標語言可以是機器語言(二進制數(shù))，也可以是匯編語言(字符)，或者是其它中間語言(字符)，但最終結果必定是機器語言。機器語言程序用二進制文件存儲，匯編語言或中間語言程序用文本文件存儲。目標程序是經翻譯程序加工后用目標語言表示的程序。㈣二進制文件(BinaryFile)二進制文件由機器指令即二進制數(shù)構成，因二進制數(shù)可能是26，故文件尾用文件長度(文件的字節(jié)數(shù))指示，擴展名通常為EXE。㈤翻譯程序(Translator)將源程序譯成邏輯上等價的目標程序的程序。翻譯程序有二種工作方式：編譯和解釋。解釋程序Interpreter

源程序結果輸入數(shù)據(jù)解釋、執(zhí)行解釋方式主要特點是：用戶程序是消極的。用戶程序運行時，控制點在解釋程序，即用戶程序的執(zhí)行離不開解釋程序。①解釋方式(Interpret)以源程序作為輸入，輸入一句解釋執(zhí)行一句，不產生完整的目標程序，相應的翻譯程序稱為解釋程序(Interpreter)

。工作方式如下圖所示：②編譯方式(Compile)將源程序全部譯為目標程序，該目標程序可在操作系統(tǒng)環(huán)境下直接執(zhí)行，相應的翻譯程序稱為編譯程序(Compiler)

，工作方式如下圖所示：編譯程序Compile連接程序Link裝入運行Run編輯程序EditASCII碼二進制(整體未定位)

二進制(整體定位)

源程序結果輸入數(shù)據(jù)編輯程序的工作結果是ASCII碼形式的源程序。編譯程序以ASCII碼形式的源程序為輸入，它的工作結果是二進制形式的目標程序，但并未包括用戶程序中所使用的系統(tǒng)函數(shù)的目標代碼。從整體上來看，程序是不完整的，程序中的部分地址尚未確定（例系統(tǒng)函數(shù)的調用）。將二進制形式的用戶程序和系統(tǒng)函數(shù)目標代碼連接成一個程序，對未確定的地址進行定位。由操作系統(tǒng)將用戶程序裝入內存后運行。程序在運行過程中讀入數(shù)據(jù)，經處理加工后輸出計算結果。編譯方式主要特點是：用戶程序是積極的。用戶程序執(zhí)行時，控制點在用戶程序自身。除操作系統(tǒng)外，程序運行無需其它支撐軟件。③二種翻譯方式比較解釋方式和編譯方式的主要區(qū)別是：目標代碼的執(zhí)行方式不同，基本原理和方法沒有本質上的區(qū)別。1）解釋方式的優(yōu)點提供一種直接的交互調試功能，容易獲得較好的動態(tài)調試效果。使用變量可不預先定義。變量性質可動態(tài)修改。2）解釋方式的缺點在執(zhí)行時需動態(tài)地對程序進行分析翻譯，開銷大，其執(zhí)行速度相當于編譯方式的1/10至1/100。解釋方式占用內存大顯然解釋程序的優(yōu)點就是編譯程序的缺點，反之亦然，對于編譯程序的優(yōu)缺點不再重復敘述。④對任何一種高級語言，既可采用編譯方式，也可采用解釋方式，包括匯編語言在內（MASM方式和DEBUG方式）。1.3 編譯過程概述典型的編譯程序工作過程是：輸入源程序，對它進行加工處理，最后輸出目標程序（機器語言或匯編語言形式）。整個過程相當復雜，從數(shù)據(jù)加工的角度來看，可將其分成4個邏輯階段，它們是：詞法分析語法分析語義分析（中間代碼產生）目標代碼生成詞法分析語法分析語義分析(中間代碼產生)目標代碼生成源程序目標程序編譯程序基本上是按照這個流程來設計的。圖示如下： 以算術表達式3+abc*128為例，來說明編譯程序工作過程。㈠詞法分析(LexicalAnalysis)執(zhí)行詞法分析任務的程序稱為詞法分析器。任務：字符串形式單詞編碼形式單詞內部碼（二元式）依據(jù)：語言的構詞規(guī)則①二元式(Pair)(單詞種別,單詞值)單詞種別：用整數(shù)碼表示（為直觀起見用字符表示），語法分析時用。單詞值：在本書中用字符串表示，語義分析時用。當一個單詞種別中可能有多個單詞時，單詞的值才有意義。為了便于輸入處理，無意義的單詞值用"NUL"表示。②二元式編碼單詞單詞種別單詞值++NUL--NUL**NUL//NUL((NUL))NUL………標識符i字符串形式符號名

整常數(shù)x字符串形式整常數(shù)實常數(shù)y字符串形式實常數(shù)………經詞分析，算術表達式3+abc*128的單詞內部碼（二元式）為：('x',"3")('+',"NUL")('i',"abc")('*',"NUL")('x',"128")㈡語法分析(Parsing)執(zhí)行語法分析任務的程序稱為語法分析器。任務：檢查源程序的語法結構是否正確依據(jù)：語言的語法規(guī)則在語法分析時，算術表達式3+abc*128的語法結構應表示為x+i*x，語法分析器最終應識別出這是一個算術表達式。識別過程相當于建立一棵語法樹 <算術表達式> <算術表達式> + <項> <項> <項> * <因子> <因子> <因子> x(整常數(shù)) x(整常數(shù)) i(標識符)㈢語義分析(SemanticAnalysis)執(zhí)行語義分析任務的程序稱為語義分析器或中間代碼產生器。任務：建立符號表和常數(shù)表，記錄源程序中標識符屬性和常數(shù)值，根據(jù)語言的語義規(guī)定生成中間代碼。依據(jù)：語言的語義內涵語義分析（中間代碼產生）主要工作為：語義正確性檢查語義翻譯①語義正確性檢查 例2：begin

real

A;integerB;B=A+B;end

語法正確，不同的語言有不同的語義解釋。標準Fortran語言認為是錯誤的，其不允許不同類型的量進行混合運算。C語言認為是正確的，允許混合運算，但需轉換成相同類型的量，然后再進行運算。Pascal語言認為是錯誤的，雖允許混合運算，但不允許將實型量賦值于整型量。②語義翻譯1)說明語句的翻譯 將標識符及其屬性填入符號表。2)執(zhí)行語句的翻譯 根據(jù)不同語句的語義，生成邏輯上等價的中間代碼。中間代碼結構簡單、意義明確的記號系統(tǒng)，非常接近機器指令，又獨立于具體機器。常用的中間代碼有三元式和四元式。表達式3+abc*128可譯成如下四元式：

(*,&abc,&128,&T1) (+,&3,&T1,&T2)其中，

&abc表示標識符abc在符號表中入口（即地址）；

T1和T2是在翻譯過程中由編譯程序引入的臨時變量，&T1和&T2分別表示T1和T2在符號表中入口；而&128表示常數(shù)128在常數(shù)表中的地址。符號表(SymbolTable)

符號表用于記錄源程序中出現(xiàn)的標識符(Identifier)，一個標識符往往具有一系列的語義值，它包括標識符的名稱、標識符的種屬、標識符的類型、標識符值的存放地址等等。每個標識符在符號表中有一項記錄，用于記錄標識符的各種語義值，而在四元式中填寫的是標識符在符號表中的記錄地址，通常稱為符號表入口。內存地址符號名種屬類型…………未分配abc簡單變量整型未分配T1簡單變量整型未分配T2簡單變量整型…………符號表的結構示意如下：常數(shù)表(ConstantTable)

常數(shù)表用于記錄在源程序中出現(xiàn)的常數(shù)。假定，每個整常數(shù)在常數(shù)表中占2個字節(jié)，每個實常數(shù)在常數(shù)表中占4個字節(jié)。常數(shù)的二進制值00000000-00000011（3）00000000-01000000（128）……常數(shù)表的結構示意如下：㈣目標代碼生成(CodeGeneration)執(zhí)行目標代碼生成的程序稱為目標代碼生成器。任務：中間代碼目標代碼（機器指令或匯編語言）依據(jù)：目標機器的系統(tǒng)結構假設模型機器的指令格式為：

opRi,M （Ri）op（M）→Ri

opRi,Rj （Ri）op（Rj）→Ri

opRi,C （Ri）opC→Ri其中Ri表示寄存器，M表示內存地址（可用符號表示），C表示常數(shù)。表達式3+abc*128最終形成的匯編語言程序示意如下： LoadR0,abc MulR0,128 StoreR0,T1 LoadR0,3 AddR0,T1 StoreR0,T2編譯程序在工作過程中可發(fā)現(xiàn)源程序中各種錯誤，錯誤類型及錯誤處理對策簡述如下：㈠錯誤類型詞法錯誤（可在詞法分析階段發(fā)現(xiàn)）語法錯誤（可在語法分析階段發(fā)現(xiàn)）語義錯誤（可在語義分析階段發(fā)現(xiàn)）1.4 出錯處理(ErrorHandle)㈡出錯處理一旦發(fā)現(xiàn)錯誤，暫停編譯程序工作，指出錯誤的地點和類型。在發(fā)現(xiàn)錯誤后，不中斷編譯程序工作。采取某些措施（例錯誤局部化、錯誤校正等），使得源程序的編譯工作可繼續(xù)下去，盡可能發(fā)現(xiàn)源程序中比較多的錯誤。1.5 編譯程序的前端和后端

由于在編譯程序的內部引入了中間代碼，這樣可將編譯程序分為二個相互獨立部分。㈠編譯程序前端(TheFrontEnd)組成：詞法分析器、語法分