編譯原理基礎(chǔ)課件

引言1.1從面向機器的語言到面向人類的語言

計算機的硬件只能識別由0、1字符串組成的機器指令序列，即機器指令程序。在計算機剛剛問世的年代，人們只能向計算機輸入機器指令程序來指揮它進行簡單的數(shù)學(xué)計算。機器指令程序是最基本的計算機語言。由于機器指令程序不易理解，用它編寫程序既困難又容易出錯，于是人們就用容易記憶的符號來代替0、1字符串。用符號表示的指令被稱為匯編指令，匯編指令的集合被稱為匯編語言，由匯編語言編寫的指令序列被稱為匯編語言程序。雖然匯編指令比機器指令在閱讀和理解上有了長足進步，但是二者之間并無本質(zhì)區(qū)別，它們均要求程序設(shè)計人員根據(jù)指令工作的方式思考、解決問題。因此，人們稱這類語言為面向機器的語言或低級語言。

隨著計算機應(yīng)用需求的不斷增長，人們希望能有功能更強、抽象級別更高的語言來支持程序設(shè)計，于是就產(chǎn)生了面向各類應(yīng)用的程序設(shè)計語言。這些語言的共同特征是便于人類的理解與使用，因此被稱為面向人類的語言或高級語言。表1.1列出了幾種面向機器和面向人類的語言及其表現(xiàn)形式。表1.1面向機器和面向人類語言舉例分類語言表現(xiàn)形式舉例面向機器機器指令0000001111110000匯編指令addsi,ax

面向人類通用程序設(shè)計語言x:=a+b;sort(list);ifcthenaelseb;數(shù)據(jù)查詢語言selectid_no,namefromstudent_table;形式化描述語言E:E'+'E|E'*'E|id;1．通用程序設(shè)計語言通用程序設(shè)計語言是繼匯編語言之后發(fā)展起來的應(yīng)用最廣的一類語言，如人們常用的FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等語言。這類語言的特征是：語言結(jié)構(gòu)符合人類的思維特征，如直接使用表達式進行數(shù)學(xué)運算；具有很高抽象程度，如引入過程與類等機制；程序設(shè)計中強調(diào)邏輯過程，即程序員要考慮事情的前因后果，不但要設(shè)計做什么，還要考慮怎么做，如條件或循環(huán)的判斷等。2．數(shù)據(jù)查詢語言與通用程序設(shè)計語言相比，數(shù)據(jù)查詢語言的抽象程度更高，它只要求程序員具有清晰的邏輯思維能力，設(shè)計好做什么，而忽略怎么做這樣的實現(xiàn)細節(jié)，從而使得對大量復(fù)雜數(shù)據(jù)的處理變得輕松簡單。3．形式化描述語言形式化描述語言的代表之一是編譯器構(gòu)造中常用的工具YACC的語言。這類語言的核心部分是基于數(shù)學(xué)基礎(chǔ)的產(chǎn)生式，設(shè)計人員只需利用產(chǎn)生式描述語言結(jié)構(gòu)的文法，就可以構(gòu)造出識別該語言結(jié)構(gòu)的識別器。4．其他面向特定應(yīng)用領(lǐng)域的語言隨著計算機應(yīng)用領(lǐng)域的不斷拓展，先后出現(xiàn)了多種面向特定應(yīng)用領(lǐng)域的高級語言，如面向互聯(lián)網(wǎng)應(yīng)用的HTML、XML，面向計算機輔助設(shè)計的MATLAB，面向集成電路設(shè)計的VHDL、Verilog，面向虛擬現(xiàn)實的VRML等等。這些形形色色、多不勝數(shù)的計算機語言推動了計算機應(yīng)用的飛速發(fā)展，使得計算機成為人類生活中不可缺少的重要部分。1.2語言之間的翻譯

盡管人類可以借助高級語言與計算機進行交往，但是計算機硬件真正能夠識別的語言只是0、1組成的機器指令序列，這就需要在高級語言和機器語言之間建立若干橋梁，將高級語言逐步過渡到機器語言。換句話說，我們需要若干“翻譯”，把人類懂的高級語言翻譯成計算機懂的機器語言。由于應(yīng)用的不同，語言之間的翻譯是多種多樣的。圖1.1給出了一些常見的語言之間的翻譯模式。在圖1.1中，語言分為三個層次：高級語言、匯編語言、機器語言。雖然匯編語言和機器語言同屬于低級語言，但是由于從匯編語言到可直接執(zhí)行的機器指令之間也需要一層翻譯，所以把它們分為不同的層次。設(shè)分別有兩個高級語言L1和L2，兩個匯編語言A1和A2，以及兩個機器語言M1和M2。

高級語言之間的翻譯，一般被稱為轉(zhuǎn)換，如FORTRAN到Ada的轉(zhuǎn)換等，或者被稱為預(yù)處理，如SQL到C/C++的預(yù)處理等。高級語言可以直接翻譯成機器語言，也可以翻譯成匯編語言，這兩個翻譯過程被稱為編譯。從匯編語言到機器語言的翻譯被稱為匯編。高級語言是與具體計算機無關(guān)的，而匯編語言和機器語言均是與計算機有關(guān)的，因此，若將一個匯編語言匯編為可在另一機器上運行的機器指令，則稱為交叉匯編，而建立在交叉匯編基礎(chǔ)之上的編譯模式，如首先將L2編譯成A2，再將A2匯編為M1，有時也被稱為交叉編譯。上述這些翻譯模式一般被認為是正向工程。在一些特定情況下需要逆向工程，如把機器語言翻譯成匯編語言，或者把匯編語言翻譯成高級語言，分別稱它們?yōu)榉磪R編和反編譯。值得一提的是，反編譯是一件十分困難的事情。承擔(dān)這些語言之間翻譯任務(wù)的軟件，一般被稱為某某程序或某某器，為簡單起見，本教材統(tǒng)一采用后一種方式，即將這些翻譯軟件稱為轉(zhuǎn)換器、編譯器等。圖1.1語言之間的翻譯模式

上述語言之間的翻譯雖然各不相同，但基本方法，特別是對源語言的分析方法是相同的。由于高級語言之間的轉(zhuǎn)換和匯編語言到機器語言的翻譯過程中，源程序和目標程序之間的結(jié)構(gòu)變化不大，其處理方法相對編譯器來講一般比較簡單，因此我們以編譯器為例，討論把高級語言中應(yīng)用最廣的通用程序設(shè)計語言翻譯成匯編語言程序所涉及的基本原理、技術(shù)和方法。這些原理、技術(shù)和方法也同樣適用于其他各類翻譯器的構(gòu)造，同時有些技術(shù)和方法也可以被用于其他軟件設(shè)計。在后繼討論中，我們約定源程序是指通用程序設(shè)計語言程序，而目標程序是指匯編語言程序。1.3編譯器與解釋器

編譯器(Compiler)一詞是GraceMurrayHopper在20世紀50年代初提出來的，而被公認為最早的編譯器是50年代末研制的FORTRAN編譯器。從用戶的觀點來看，編譯器是一個黑盒子，如圖1.2(a)所示(為簡明起見，圖中忽略了對目標程序的匯編過程)。源程序的翻譯和翻譯后程序的運行是兩個獨立的不同階段。首先是編譯階段，用戶輸入源程序，經(jīng)過編譯器的處理，生成目標程序。然后是目標程序的運行階段，根據(jù)目標程序的要求進行適當?shù)臄?shù)據(jù)輸入，最終得到運行結(jié)果。

解釋器采用另一種方式翻譯源程序。它不像編譯器那樣，把源程序的翻譯和目標程序的運行分割開來，而是把翻譯和運行結(jié)合在一起進行，翻譯一段源程序，緊接著就執(zhí)行它。這種方式被稱為解釋。在計算機應(yīng)用中，凡是可以采用編譯方式的地方，幾乎都可以采用解釋的方式，圖1.2(b)是一個解釋器的工作模型。

假設(shè)有源程序：

read(x);write("x=",x);

則編譯器的輸入是此源程序。目標程序的輸入如果是3，則輸出是x=3。而對于解釋器，則輸入端既包括上述源程序，又包括3，其輸出同樣是x=3。

可以看出，編譯器的工作相當于在翻譯一本原著，計算機運行編譯后的目標程序，相當于閱讀一本譯著，原著(或原作者)和譯著者并不在場，主角是譯著。而解釋器的工作相當于在進行同聲翻譯，計算機運行解釋器，相當于我們直接通過翻譯聽外賓講話，外賓和翻譯均需到場，主角是翻譯。圖1.2編譯器與解釋器工作方式的對比(a)編譯器的工作方式；(b)解釋器的工作方式

解釋器與編譯器的主要區(qū)別在于：運行目標程序時的控制權(quán)在解釋器而不在目標程序。因此，與編譯器相比，解釋器有以下兩個優(yōu)點:(1)具有較好的動態(tài)特性:運行時，由于源程序也參與其中，因此數(shù)據(jù)對象的類型可以動態(tài)改變，并允許用戶對源程序進行修改，且可提供較好的出錯診斷，從而為用戶提供了交互式的跟蹤調(diào)試功能。

(2)具有較好的可移植性:解釋器一般也是用某種程序設(shè)計語言編寫的，因此，只要對解釋器進行重新編譯，就可以使解釋器運行在不同的環(huán)境中。

由于解釋器的動態(tài)特性和可移植特性，在有些特定的應(yīng)用中必須采用解釋的方法。典型的例子是數(shù)據(jù)庫系統(tǒng)中的動態(tài)查詢語句和Java的字節(jié)代碼。前者利用了解釋器的動態(tài)特性，在程序運行時根據(jù)輸入動態(tài)生成查詢語句，然后解釋執(zhí)行。后者利用了解釋器的可移植特性，可在任何機器上對字節(jié)代碼進行解釋執(zhí)行，習(xí)慣上稱之為Java虛擬機。但是，由于解釋器是把源程序的翻譯和目標程序的運行過程結(jié)合在一起，因此，與編譯器相比，它在運行時間和空間上的損失較大，運行效率低：(1)時間上:在運行過程中，解釋器要時刻檢查源程序。例如，每一次引用變量，都要進行類型檢查，甚至需要重新進行存貯分配，從而大大降低了程序的運行速度。用早期BASIC編寫的源程序，編譯后運行和解釋執(zhí)行的時間比約為1:10。

(2)空間上：執(zhí)行解釋時，不但要有用戶程序的運行空間，而且解釋器和相應(yīng)的運行支撐系統(tǒng)也要占據(jù)內(nèi)存空間。

由于編譯和解釋的方法各有特點，因此，現(xiàn)有的一些編譯系統(tǒng)既提供編譯的方式，也提供解釋的方式，或者是一種中和的方式。例如在Java虛擬機上發(fā)展的一種新技術(shù)，稱為compiling-just-in-time，它的基本思想是，當一段代碼第一次運行時，首先對它進行編譯，而在其后的運行中不再進行編譯。這種方法特別適合一段代碼多次運行的情況，而對于大多數(shù)代碼僅運行一次的情況并不適用。從翻譯的角度來講，兩種方式所涉及的基本原理、方法與技術(shù)是相似的。1.4編譯器的工作原理與基本組成1.4.1通用程序設(shè)計語言的主要成份通用程序設(shè)計語言的典型特征之一是抽象，其抽象程度是以程序設(shè)計語言所支持的基本結(jié)構(gòu)為特征的，可以大致劃分為三種形式：過程、模塊（抽象數(shù)據(jù)類型，ADT）和類。以過程為基本結(jié)構(gòu)的程序設(shè)計語言的典型代表有C、Pascal等；以ADT為基本結(jié)構(gòu)的程序設(shè)計語言的典型代表是Ada83；而以類為基本結(jié)構(gòu)的程序設(shè)計語言包括當前流行的C++、Java和Ada95等。這三種形式經(jīng)過了一個演變過程，每一次演變都使得程序設(shè)計語言的抽象程度得到一次提高，同時也為這些程序設(shè)計語言的編譯器提出了新的要求。

類概念的引入，為利用程序設(shè)計語言構(gòu)造類型提供了真正的支持，也是面向?qū)ο蟪绦蛟O(shè)計語言的重要特征之一。程序設(shè)計語言提供的機制與程序設(shè)計的風(fēng)格有著密切關(guān)系，以過程為基本抽象的程序設(shè)計語言支持的是過程式的程序設(shè)計范型（paradigm），以類為基本抽象的程序設(shè)計語言支持的是面向?qū)ο蟮某绦蛟O(shè)計范型，以ADT為基本抽象的程序設(shè)計語言介于二者之間，一般被認為是面向過程的語言，但也被認為是基于對象的語言。有些面向?qū)ο蟮某绦蛟O(shè)計語言是由過程式的語言發(fā)展而來的，如C++、Ada95等，它們實質(zhì)上是支持多范型的程序設(shè)計語言。

由于篇幅和授課時間所限，后繼章節(jié)均以最簡單的、以過程為基本結(jié)構(gòu)的程序設(shè)計語言為背景進行討論。因為無論何種形式的程序設(shè)計語言，均是由聲明和操作這樣兩個基本元素構(gòu)成的，所不同的是聲明和操作的范圍和復(fù)雜程度不同。以過程為基本結(jié)構(gòu)的程序設(shè)計語言的特征是把整個程序作為一個過程。過程的定義由兩類語句組成：聲明性語句和操作性語句。一般來講，聲明性語句提供所操作對象的性質(zhì)，如數(shù)據(jù)類型、值、作用域等。而操作性語句確定操作的計算次序，完成實際操作。過程由過程頭和過程體兩個部分組成，對應(yīng)的聲明性和操作性語句用例1.1加以說明。例1.1有一Pascal的過程如下所示：(1)proceduresample(y:integer);(2)varx:integer;(3)beginx:=y;(4)ifx>100thenx:=0(5)end;(1)是過程頭，它是一個聲明性的語句，為使用者提供調(diào)用信息，包括過程名、參數(shù)、返回值(如果有的話)等。

(2)~(5)是過程體，它是一個語句序列，語句序列中既包括聲明性語句也包括操作性語句。(2)是聲明性語句，而(3)~(5)是操作性語句。對于編譯器來講，它對聲明性語句的處理一般是生成相應(yīng)的環(huán)境(存儲空間)，而對操作性語句則是生成此環(huán)境中的可執(zhí)行代碼序列。為了便于編譯器的處理，操作性語句中使用的每個操作對象，均應(yīng)在使用前進行聲明，即遵循先聲明后引用的原則。1.4.2以階段劃分編譯器對于自然語言(如英語)的翻譯，經(jīng)歷這樣幾個主要階段:識別單詞、識別句子、理解意思、譯成中文并對譯文進行合理的修飾。編譯器對于計算機語言的翻譯，也同樣需要經(jīng)歷這樣幾個階段:首先進行詞法分析，識別出合法的單詞；其次進行語法分析，得到由單詞組成的句子結(jié)構(gòu)；然后進行語義分析，并且生成目標程序。為了使翻譯工作更好地進行，編譯器往往在語義分析之后先生成所謂的中間代碼，并且可以對中間代碼進行優(yōu)化，最后從優(yōu)化后的中間代碼生成目標程序。每個階段的工作在邏輯上由圖1.3中的一個程序模塊承擔(dān),其中的符號表管理器和出錯處理器貫穿編譯器各個階段，為了統(tǒng)一，也把它們稱為編譯的兩個階段。圖1.3編譯器的階段1.4.3編譯器各階段的工作我們以僅包含一條聲明語句和一條可執(zhí)行語句的Pascal源程序為例，說明編譯器各個階段處理的全過程。例中每個前一階段的輸出是后一階段的輸入。為了便于理解，敘述采用的是邏輯的和示意性的方法，其中表示變量名稱的標識符用id1、id2、id3表示，目的是強調(diào)標識符的內(nèi)部表示與輸入序列的區(qū)別，而程序中的關(guān)鍵字和特殊符號以及像60這樣的數(shù)字字面量等，均采用外部原來的表示，目的是為了直觀。

例1.2

有一Pascal源程序語句如下所示：

varx,y,z:real;x:=y+z*60;

編譯器從左到右掃描輸入，首先進行的是詞法分析。詞法分析器的輸入是源程序，輸出是識別出的記號流。varx,y,z:real;x:=y+z*60;詞法分析varid1,id2,id3:real;id1:=id2+id3*60;

語法分析器以詞法分析器返回的記號流為輸入構(gòu)造句子的結(jié)構(gòu)，并以樹的形式表示出來，稱之為語法樹。語法分析

語義分析器根據(jù)語法分析器構(gòu)造的語法樹，進行適當?shù)恼Z義處理。對于聲明語句，進行符號表的查填。下述符號表部分的內(nèi)容中，每一行存放一個符號的信息，第一行存放標識符x的信息，它的類型是real，為它分配的地址是0。第二行存放y的信息，它的類型是real，為它分配的地址是4。由此可知，我們?yōu)槊總€實型數(shù)分配一個大小為四個單位的存儲空間。對于可執(zhí)行語句，檢查結(jié)構(gòu)合理的表達式運算是否有意義。由于變量x，y，z均是real，而60被認為是integer，因此，語義檢查時需要進行把60轉(zhuǎn)換為60.0的處理。反映在語法樹上，就是增加了一個新節(jié)點itr?(將整型數(shù)轉(zhuǎn)換為實型數(shù))。語義分析

由于聲明語句并不生成可執(zhí)行的代碼，所以到此為止，對聲明語句的處理已經(jīng)完成。下邊開始的中間代碼生成，僅涉及源程序中的賦值句。中間代碼生成器對語法樹進行遍歷，并生成可以順序執(zhí)行的中間代碼序列。最常用的中間代碼形式是四元式，它的基本形式為:(序號)(op，arg1，arg2，result)

操作符左操作數(shù)右操作數(shù)結(jié)果

操作符也被稱為算符，操作數(shù)也被稱為算子。上式表示第(序號)個四元式，arg1和arg2進行op運算，結(jié)果存進result。如四元式(+，x，y，T)表示的運算為T:=x+y，而四元式(:=，x，，T)表示的運算為T:=x。為了表示上的直觀，有時也把四元式直接表示為T:=x+y和T:=x的形式。這似乎與程序設(shè)計語言中的表達式在表示上沒有什么區(qū)別，因此有時需要根據(jù)上下文來確定是算術(shù)表達式還是四元式。另外，四元式的一個特征是賦值號右邊最多只有一個操作符和兩個操作數(shù)。

中間代碼生成

(1)?(itr, 60, , T1)(2)?(*, id3, T1, T2)(3)?(+, id2, T2, T3)(4)?(:=, T3, , id1)

下一步工作就可以對中間代碼進行優(yōu)化了。分析上邊的4個四元式可以看出，60是編譯時已經(jīng)知道的常數(shù)，所以把它轉(zhuǎn)換成60.0的工作可以在編譯時完成，沒有必要生成(1)號四元式。再看(4)號四元式，它的作用僅是把T3的值傳給id1(這樣的運算被稱為復(fù)寫傳播)，不難看出，這條四元式也是多余的。經(jīng)過優(yōu)化后，4個四元式減少為兩個。(1)?(*, id3,60.0,T1)(2)?(+, id2, T1, id1)中間代碼優(yōu)化

最后從優(yōu)化后的中間代碼生成目標代碼。這里的目標代碼是匯編指令，其中MOVF、MULF和ADDF分別表示浮點數(shù)的傳送、乘和加操作。對于二元運算MULF和ADDF，操作形式為OPsource，target，它表示target:=sourceOPtarget，即sorce與target進行OP運算，結(jié)果存進target。對于一元運算MOVF，操作形式為MOVFsource，target，它表示target:=source，即將source中的內(nèi)容移進target中。MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1 目標代碼生成1．詞法分析詞法分析器根據(jù)詞法規(guī)則識別出源程序中的各個記號(token)，每個記號代表一類單詞(lexeme)。源程序中常見的記號可以歸為以下幾大類，其中每一類均可再細分。

(1)關(guān)鍵字:如var、begin、end...，它們在源程序中均有特定含義，一般不作它用，在這種情況下也被稱為保留字。

(2)標識符:如x、y、z、sort...，它們在源程序中被用作變量名、過程名、類型名和標號等所有對象的名稱。(3)字面量:如60、"XidianUniversity"...，一般表示常數(shù)或字符串常量，它們也可以被細分為數(shù)字字面量、字符串字面量等。

(4)特殊符號:如":="、"+"、";"...，它們在源程序中均有特定含義，根據(jù)它們的作用，也可以被細分為運算符、分隔符等。

2．語法分析語法分析器根據(jù)語法規(guī)則識別出記號流中的結(jié)構(gòu)(短語、句子等)，并構(gòu)造一棵能夠正確反映該結(jié)構(gòu)的語法樹。以后我們會看到，除了反映語言結(jié)構(gòu)外，有些語法樹也反映語法分析的關(guān)鍵步驟。因此，語法樹可以是隱含的，也可以確有其“樹”。語法樹的數(shù)據(jù)結(jié)構(gòu)一般采用典型的二叉樹結(jié)構(gòu)，因為任何形態(tài)的樹均可以轉(zhuǎn)化為二叉樹。

3．語義分析語義分析器根據(jù)語義規(guī)則對語法樹中的語法單元進行靜態(tài)語義檢查，如類型檢查和轉(zhuǎn)換等，其目的在于保證語法正確的結(jié)構(gòu)在語義上也是合法的。當分析到聲明語句時，語義分析器將相應(yīng)的環(huán)境信息記錄在符號表中，以便在后繼操作語句中使用。如例1.2中的三個變量都是real類型。而60被默認為integer類型。不同類型的數(shù)所占用的存貯空間不同，例如real類型占用4個存貯單元，則三個變量被分配的地址分別為0、4、8。當分析到操作性語句時，可以根據(jù)符號表中的信息判斷各操作數(shù)是否合法，由于三個變量均為real，而60是integer類型，因此，此時的語義分析要增加一個操作itr，把60轉(zhuǎn)換成60.0。

4．中間代碼生成中間代碼生成器根據(jù)語義分析器的輸出生成中間代碼。中間代碼可以有若干種形式，它們的共同特征是與具體機器無關(guān)。最常用的一種中間代碼是三地址碼，它的一種實現(xiàn)方式是四元式。三地址碼的優(yōu)點是便于閱讀、便于優(yōu)化。

值得一提的是，無論是對于解釋器還是編譯器，到中間代碼生成以前的各階段(即完成語義分析)是完全一樣的。語義分析完成以后，語法樹已經(jīng)形成，執(zhí)行計算的基本元素已經(jīng)具備，因此，對于解釋器來講，此時就可以直接形成計算步驟并且進行計算，沒有必要再做中間代碼生成和其后的工作?；蛘?，解釋器在語義分析完成以后，生成某種中間代碼，統(tǒng)一對此中間代碼進行解釋執(zhí)行。由于語法樹和中間代碼均不依賴于任何機器，因此解釋器是可移植的。典型的例子是Java字節(jié)代碼與Java虛擬機。

5．中間代碼優(yōu)化優(yōu)化是編譯器的一個重要組成部分，由于編譯器將源程序翻譯成中間代碼的工作是機械的、按固定模式進行的，因此，生成的中間代碼往往在時間上和空間上有很大浪費。當需要生成高效目標代碼時，就必須進行優(yōu)化。

優(yōu)化過程可以在中間代碼生成階段進行，也可以在目標代碼生成階段進行。由于中間代碼是不依賴于機器的，在中間代碼一級考慮優(yōu)化可以避開與機器有關(guān)的因素，把精力集中在對控制流和數(shù)據(jù)流的分析上。因此，優(yōu)化的大部分工作在目標代碼生成之前進行，只有少部分與機器有關(guān)的優(yōu)化(如局部的優(yōu)化或寄存器的分配等)工作放在目標代碼生成時進行。優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但是，優(yōu)化后的代碼序列在占用的空間上和程序執(zhí)行的時間上都更節(jié)省、更有效。

6．目標代碼生成目標代碼生成是編譯器的最后一個階段。在生成目標代碼時要考慮以下幾個問題：計算機的系統(tǒng)結(jié)構(gòu)、指令系統(tǒng)、寄存器的分配以及內(nèi)存的組織等。編譯器生成的目標程序代碼可以有多種形式。

(1)匯編語言形式(AssemblyLanguageFormat):編譯器生成匯編語言形式的代碼序列。一般來講，生成匯編指令代碼比生成二進制代碼序列在處理上要簡單且易讀，而且，由于匯編語言仍然是符號形式的，所以特別便于實現(xiàn)交叉編譯。它的弱點是編譯之后還要經(jīng)過一次匯編。(2)可重定位二進制代碼形式(RelocatableBinaryFormat):這實際上是編譯器常采用的一種目標代碼。編譯器生成二進制代碼模塊，模塊內(nèi)地址以模塊首地址相對尋址，經(jīng)過鏈接程序進行鏈接。鏈接時還需把程序中所引用的預(yù)定義標準例程和其它已編譯過的模塊包括進來，最后形成一個可直接運行的代碼序列。(3)內(nèi)存形式(Memory-ImageFormat):編譯器生成的代碼序列直接被裝入原編譯器所在的位置并被立即執(zhí)行，反映在外部也就是編譯后馬上運行。這類形式在英文中也被稱為Load-and-Go。由于這種形式不生成以文件形式存放在磁盤上的目標代碼，也沒有被鏈接的過程，因而這種形式特別適合初學(xué)者或在程序的調(diào)試階段使用。它的弱點是運行一次就需要編譯一次。由于這三種形式各有其它形式無法替代的特點，有些編譯器同時提供這三種或者其中兩種形式，用戶可以根據(jù)需要選擇使用。7．符號表管理符號表的作用是記錄源程序中符號的必要信息，并加以合理組織，從而在編譯器的各個階段能對它們進行快速、準確的查找和操作。符號表中的某些內(nèi)容甚至要保留到程序的運行階段。

8．出錯處理由于例1.2中給出的是一個沒有錯誤的源程序，因而出錯處理是一個還未涉及的階段。但是，用戶編寫的源程序中往往會有一些錯誤，這些錯誤大致被分為靜態(tài)錯誤和動態(tài)錯誤兩類。所謂動態(tài)錯誤，是指源程序中的邏輯錯誤，它們發(fā)生在程序運行的時候，也被稱為動態(tài)語義錯誤，如變量取值為零時被作為除數(shù)，數(shù)組元素引用時下標出界等。靜態(tài)錯誤又可分為語法錯誤和靜態(tài)語義錯誤。語法錯誤是指有關(guān)語言結(jié)構(gòu)上的錯誤，如單詞拼寫錯、表達式中缺少操作數(shù)、begin和end不匹配等。靜態(tài)語義錯誤是指分析源程序時可以發(fā)現(xiàn)的語言意義上的錯誤，如加法的兩個操作數(shù)中一個是整型變量名，而另一個是數(shù)組名等。

靜態(tài)錯誤應(yīng)該在編譯的不同階段被檢查出來，并且采用適當?shù)牟呗孕迯?fù)它們，使得分析過程能夠繼續(xù)下去，直到源程序的結(jié)束。遇到一個錯誤就使編譯器停止工作的做法是不負責(zé)任的，也是用戶難以接受的。1.4.4編譯器的分析/綜合模式對于編譯器的各個階段，邏輯上可以把它們劃分為兩個部分，即分析部分和綜合部分。從詞法分析到中間代碼生成各階段的工作稱為分析，而以后直到目標代碼生成各階段的工作被稱為綜合。分析部分也被稱為編譯器的前端，綜合部分也被稱為編譯器的后端。圖1.4所示是一個理想的分析/綜合模式。在這里，中間代碼起了分水嶺的作用，由于中間代碼是與機器無關(guān)的，因此它把編譯器分成了與機器有關(guān)和無關(guān)的兩部分，從而提高了編譯器開發(fā)和維護的效率。例如，對于一種程序設(shè)計語言，可以開發(fā)一個共同的前端，再針對不同的機器設(shè)計不同的后端，并且語言結(jié)構(gòu)的修改往往只涉及前端的維護。

也可以針對某一機器開發(fā)一個后端，而對于不同的語言設(shè)計各自的前端，生成同一種中間代碼，從而得到一個機器上的若干個編譯器。當然，由于語言之間的差異，這些想法在實現(xiàn)上還存在著許多困難。另外，編譯器和解釋器的區(qū)別，也往往是形成中間代碼之后開始：編譯器從中間代碼生成目標代碼，而解釋器解釋中間代碼得到運行結(jié)果。值得注意的是，編譯器和解釋器所需的中間代碼形式可能有所不同。圖1.4編譯器的分析/綜合模式1.4.5編譯器掃描的遍數(shù)在圖1.3所示的編譯器模型中，編譯器的每個階段都是對以某種形式表示的完整程序進行一遍分析。我們把每個階段將程序完整分析一遍的工作模式稱為一遍掃描。例如，詞法分析器對輸入源程序進行第一遍掃描，把源程序分解成一串記號流，并進行必要的符號登記工作(由符號表管理器處理)。語法分析器進行第二遍掃描，它以詞法分析器輸出的記號流為輸入，識別出語言結(jié)構(gòu)，如賦值語句、過程定義等，并建立和輸出對應(yīng)的語法樹。依此類推，最后生成目標程序。但是，這樣一個階段對應(yīng)一遍掃描的工作方式只是邏輯上的。由于多次掃描的方式需要大量的存儲空間存放中間表示，并且也會增加一些不必要的輸入輸出操作，因此，編譯器往往是把若干個階段的工作結(jié)合起來，對應(yīng)一遍掃描，從而減少對程序的掃描遍數(shù)。原理上希望掃描的遍數(shù)越少越好，這就必須保證兩點：(1)為編譯器的運行提供足夠大的空間。由于若干階段的工作合并在一遍中完成，所以處理各階段工作的程序都隨時準備運行，而且各階段所需的信息也要同時放在內(nèi)存中。隨著計算機硬件技術(shù)的發(fā)展，空間已不成為問題。(2)在語言的設(shè)計上和編譯技術(shù)上為減少掃描遍數(shù)提供支持。在語言設(shè)計上，盡量使得編譯器可以僅從已掃描過的內(nèi)容就得到足夠的信息。例如，許多程序設(shè)計語言都要求對標識符先聲明后引用，這就保證了任何一個標識符出現(xiàn)時就可以確定它的性質(zhì)，而不需要掃描標識符以后的程序部分。另外，也可以采用一些專門技術(shù)來達到類似目的。最典型的例子是轉(zhuǎn)移語句的翻譯。大多數(shù)程序設(shè)計語言允許向前轉(zhuǎn)移的goto語句，而遇到goto時，其具體轉(zhuǎn)向并不知道，因而無法確定此語句的轉(zhuǎn)向地址。對這種情況，可以采用一種稱為“拉鏈/回填”的技術(shù)，把生成的轉(zhuǎn)移指令中確定不了的轉(zhuǎn)移地址先暫時空起，等到地址確定后再回填進去。

雖然從編譯器工作效率的角度講，一遍掃描是最好的。但是，由于各種原因，若干遍掃描也是不可少的。例如，由于中間代碼界定了前端和后端，并且兩個部分的工作有很大區(qū)別，因此，往往至少將前端作為一遍掃描。另外，為了生成高質(zhì)量的目標代碼，需要對中間代碼進行優(yōu)化，而全局性的控制流和數(shù)據(jù)流分析也應(yīng)該是對中間代碼的一遍掃描?？傊?，對一個具體的編譯器，要確定用幾遍掃描來完成，需要綜合考慮各種因素，從中取得最佳折中。1.5編譯器的編寫

編譯器本身也是一個程序，那么用什么編寫編譯器呢?早期人們用匯編語言編寫編譯器。眾所周知，人工可以編寫出效率很高的程序，但由于編譯器本身是一個十分復(fù)雜的系統(tǒng)(如早期的FORTRAN用了18人年才完成)，而用匯編語言編寫編譯器的效率很低，往往給實現(xiàn)帶來很大困難。因此，除了特別需要，人們早已不再用匯編語言編寫完整的編譯器?，F(xiàn)在常用通用程序設(shè)計語言編寫編譯器，它的效率比匯編語言要高得多。不過，用單純程序設(shè)計的方法來對付編譯器這樣的龐然大物也顯得不夠。

為此，需要一些專門的編譯器編寫工具來支持編譯器某些部分的自動生成。比較成熟和通用的工具有詞法分析器生成器和語法分析器生成器，如被廣泛應(yīng)用的LEX和YACC。另外，還有一些工具，如語法制導(dǎo)翻譯工具(用于語義分析)、自動的代碼生成器(用于中間代碼生成和目標代碼生成)和數(shù)據(jù)流工具(用于優(yōu)化)等。這些工具的共同特點是，僅需要對語言相應(yīng)部分的特征進行描述，而把生成算法的過程隱蔽起來，同時所生成的部分可以很容易地并入到編譯器的其它部分中。因此，這些工具往往與某程序設(shè)計語言聯(lián)系在一起，如與LEX和YACC聯(lián)系的程序設(shè)計語言是C。1.6本章小結(jié)

編譯原理是一門理論和實踐并重的課程，大部分同學(xué)都會感到學(xué)習(xí)這門課程十分困難。關(guān)鍵問題是應(yīng)該掌握好的學(xué)習(xí)方法，在此我們強調(diào)兩點：

①牢固掌握基本概念，這要進行大量的閱讀，并通過閱讀加深理解；

②靈活使用基本方法，這要在閱讀理解的基礎(chǔ)上做好習(xí)題和上機作業(yè)。(1)語言的翻譯：

①面向人類的高級語言，如通用程序設(shè)計語言Pascal、C/C++、Java、Ada以及一些有特定應(yīng)用領(lǐng)域的語言等；

②面向機器的低級語言，如匯編語言和二進制機器代碼等；

③編譯器與匯編器，把高級語言翻譯成低級語言的程序被稱為編譯器(或解釋器)，把匯編語言翻譯成機器代碼的程序被稱為匯編器。編譯器與解釋器，編譯器首先把源代碼翻譯成目標代碼，然后執(zhí)行目標代碼，解釋器一邊翻譯源代碼，一邊執(zhí)行解釋后的代碼。(2)編譯器的基本組成：以階段劃分編譯器，階段包括詞法分析、語法分析、語義分析、中間代碼生成、中間代碼優(yōu)化、目標代碼生成、符號表管理以及出錯處理。

(3)編譯器的分析－綜合模式：把編譯器分為前端和后端。前端稱為分析，它的輸出與機器無關(guān)；后端稱為綜合，以前端的輸出為輸入，其輸出與具體機器指令密切相關(guān)。編譯器的這種劃分方式，有利于編譯器的開發(fā)、維護與移植。2.1詞法分析中的若干問題2.1.1記號、模式與單詞自然語言中的句子通常由一個個單詞和標點符號組成，可以根據(jù)其在句子中的作用，將它們劃分為動詞、名詞、形容詞、標點符號等不同的種類。程序設(shè)計語言與此相類似，組成語句的基本單元也可根據(jù)其在句子中的作用分類。最基本分類有四類：

(1)關(guān)鍵字(保留字)：這類單詞在程序設(shè)計語言中有固定的意義，如begin、end、while等。若在程序設(shè)計語言中不允許用它們再表示其他的意思，則這類單詞也被稱為保留字。(2)標識符：標識符是程序設(shè)計語言中最大的一個類別，它的作用是為某個實體起一個名字，以便于今后稱呼(引用)，如draw_line、sort等?？梢杂脴俗R符來命名的實體包括類型、變量、過程、常量、類、對象、程序包、標號等，即類型名、變量名、過程名、常量名等。(3)字面量：字面量是指直接以其字面所表示的常量，如25、true、"Thisisastring"等。值得注意的是，字面量與常量是兩個不同的概念，常量可以是一個字面量(直接表示)，也可以是一個常量名(命名表示)。例如可以在Pascal中聲明：constmax_length=25，顯然25是一個常量，max_length也是一個常量，我們稱25為字面量，而不稱max_length為字面量。根據(jù)字面量的內(nèi)容，可以將它們再進行更細的劃分，如常數(shù)字面量(包括整型字面量、實型字面量、枚舉字面量等)、字符串字面量等。(4)特殊符號：程序設(shè)計語言中的特殊符號，類似于自然語言中的標點符號，每個符號在程序設(shè)計語言中均有特殊用途?？梢愿鶕?jù)它們的用途，再細分為算符(如+、、*、/等)、分隔符(如；、”、“等)。顯然，一個單詞究竟是標識符、關(guān)鍵字，還是特殊符號，需要根據(jù)一定的構(gòu)詞規(guī)則來產(chǎn)生和識別。我們將產(chǎn)生和識別單詞的規(guī)則稱為模式(patten)，按照某個模式(規(guī)則)識別出的元素稱為記號(token)，而單詞(lexeme)一詞是指被識別出元素自身的值。

例2.1

對于語句：position:=initial+rate*60，可以識別出下述序列：標識符特殊符號標識符特殊符號標識符特殊符號數(shù)字字面量其中position、initial、rate均被識別為標識符，因為它們均符合同一條規(guī)則，即以字母打頭的字母數(shù)字串。記號至少含有兩個信息：一個是記號的類別，如“標識符”；另一個是記號的值，如“position”。顯然，如果把記號看作是一個類型的話，則單詞就是一個類型中的實例。由于我們總是說識別出一個標識符，而不說識別出一個position或rate，因而將詞法分析器識別出的序列稱為記號流。

記號的類別、模式以及單詞三者之間的關(guān)系可以用表2.1加以說明。其中，const和if分別是被細分的關(guān)鍵字，它們的特點是一個記號類別僅對應(yīng)一個單詞；relation表示關(guān)系運算符；id表示標識符；num表示數(shù)字字面量；literal表示字符串字面量；comment表示注釋，它們的特點是一個記號類別可以對應(yīng)若干個單詞。由于語法分析及其后的階段并不對注釋進行分析，因而可在詞法分析階段中濾掉注釋，即詞法分析器可以不向語法分析器返回comment。而其他的記號，均是源程序中的有效成分，需要返回給語法分析器。表2.1記號、模式與單詞2.1.2記號的屬性從例2.1中已經(jīng)知道，記號至少包含兩個部分：記號類別和記號的其他信息。可以看出，記號的類別唯一標識一類記號，例如所有的關(guān)系運算符均可以由relation來標識，而所有字符串字面量均可以由literal來標識。所以，記號的類別可以被認為是記號的名字或記號的代表，在不引起混淆的情況下，將記號的類別簡稱為記號。記號的其他信息被稱為記號的屬性。例如，num可以取值3.1416，則稱3.1416是num的屬性，而literal可以取值“coredumped”(不含引號)，則稱“coredumped”是literal的屬性。由此可見，記號的類別標識一類記號，而記號的類別加屬性標識一個記號實例。

在計算機內(nèi)部，可以有不同的方式來表示記號的類別和屬性。一般情況下，記號的類別可以用整型編碼或枚舉類型表示，如表2.1中每個記號類別可以用括號中的整型編碼表示，如01表示const，82表示id等。根據(jù)記號類別的不同，記號的屬性的值可以有不同的表示方法。relation的屬性值是一個有限可枚舉集合，可以用每個屬性值在集合中的位置來表示它，如1表示<，2表示<=，依此類推。id的屬性值是一個無限可枚舉集合，因此，只能用每個標識符的原始輸入形式(字符串)來表示，如pi、draw_line等。字面量的屬性根據(jù)情況，其表示方式也不同，如數(shù)字字面量可由轉(zhuǎn)義后的實際值表示，如表示為3.1416而不是“3.1416”，而字符串字面量就無需轉(zhuǎn)義。

例2.2

表達式mycount>25由表2.2的三個記號組成。其中標識符的屬性值也可以由mycount在符號表中的入口(下標)來表示。表2.2記號的表示2.1.3詞法分析器的作用與工作方式詞法分析器是編譯器中唯一與源程序打交道的部分，從某種意義說，也可以被認為是整個編譯器的預(yù)處理器。它的主要工作包括：

(1)濾掉源程序中的無用成分，如注釋、空格、回車等。例如，表2.1中記號的種類除了comment之外，均有一個編碼，表示需要遞交給語法分析器進行后繼的處理，而comment沒有對應(yīng)編碼，表示注釋成分可以過濾掉，不需要遞交，因為語法分析及其之后的各個階段已經(jīng)不再需要它們。(2)處理與具體平臺有關(guān)的輸入。不同的操作系統(tǒng)或相關(guān)軟件構(gòu)成的平臺，對某些特殊符號(如文件結(jié)束符等)可能有不同表示，因此需要在詞法分析階段分情況處理。

(3)識別記號，并交給語法分析器。這是詞法分析器的主要任務(wù)，本章將在各節(jié)中詳細討論。(4)調(diào)用符號表管理器或出錯處理器，進行相關(guān)處理。詞法錯誤是源程序中常見的錯誤，如出現(xiàn)非法字符、拼錯關(guān)鍵字、多或少字符等。值得注意的是，詞法錯誤往往不是由詞法分析器檢查出來的，而是由語法分析器發(fā)現(xiàn)的。這是因為，源程序中除了非法字符之外的大部分字符或字符串，都可以被詞法分析器的某個模式所匹配，從而被識別成一個記號。而這些記號的正確與否，在沒有上下文對照的情況下，是很難判斷的。例如，12x被認為是一個非法的Pascal的標識符，但是，由于12可以被識別整型數(shù)的模式匹配，而x可以被識別標識符的模式匹配，因而詞法分析器會分別識別出一個整型數(shù)和一個標識符，而不是報告一個錯誤。

根據(jù)編譯器的總體需求，詞法分析器在整個編譯器中可以有不同的工作方式。

(1)詞法分析器作為語法分析器的子程序。最常采用，也最容易實現(xiàn)的工作方式是將詞法分析器作為語法分析器的子程序，每當語法分析器需要一個記號時，就調(diào)用詞法分析器，并得到一個識別出的記號。其工作方式如圖2.1所示。

(2)詞法分析器進行單獨的一遍掃描。另一種常用的工作方式，是安排詞法分析器進行單獨的一遍掃描，它以源程序為輸入，輸出是以記號流形式表示的源程序。其工作方式如圖2.2所示。圖2.1作為子程序的詞法分析器

圖2.2詞法分析器進行單獨一遍掃描(3)與語法分析器并行工作的模式。上述兩種詞法分析器的工作模式與語法分析器的關(guān)系均被認為是串行的。為了提高編譯器的效率，可以通過一個隊列，使詞法分析器和語法分析器以生產(chǎn)/消費的形式并行工作。詞法分析器將識別出的記號流輸出到隊列中，語法分析器從隊列中取得記號，只要隊列中有識別出的記號，則詞法分析器和語法分析器就可以同時工作。其工作方式如圖2.3所示。圖2.3并行工作模式2.1.4輸入緩沖區(qū)詞法分析器是編譯器中讀入源程序字符序列的唯一階段，而相當可觀的編譯時間又消耗在詞法分析階段，所以，加快詞法分析是設(shè)計編譯器時要考慮的重要問題之一?？梢酝ㄟ^設(shè)立輸入緩沖區(qū)來加快讀入源程序字符序列的速度。如果使用詞法分析器生成器編寫詞法分析器，則生成器會提供讀入和緩沖輸入序列的例程；如采用通用程序設(shè)計語言編寫詞法分析器，就需要顯式地管理源程序的讀取。

輸入緩沖區(qū)一般被設(shè)計為一塊與磁盤扇區(qū)大小成倍數(shù)關(guān)系的內(nèi)存。若一個扇區(qū)為1024字節(jié)，則輸入緩沖區(qū)可以取1024、4096或8192字節(jié)等。這樣可以保證對緩沖區(qū)的一次輸入所需的I/O操作次數(shù)盡可能少。輸入緩沖區(qū)的安排一般采用單緩沖區(qū)或雙緩沖區(qū)(緩沖區(qū)對)的方式。下邊所介紹的是單緩沖區(qū)方式，它也是詞法分析器生成器FLEX所采用的方式。

圖2.4是一個單緩沖區(qū)的示意圖。有效輸入序列從緩沖區(qū)的起始位置開始存放，最后添加一個特殊標記(此處用#表示)：若緩沖區(qū)一次裝不下整個源程序，它就表示緩沖區(qū)的結(jié)束，否則它緊跟在文件結(jié)束符(eof)之后，表示整個輸入源程序的結(jié)束。用兩個指針c_ptr和f_ptr分別指向當前被識別記號的第一個字符和向前掃描的字符。最初，兩個指針同時指向下一個被識別記號的第一個字符，f_ptr向前掃描，直到某個模式匹配成功。一旦這個記號被確定，f_ptr指向被識別出記號的右端字符，在此記號被處理后，兩個指針都移向該記號之后的下一個字符。在f_ptr向前掃描的過程中，如果遇到文件結(jié)束標志，則表示輸入序列已被處理完。如果遇到特殊標記#，說明緩沖區(qū)中的內(nèi)容需要更新。這時，首先將c_ptr到f_ptr所指的內(nèi)容(不包括特殊標記)移到緩沖區(qū)的起始位置，然后將新的內(nèi)容讀進緩沖區(qū)，最后加上特殊標記。具體算法如下：c_ptrf_ptr圖2.4單緩沖區(qū)procedureget_next_buffer(buffer，start，length)is--start和length是需仍保留在緩沖區(qū)中字符串的起始位置和長度beginiflength>=buffer_size --buffer_size是緩沖區(qū)實際容量

thenreturnerror；

elseforiinlow..low+length1 --low是緩沖區(qū)下界，假設(shè)從0開始

loopbuffer(i):=buffer(start+ilow)； --把剩余的輸入移到緩沖區(qū)頭部

endloop； num_to_read:=buffer_sizelength；

ifnumber_to_read>block_size--block_size應(yīng)是磁盤扇區(qū)的整數(shù)倍

thennumber_to_read:=block_size;endif;read_buffer(buffer，length+low，num_to_read)；

endif；endget_next_buffer；

假設(shè)被掃描的輸入序列的最大長度不超過max_length，則可以選擇buffer_size=block_size+max_length，即緩沖區(qū)的大小是磁盤扇區(qū)大小的整數(shù)倍加上一個最長可能被掃描的輸入序列。這種緩沖技術(shù)能勝任大多數(shù)情況，但在向前被掃描字符個數(shù)超過緩沖區(qū)長度的極端情況下會失效。早期的程序設(shè)計語言通常采用開括號與閉括號的方式標識注釋，如表2.1中的comment，如果程序員不小心忘記書寫閉括號，而詞法分析器的設(shè)計又將comment作為一個完整的記號識別，就會出現(xiàn)被掃描字符個數(shù)超過緩沖區(qū)長度的情況。因此，后來設(shè)計的程序設(shè)計語言大多采用僅有開括號，而默認換行標志為閉括號的注釋方式，如上述算法中的“--”(Ada的注釋方式)或者C++中的“//”，從根本上杜絕了這種極端情況。2.2模式的形式化描述2.2.1字符串與語言從詞法分析的角度看，程序設(shè)計語言是由記號組成的集合，每個記號又是由若干字母按照一定規(guī)則組成的字符串。為了討論的簡單性和準確性，本章對常用的術(shù)語以定義的方式給出。有一點需要強調(diào)，編譯領(lǐng)域的很多名詞術(shù)語的使用并不統(tǒng)一，因此希望讀者掌握“是什么”，而不是“叫什么”。在下述的討論中，我們首先定義一個泛泛的“語言”，然后在此基礎(chǔ)上規(guī)定一個正規(guī)集，而程序設(shè)計語言就是一個正規(guī)集。

定義2.1語言L是有限字母表∑上有限長度字符串的集合。定義2.1明確指出，語言是一個集合，集合中的元素是字符串，并且強調(diào)了兩個有限:①字母表是有限的，即字母表中元素是有限多個；

②字符串的長度是有限的，即字符串中字符個數(shù)是有限多個。這是由于計算機所能表示的字符個數(shù)和字符串的長度都是有限的。

由于字符串的有序性，使得以字符串作為元素的集合具有某些特性。字符串和集合的基本概念和特性，以表格的形式分別列在表2.3和表2.4中。其中，字符串的連接運算是一種新形式的運算，它表示兩個字符串首尾相接，形成一個新的集合。例如，S1="pre"，S2="fix"，則S1S2="prefix"。值得注意的是，集合中連接運算所形成的新集合與交運算形成的新集合完全不同。例如，若L={"pre"，M={"fix"，則L∩M=Φ，而LM={"prefix"。表2.3字符串的基本概念表2.4字符串集合上的基本運算2.2.2正規(guī)式與正規(guī)集定義2.2令Σ是一個有限字母表，則Σ上的正規(guī)式及其表示的集合遞歸定義如下:①ε是正規(guī)式，它表示集合L(ε)=ε；

②若a是Σ上的字符，則a是正規(guī)式，它表示集合L(a)=；

③若正規(guī)式r和s分別表示集合L(r)和L(s)，則

(a)r|s是正規(guī)式，表示集合L(r)∪L(s)；

(b)rs是正規(guī)式，表示集合L(r)L(s)；

(c)r*是正規(guī)式，表示集合(L(r))*；

(d)(r)是正規(guī)式，表示的集合仍然是L(r)。可用正規(guī)式描述的語言稱為正規(guī)語言或正規(guī)集。

定義2.2中①和②規(guī)定了正規(guī)式的基本操作數(shù)或基本正規(guī)式。定義2.2的③給出了正規(guī)式上的三種運算:(a)或運算、(b)連接運算和(c)閉包運算。對于由多個操作數(shù)和多個操作符組成的正規(guī)式，可以利用(d)所給的括號規(guī)定運算的先后次序。如果對或、連接和閉包運算進行如下約定:①三種運算均具有左結(jié)合性質(zhì)；

②運算的優(yōu)先級從高到低順序排列為:閉包運算、連接運算、或運算。則正規(guī)式中不必要的括號可以被省略。例如，(a)|((b)*(c))可以簡化成a|b*c。

例2.3

設(shè)字母表∑={a，b，c}，部分∑上的正規(guī)式和正規(guī)式所表示的正規(guī)集如表2.5所示。表2.5正規(guī)式與它表示的正規(guī)集

正規(guī)集是一個集合，而正規(guī)式是表示正規(guī)集的一種方法。正如不同算術(shù)表達式可以表示同一個數(shù)(如3+5、5+3、2+6等均表示8)一樣，不同正規(guī)式也可以表示同一個正規(guī)集，即正規(guī)式與正規(guī)集之間是多對一的關(guān)系。例2.4令L(x)={a，b}，L(y)={c，d}，則

L(x|y)={a，b，c，d} L(y|x)={a，b，c，d}x|y和y|x表示同一個正規(guī)集。

定義2.3若正規(guī)式P和Q表示了同一個正規(guī)集，則稱P和Q是等價的，記為P=Q。正規(guī)式之間的一些恒等運算，被稱為正規(guī)式的代數(shù)性質(zhì)。表2.6給出了正規(guī)式的若干代數(shù)性質(zhì)。利用這些性質(zhì)，可以對復(fù)雜的正規(guī)式進行化簡，使得可以用最簡單形式的正規(guī)式表示一個集合。而簡單的正規(guī)式意味著其所對應(yīng)的識別器的構(gòu)造也是簡單的。表2.6正規(guī)式的代數(shù)性質(zhì)2.2.3記號的說明表2.1中用自然語言對模式進行了非形式化的描述，例如標識符模式的非形式化描述是“以字母打頭的字母數(shù)字串”。這一描述很不精確，存在一些問題，如哪些符號是字母，哪些符號是數(shù)字，字母數(shù)字串的長度可以是多少等等。由于正規(guī)式是嚴格的數(shù)學(xué)表達式，采用正規(guī)式來描述模式，解決了精確描述模式的問題。另外，從詞法分析器的角度上看程序設(shè)計語言，用正規(guī)式說明的記號是一個正規(guī)集。用正規(guī)式說明記號的公式為：記號=正規(guī)式，可以讀作為“(左邊)記號定義為(右邊)正規(guī)式”，或者“記號是正規(guī)式”。通常，在不引起混淆的情況下，也把說明記號的公式簡稱為正規(guī)式，或者規(guī)則。

例2.5

表2.1中的記號relation、id和num分別是Pascal的關(guān)系運算符、標識符和無符號數(shù)，它們的正規(guī)式表示如下所示：

relation=<|<=|<>|>|>=|=id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)

上述正規(guī)式給出了標識符的精確定義，用自然語言可以描述為“字母是英文26個字母大小寫中任何一個，數(shù)字是十進制阿拉伯數(shù)字中的任何一個，標識符是以字母打頭的、其后可跟隨0個或若干個字母或數(shù)字的字符串”。1．簡化正規(guī)式描述為了簡化正規(guī)式的描述，通?？梢圆捎萌缦碌膸追N正規(guī)式的縮寫形式。

(1)正閉包。若r是表示L(r)的正規(guī)式，則r+是表示(L(r))+的正規(guī)式，且下述等式成立:r+=rr*=r*r，r*=r+|ε+與*具有相同的運算優(yōu)先級和結(jié)合性。

(2)可缺省。若r是正規(guī)式，則(r)?是表示L(r)∪ε的正規(guī)式，且下述等式成立:r?=r|ε(3)字符組。字符組是或關(guān)系的縮寫形式，它把所有存在或關(guān)系的字符集中在[]里面。其中的字符可以有如下兩種書寫方式:

枚舉方式:如[abc]，它等價于a|b|c

分段方式:如[0-9a-z]，它等價于 [0123456789abcdefghijklmnopqrstuvwxyz](4)非字符組。若[r]是一個字符組形式的正規(guī)式，則[^r]是表示∑L(r)的正規(guī)式。例如，若∑=，則L([^abc])={d,e,f,g}。

(5)串。若r是字符連接運算的正規(guī)式，則串"r"與r等價，即r="r"。特別地，ε="",?a="a"。引入串的表示可以避免與正規(guī)式中運算符的沖突。例如："a|b"=a"|"b≠a|b。

2．引入輔助定義式引入輔助定義式的主要目的是為較復(fù)雜、但需要重復(fù)書寫的正規(guī)式命名，并在定義式之后的引用中，用名字代替相應(yīng)的正規(guī)式。所以，輔助定義式實質(zhì)上仍然是正規(guī)式，唯一的區(qū)別是正規(guī)式與外部模式匹配，而輔助定義式不與任何模式匹配。

例2.6

引入正規(guī)式的縮寫形式和輔助定義式后，id和num的正規(guī)式可重寫如下。

char =[a-zA-Z]digit =[0-9]digits =digit+optional_fraction =(.digits)?optional_exponent =(E(+|)?digits)?id =char(char|digit)*num =digitsoptional_fractionoptional_exponent 2.3記號的識別——有限自動機2.3.1不確定的有限自動機(NondeterministicFiniteAutomata，NFA)

定義2.4NFA是一個五元組(5-tuple)M=(S，∑，move，s0，F(xiàn))

其中：

①S是有限個狀態(tài)(state)的集合；

②∑是有限個輸入字符(包括ε)的集合；③move是一個狀態(tài)轉(zhuǎn)移函數(shù)，move(si，ch)=sj表示當前狀態(tài)si下若遇到輸入字符ch，則轉(zhuǎn)移到狀態(tài)sj；

④s0是唯一的初態(tài)(也稱開始狀態(tài))；

⑤F是終態(tài)集(也稱接受狀態(tài)集)，它是S的子集，包含了所有的終態(tài)。

有限自動機是一個抽象的概念，可以用兩種直觀的方式——狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣來表示，這兩種方式分別簡稱為轉(zhuǎn)換圖和轉(zhuǎn)換矩陣。轉(zhuǎn)換圖是一個有向圖，NFA中的每個狀態(tài)對應(yīng)轉(zhuǎn)換圖中的一個節(jié)點；NFA中的每個move函數(shù)對應(yīng)轉(zhuǎn)換圖中的一條有向邊，該有向邊從si節(jié)點出發(fā)，進入sj節(jié)點，字符ch(或ε)是邊上的標記。顯然，NFA的初態(tài)是轉(zhuǎn)換圖中沒有前驅(qū)的節(jié)點，而NFA的終態(tài)在轉(zhuǎn)換圖中用有別于其他節(jié)點的方法表示。例如，若節(jié)點用一個圓圈表示，則終態(tài)節(jié)點可以用一個加粗的圓圈或者雙圈表示。轉(zhuǎn)換矩陣是一個二維數(shù)組，其中每個元素M[si,sj]中的內(nèi)容是從狀態(tài)si到狀態(tài)sj的邊上的標記ch(或ε)。在轉(zhuǎn)換矩陣中，一般以矩陣第一行所對應(yīng)的狀態(tài)為初態(tài)，而終態(tài)需要特別指出。

例2.7

識別由正規(guī)式(a|b)*abb說明的記號的NFA定義如下：

S={0,1,2,3},Σ={a,b}，s0=0,F={3}move={move(0,a)=0,move(0,a)=1,move(0,b)=0,move(1,b)=2,move(2,b)=3}

它的轉(zhuǎn)換圖和轉(zhuǎn)換矩陣表示如圖2.5所示。在轉(zhuǎn)換矩陣中，需指出0是初態(tài)，3是終態(tài)。圖2.5識別(a|b)*abb的NFA(a)轉(zhuǎn)換圖表示的NFA；(b)轉(zhuǎn)換矩陣表示的NFA

例2.8

識別表2.1中記號id、num和relation的轉(zhuǎn)換圖如圖2.6所示。id和num依據(jù)的是例2.6中簡化的正規(guī)式。不難看出，轉(zhuǎn)換圖識別的每一個記號實質(zhì)上是從初態(tài)開始到某個終態(tài)的路徑上的標記。例如，在識別relation的轉(zhuǎn)換圖中，從0開始到2的路徑標記是“<=”，表示在終態(tài)2處識別出一個關(guān)系運算符，語句return(relation,LE)表示此處可以返回記號的種類relation和關(guān)系運算符的值LE(小于等于號)。 圖2.6狀態(tài)轉(zhuǎn)換圖(a)relation的轉(zhuǎn)換圖；(b)id的轉(zhuǎn)換圖；(c)num的轉(zhuǎn)換圖NFA的特點是它的不確定性，即在當前狀態(tài)下，對同一個字符ch，可能有多于一個的下一狀態(tài)轉(zhuǎn)移。不確定性反映在NFA的定義中，就是move函數(shù)是一對多的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點可通過多于一條標記相同字符的邊轉(zhuǎn)移到不同的狀態(tài)；反映在轉(zhuǎn)換矩陣中，就是M[si,sj]中不是一個單一狀態(tài)，而是一個狀態(tài)的集合。

用NFA識別輸入序列的方法是：從NFA的初態(tài)開始，對于輸入序列中的每一個字符，尋找它的下一狀態(tài)轉(zhuǎn)移，直到?jīng)]有下一狀態(tài)轉(zhuǎn)移為止。若此時所處狀態(tài)是終態(tài)，則從初態(tài)到終態(tài)路徑上的所有標記，構(gòu)成了一個識別出的記號。否則沿原路返回，并在返回的每一個節(jié)點試探可能的下一條路徑，直到遇到第一個終態(tài)，或者一直返回到初態(tài)也沒有遇到終態(tài)。對于輸入序列，若試探了所有的路徑也找不到下一狀態(tài)轉(zhuǎn)移或不能到達一個終態(tài)，則NFA不接受該序列，說明它不是語言中的合法記號。若到達一個終態(tài)，則NFA接受該序列，說明它是語言中的一個合法記號。

例2.9

用例2.7中的NFA來識別輸入序列abb和abab。識別過程如圖2.7所示。對于abb的識別，有兩條路徑。第一條路徑從狀態(tài)0出發(fā)，經(jīng)過字符a到達狀態(tài)0，經(jīng)過字符b到達狀態(tài)0，再經(jīng)過字符b到達狀態(tài)0，此時輸入序列已經(jīng)結(jié)束，但是NFA沒有到達終態(tài)，所以NFA不接受輸入序列abb。但是，由于在狀態(tài)0遇到字符a的下一狀態(tài)還可以是1，因此沿原路回退到狀態(tài)0。再試探另一路徑：從狀態(tài)0出發(fā)，經(jīng)過字符a到達狀態(tài)1，經(jīng)過字符b到達狀態(tài)2，最后經(jīng)過字符b到達狀態(tài)3。由于狀態(tài)3是一個終態(tài)，所以，字符串a(chǎn)bb被NFA接受，或者說被NFA識別。該過程被稱為識別過程，其中的0123被稱為識別路徑，而標記該路徑的字符串a(chǎn)bb是NFA所識別的記號。再來看對abab的識別過程。從0狀態(tài)出發(fā)遇到第一個字符a可以選擇兩條路徑對abab進行識別，當選擇了遇到第一個字符a沿路徑000到達第二個字符a時，又可以選擇兩條路徑。因此，NFA對abab的識別有圖2.7(b)所示的三條路徑可走。但是三條路徑均不能到達終態(tài)，且再無路徑可以試探,?所以NFA不接受輸入序列abab,?也就是說，abab不是一個合法的記號。圖2.7NFA識別輸入序列abb和abab(a)abb的識別過程；(b)abab的識別過程

從例2.9中可以看出，用NFA識別記號存在下述問題：

(1)只有嘗試了全部可能的路徑，才能確定一個輸入序列不被接受，而這些路徑的條數(shù)隨著路徑長度的增長成指數(shù)增長。

(2)識別過程中需要進行大量的回溯，時間復(fù)雜度與輸入序列成指數(shù)級增長，且算法復(fù)雜。造成這種情況的原因是NFA的不確定性，即在當前的狀態(tài)下，遇到的下一個字符可能有多于一條的路徑可走，而在當前狀態(tài)下，這些路徑中哪條路徑可以到達終態(tài)或者全部路徑均不能到達終態(tài)都是不可知的。2.3.2確定的有限自動機(DeterministicFiniteAutomata,DFA)

定義2.5DFA是NFA的一個特例，其中：

①沒有狀態(tài)具有ε狀態(tài)轉(zhuǎn)移(ε-transition)，即狀態(tài)轉(zhuǎn)換圖中沒有標記ε的邊；

②對每一個狀態(tài)s和每一個字符a，最多有一個下一狀態(tài)。

例2.10

識別由正規(guī)式(a|b)*abb說明的記號的DFA，其轉(zhuǎn)換圖和轉(zhuǎn)換矩陣表示如圖2.8所示。根據(jù)轉(zhuǎn)換圖，讀者不難寫出此DFA的定義。用它識別輸入序列abb和abab的過程如圖2.9所示。圖2.8識別(a|b)*abb的DFA(a)轉(zhuǎn)換圖表示的DFA；(b)轉(zhuǎn)換矩陣表示的DFA圖2.9DFA識別輸入序列abb和abab

與NFA相比，DFA的特點就是它的確定性，即在當前狀態(tài)下，對同一個字符ch，最多有一個下一狀態(tài)轉(zhuǎn)移。確定性反映在DFA的定義中，就是move函數(shù)是一對一的；反映在轉(zhuǎn)換圖中，就是從一個節(jié)點出發(fā)的任何不同的邊上標記的字符均不同；反映在轉(zhuǎn)換矩陣中，就是M[si,sj]中是一個單一狀態(tài)。由于在DFA上識別輸入序列時，在任何一個當前狀態(tài)下遇到任何輸入字符，其下一狀態(tài)轉(zhuǎn)移均是唯一確定的，因此，無論是接受還是不接受，均經(jīng)歷一條確定的路徑，而無其他任何路徑可走。也就是說，在DFA上識別輸入序列無需回溯，從而大大簡化了記號的識別過程。DFA識別輸入序列的過程總結(jié)為算法2.1，被稱為模擬器(模擬DFA的行為)，也被稱為驅(qū)動器(用DFA的數(shù)據(jù)驅(qū)動分析動作)。模擬DFA算法的最大特點是方法與模式無關(guān)，它僅根據(jù)DFA的當前狀態(tài)和狀態(tài)轉(zhuǎn)移進行一系列的動作，直到回答yes或者no。而所有與模式相關(guān)的信息均包含在DFA中。

算法2.1模擬DFA

輸入

DFAD和輸入字符串x。x由文件結(jié)束符eof終止，D的初態(tài)為s0，終態(tài)集為F。

輸出若D接受x，回答“yes”，否則回答“no”。

方法用下述過程識別x：

s:=s0；a:=nextchar；

whilea≠eofloops:=move(s，a)；a:=nextchar;endloop；

ifsisinFthenreturn"yes"；elsereturn"no"；endif