引言1.1從面向機(jī)器的語(yǔ)言到面向人類的語(yǔ)言

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

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

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

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

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

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

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

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

假設(shè)有源程序：

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

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

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

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

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

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

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

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

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

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

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

例1.2

有一Pascal源程序語(yǔ)句如下所示：

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

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

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

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

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

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

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

中間代碼生成

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

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

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

(1)關(guān)鍵字:如var、begin、end...，它們?cè)谠闯绦蛑芯刑囟êx，一般不作它用，在這種情況下也被稱為保留字。

(2)標(biāo)識(shí)符:如x、y、z、sort...，它們?cè)谠闯绦蛑斜挥米髯兞棵⑦^(guò)程名、類型名和標(biāo)號(hào)等所有對(duì)象的名稱。(3)字面量:如60、"XidianUniversity"...，一般表示常數(shù)或字符串常量，它們也可以被細(xì)分為數(shù)字字面量、字符串字面量等。

(4)特殊符號(hào):如":="、"+"、";"...，它們?cè)谠闯绦蛑芯刑囟êx，根據(jù)它們的作用，也可以被細(xì)分為運(yùn)算符、分隔符等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

①牢固掌握基本概念，這要進(jìn)行大量的閱讀，并通過(guò)閱讀加深理解；

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

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

②面向機(jī)器的低級(jí)語(yǔ)言，如匯編語(yǔ)言和二進(jìn)制機(jī)器代碼等；

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

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

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

例2.1

對(duì)于語(yǔ)句：position:=initial+rate*60，可以識(shí)別出下述序列：標(biāo)識(shí)符特殊符號(hào)標(biāo)識(shí)符特殊符號(hào)標(biāo)識(shí)符特殊符號(hào)數(shù)字字面量其中position、initial、rate均被識(shí)別為標(biāo)識(shí)符，因?yàn)樗鼈兙贤粭l規(guī)則，即以字母打頭的字母數(shù)字串。記號(hào)至少含有兩個(gè)信息：一個(gè)是記號(hào)的類別，如“標(biāo)識(shí)符”；另一個(gè)是記號(hào)的值，如“position”。顯然，如果把記號(hào)看作是一個(gè)類型的話，則單詞就是一個(gè)類型中的實(shí)例。由于我們總是說(shuō)識(shí)別出一個(gè)標(biāo)識(shí)符，而不說(shuō)識(shí)別出一個(gè)position或rate，因而將詞法分析器識(shí)別出的序列稱為記號(hào)流。

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

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

例2.2

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

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

(3)識(shí)別記號(hào)，并交給語(yǔ)法分析器。這是詞法分析器的主要任務(wù)，本章將在各節(jié)中詳細(xì)討論。(4)調(diào)用符號(hào)表管理器或出錯(cuò)處理器，進(jìn)行相關(guān)處理。詞法錯(cuò)誤是源程序中常見(jiàn)的錯(cuò)誤，如出現(xiàn)非法字符、拼錯(cuò)關(guān)鍵字、多或少字符等。值得注意的是，詞法錯(cuò)誤往往不是由詞法分析器檢查出來(lái)的，而是由語(yǔ)法分析器發(fā)現(xiàn)的。這是因?yàn)椋闯绦蛑谐朔欠ㄗ址獾拇蟛糠肿址蜃址伎梢员辉~法分析器的某個(gè)模式所匹配，從而被識(shí)別成一個(gè)記號(hào)。而這些記號(hào)的正確與否，在沒(méi)有上下文對(duì)照的情況下，是很難判斷的。例如，12x被認(rèn)為是一個(gè)非法的Pascal的標(biāo)識(shí)符，但是，由于12可以被識(shí)別整型數(shù)的模式匹配，而x可以被識(shí)別標(biāo)識(shí)符的模式匹配，因而詞法分析器會(huì)分別識(shí)別出一個(gè)整型數(shù)和一個(gè)標(biāo)識(shí)符，而不是報(bào)告一個(gè)錯(cuò)誤。

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

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

(2)詞法分析器進(jìn)行單獨(dú)的一遍掃描。另一種常用的工作方式，是安排詞法分析器進(jìn)行單獨(dú)的一遍掃描，它以源程序?yàn)檩斎耄敵鍪且杂浱?hào)流形式表示的源程序。其工作方式如圖2.2所示。圖2.1作為子程序的詞法分析器

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

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

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

thenreturnerror；

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

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

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

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

由于字符串的有序性，使得以字符串作為元素的集合具有某些特性。字符串和集合的基本概念和特性，以表格的形式分別列在表2.3和表2.4中。其中，字符串的連接運(yùn)算是一種新形式的運(yùn)算，它表示兩個(gè)字符串首尾相接，形成一個(gè)新的集合。例如，S1="pre"，S2="fix"，則S1S2="prefix"。值得注意的是，集合中連接運(yùn)算所形成的新集合與交運(yùn)算形成的新集合完全不同。例如，若L={"pre"，M={"fix"，則L∩M=Φ，而LM={"prefix"。表2.3字符串的基本概念表2.4字符串集合上的基本運(yùn)算2.2.2正規(guī)式與正規(guī)集定義2.2令Σ是一個(gè)有限字母表，則Σ上的正規(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ī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言或正規(guī)集。

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

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

例2.3

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

正規(guī)集是一個(gè)集合，而正規(guī)式是表示正規(guī)集的一種方法。正如不同算術(shù)表達(dá)式可以表示同一個(gè)數(shù)(如3+5、5+3、2+6等均表示8)一樣，不同正規(guī)式也可以表示同一個(gè)正規(guī)集，即正規(guī)式與正規(guī)集之間是多對(duì)一的關(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表示同一個(gè)正規(guī)集。

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

例2.5

表2.1中的記號(hào)relation、id和num分別是Pascal的關(guān)系運(yùn)算符、標(biāo)識(shí)符和無(wú)符號(hào)數(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ī)式給出了標(biāo)識(shí)符的精確定義，用自然語(yǔ)言可以描述為“字母是英文26個(gè)字母大小寫中任何一個(gè)，數(shù)字是十進(jìn)制阿拉伯?dāng)?shù)字中的任何一個(gè)，標(biāo)識(shí)符是以字母打頭的、其后可跟隨0個(gè)或若干個(gè)字母或數(shù)字的字符串”。1．簡(jiǎn)化正規(guī)式描述為了簡(jiǎn)化正規(guī)式的描述，通常可以采用如下的幾種正規(guī)式的縮寫形式。

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

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

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

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

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

2．引入輔助定義式引入輔助定義式的主要目的是為較復(fù)雜、但需要重復(fù)書寫的正規(guī)式命名，并在定義式之后的引用中，用名字代替相應(yīng)的正規(guī)式。所以，輔助定義式實(shí)質(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記號(hào)的識(shí)別——有限自動(dòng)機(jī)2.3.1不確定的有限自動(dòng)機(jī)(NondeterministicFiniteAutomata，NFA)

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

其中：

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

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

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

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

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

例2.7

識(shí)別由正規(guī)式(a|b)*abb說(shuō)明的記號(hào)的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識(shí)別(a|b)*abb的NFA(a)轉(zhuǎn)換圖表示的NFA；(b)轉(zhuǎn)換矩陣表示的NFA

例2.8

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

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

例2.9

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

從例2.9中可以看出，用NFA識(shí)別記號(hào)存在下述問(wèn)題：

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

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

定義2.5DFA是NFA的一個(gè)特例，其中：

①?zèng)]有狀態(tài)具有ε狀態(tài)轉(zhuǎn)移(ε-transition)，即狀態(tài)轉(zhuǎn)換圖中沒(méi)有標(biāo)記ε的邊；

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

例2.10

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

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

算法2.1模擬DFA

輸入

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

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

方法用下述過(guò)程識(shí)別x：

s:=s0；a:=nextchar；

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

ifsisinFthenreturn"yes"；elsereturn"no"；endif