計算機(jī)只能讀懂0或者1，而我們用高級語言編寫的程序(原程序)是抽象的符號化了的東西，為了讓計算機(jī)讀懂我們寫的程序，必須把我們書寫的程序翻譯成某臺機(jī)器能夠讀懂的(機(jī)器)語言(目標(biāo)程序)，這就是翻譯程序的作用。而“編譯”則是翻譯程序?qū)崿F(xiàn)的一種方式。

??? 編譯程序的工作過程通常是詞法分析、語法分析、語義分析、代碼生成、代碼優(yōu)化。編譯程序的這些過程的執(zhí)行先后就構(gòu)成了編譯程序的邏輯結(jié)構(gòu)，但是這些邏輯結(jié)構(gòu)不一定是按照某一個固定順序的，也有可能是按照平行或者互鎖的方式執(zhí)行的。

本文主要介紹基于 編譯器構(gòu)造技術(shù)中的由正規(guī)表達(dá)式到最小化 DFA 的算法設(shè)計和實現(xiàn)技術(shù)； 主要包括由正規(guī)表達(dá)式構(gòu)造NFA所用到的Thompson構(gòu)造法、把NFA轉(zhuǎn)化為與其等價的DFA所使用的子集構(gòu)造算法以及把DFA最小化的算法，最后實現(xiàn)詞法分析。Thompson構(gòu)造法根據(jù)讀入的正規(guī)表達(dá)式的不同字符進(jìn)入相應(yīng)的轉(zhuǎn)換處理。NFA轉(zhuǎn)化為與其等價的DFA需分兩步進(jìn)行：a、構(gòu)造NFA? N的狀態(tài)K的子集的算法 ； b 、計算 e -closure 。完成這些子模塊的設(shè)計后，再通過某一中間模塊的總控程序?qū)ζ湔{(diào)用，最后再由主程序合并調(diào)用。在算法實現(xiàn)過程中，主要使用visual C++進(jìn)行編程，并且用到了STL（標(biāo)準(zhǔn)模板庫）技術(shù)來對邊集、狀態(tài)集進(jìn)行定義和處理。正規(guī)表達(dá)式與自動機(jī)理論在詞法構(gòu)造乃至整個編譯器構(gòu)造過程中起著至關(guān)重要的作用，同時它們被廣泛應(yīng)用于計算機(jī)科學(xué)的各個領(lǐng)域，它們與計算機(jī)其它學(xué)科之間也有著很大的聯(lián)系。

?

?

?

?

關(guān)鍵詞： 正規(guī)表達(dá)式；DFA；Thompson構(gòu)造法；子集構(gòu)造算法；詞法分析

?


?

?

abstract

?

?????? Computer can only recognize 0 or 1. And the program we write by using higher language is a thing of abstract symbol; in order to understood by computer we must translate the program that we write into language that can recognized by computer. That is the effect of translator. And “compile” is a realizing mode of translator.

?????? The working course of translator usually is lexical analysis, syntax analysis, semantic analysis, code generation, code optimization. The logic structures are make up of the excutive order of the compiling process. But these structures are not necessary in accordance with some fixed sequence, and some may be executed in parallel or mutual locked mode.

?????? This paper according to compiler construct technology introduces the contents, methord and realize technique of Algorithms of regular expression to minimum state DFA, It Primarily includes the method for converting a regular expression to a NFA which uses Thompson's algorithm, the method for converting NFA to DFA which uses Subset Construction Algorithm and the method for DFA optimization,at last realize it’s lexical analysis. Thompson's algorithm deals with vary character which is from regular expressions. It need two step for converting a regular expression to a NFA: a 、 construct Subset Construction Algorithm for state K of NFA N. b 、 deal with e -closure. When subset module was done, I use chief function of a certain process module to transfer it. At last I use the main program to combine all of them. To realize the program,I mainly use Visual C++ 6.0 for programming. Besides I use STL technology to define and process edge gather and state gather. Regular expression and FA theory are very important for Lexical Analysis even the whole compiler construction. And they are widely used in other field of computer. They also have great relation with other subject of computer.

?

?

?

?

?

Key words: regular expression, DFA, Thompson's algorithm, Subset Construction Algorithm,? Lexical Analysis

?

正文：

??? 詞法分析器可有兩種:一種是把詞法分析器作為語法分析的一個子程序,一種是把詞法分析器作為編譯程序的獨(dú)立一遍.在前一種情況下,詞法分析器不斷地被語法分析器調(diào)用,每調(diào)用一次詞法分析器將從源程序的字符序列拼出一個單詞,并將其Token值返回給語法分析器.后一種情況則不同,詞法分析器不是被語法分析器不斷地調(diào)用,而是一次掃描全部單詞完成編譯器的獨(dú)立一遍任務(wù).

??? 詞法分析器的本質(zhì)：基本任務(wù)是進(jìn)行模式匹配,其關(guān)鍵在于分析過程中的模式說明和模式識別方法,在編譯分析中即正規(guī)表達(dá)式和有限自動機(jī)。

??? 構(gòu)造詞法分析器方法：1、手工構(gòu)造；2、利用自動生成工具LEX。但是無論用那種方法，其內(nèi)在工作原理都是相同的，都要經(jīng)過正規(guī)式到最小狀態(tài)DFA的轉(zhuǎn)換。

?

?

1.1.1???? 正規(guī)表達(dá)式、有限自動機(jī)與詞法分析的關(guān)系

?

??? 正規(guī)表達(dá)式與有限自動機(jī)的關(guān)系：（1）、字母表Σ上的有限自動機(jī)M所接受的語言L（M）是Σ上的一個正規(guī)集；（2）、對于Σ上的每一個正規(guī)式r，存在一個Σ上的非確定有限自動機(jī)M，使得L（M）=L（r）。這就是說，正規(guī)式所表示的語言即正規(guī)集與有限自動機(jī)所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用FA描述，也可以用正規(guī)式描述。而詞法分析器則是根據(jù)它們的規(guī)則構(gòu)造的。

?

?

1.1.2???? 編譯系統(tǒng)概述

?

編譯器是將一種語言翻譯為另一種語言的計算機(jī)程序。編譯器將源程序（source language）編寫的程序作為輸入，而產(chǎn)生用目標(biāo)語言（target language）編寫的等價程序。通常地，源程序為高級語言（high-level language），如C或C++，而目標(biāo)語言則是目標(biāo)機(jī)器的目標(biāo)代碼（object code，有時也稱作機(jī)器代碼（machine code）），也就是寫在計算機(jī)機(jī)器指令中的用于運(yùn)行的代碼。

編譯器是一種相當(dāng)復(fù)雜的程序，其代碼的長度可從10000行到1000000行不等。編寫甚至讀懂這樣的一個程序都非易事，大多數(shù)的計算機(jī)科學(xué)家和專業(yè)人員也從來沒有編寫過一個完整的編譯器。但是，幾乎所有形式的計算均要用到編譯器，而且任何一個與計算機(jī)打交道的專業(yè)人員都應(yīng)掌握編譯器的基本結(jié)構(gòu)和操作。除此之外，計算機(jī)應(yīng)用程序中經(jīng)常遇到的一個任務(wù)就是命令解釋程序和界面程序的開發(fā)，這比編譯器要小，但使用的卻是相同的技術(shù)。因此，掌握這一技術(shù)具有非常大的實際意義。

?

一、 編譯系統(tǒng)的 發(fā)展：

上世紀(jì)50年代，IBM的John Backus帶領(lǐng)一個研究小組對FORTRAN語言及其編譯器進(jìn)行開發(fā)。但由于當(dāng)時人們對編譯理論了解不多，開發(fā)工作變得既復(fù)雜又艱苦。與此同時， Noam Chomsky開始了他對自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編譯器的結(jié)構(gòu)異常簡單，甚至還帶有了一些自動化。Chomsky的研究導(dǎo)致了根據(jù)語言文法的難易程度以及識別它們所需要的算法來對語言分類。正如現(xiàn)在所稱的Chomsky架構(gòu)（Chomsky Hierarchy），它包括了文法的四個層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法（或上下文無關(guān)文法）被證明是程序設(shè)計語言中最有用的，而且今天它已代表著程序設(shè)計語言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。分析問題（parsing problem，用于上下文無關(guān)文法識別的有效算法）的研究是在60年代和70年代，它相當(dāng)完善的解決了這個問題?，F(xiàn)在它已是編譯原理中的一個標(biāo)準(zhǔn)部分。
??? 有限狀態(tài)自動機(jī)（Finite Automaton）和正則表達(dá)式（Regular Expression）同上下文無關(guān)文法緊密相關(guān)，它們與Chomsky的3型文法相對應(yīng)。對它們的研究與Chomsky的研究幾乎同時開始，并且引出了表示程序設(shè)計語言的單詞的符號方式。
??? 人們接著又深化了生成有效目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優(yōu)化技術(shù)（Optimization Technique），但因其從未真正地得到過被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實際上應(yīng)稱作代碼改進(jìn)技術(shù)（Code Improvement Technique）。
??? 當(dāng)分析問題變得好懂起來時，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一部分的編譯器自動構(gòu)造。這些程序最初被稱為編譯器的編譯器（Compiler-compiler），但更確切地應(yīng)稱為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統(tǒng)編寫的。類似的，有限狀態(tài)自動機(jī)的研究也發(fā)展了一種稱為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時，由Mike Lesk為Unix系統(tǒng)開發(fā)）是這其中的佼佼者。
??? 在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復(fù)雜而人們又對其不甚了解。
??? 編譯器設(shè)計最近的發(fā)展包括：首先，編譯器包括了更加復(fù)雜算法的應(yīng)用程序它用于推斷或簡化程序中的信息；這又與更為復(fù)雜的程序設(shè)計語言的發(fā)展結(jié)合在一起。其中典型的有用于函數(shù)語言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。其次，編譯器已越來越成為基于窗口的交互開發(fā)環(huán)境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調(diào)試程序以及項目管理程序。這樣的IDE標(biāo)準(zhǔn)并沒有多少，但是對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行開發(fā)已成為方向。另一方面，盡管近年來在編譯原理領(lǐng)域進(jìn)行了大量的研究，但是基本的編譯器設(shè)計原理在近20年中都沒有多大的改變，它現(xiàn)在正迅速地成為計算機(jī)科學(xué)課程中的中心環(huán)節(jié)。
??? 在九十年代，作為GNU項目或其它開放源代碼項目的一部分，許多免費(fèi)編譯器和編譯器開發(fā)工具被開發(fā)出來。這些工具可用來編譯所有的計算機(jī)程序語言。它們中的一些項目被認(rèn)為是高質(zhì)量的，而且對現(xiàn)代編譯理論感性趣的人可以很容易的得到它們的免費(fèi)源代碼。
??? 大約在1999年，SGI公布了他們的一個工業(yè)化的并行化優(yōu)化編譯器Pro64的源代碼，后被全世界多個編譯器研究小組用來做研究平臺，并命名為Open64。Open64的設(shè)計結(jié)構(gòu)好，分析優(yōu)化全面，是編譯器高級研究的理想平臺。

?

?

二、與編譯器相關(guān)的程序：

?

(1) 解釋程序（interpreter）
??? 解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執(zhí)行源程序而不是生成在翻譯完成之后才執(zhí)行的目標(biāo)代碼。從原理上講，任何程序設(shè)計語言都可被解釋或被編譯，但是根據(jù)所使用的語言和翻譯情況，很可能會選用解釋程序而不用編譯器。例如，我們經(jīng)常解釋BASIC語言而不是去編譯它。類似地，諸如LISP的函數(shù)語言也常常是被解釋的。解釋程序也經(jīng)常用于教育和軟件的開發(fā)，此處的程序很有可能被翻譯若干次。而另一方面，當(dāng)執(zhí)行的速度是最為重要的因素時就使用編譯器，這是因為被編譯的目標(biāo)代碼比被解釋的源代碼要快得多，有時要快10倍或更多。但是，解釋程序具有許多與編譯器共享的操作，而兩者之間也有一些混合之處。

?

(2) 匯編程序（assembler）
??? 匯編程序是用于特定計算機(jī)上的匯編語言的翻譯程序。正如前面所提到的，匯編語言是計算機(jī)的機(jī)器語言的符號形式，它極易翻譯。有時，編譯器會生成匯編語言以作為其目標(biāo)語言，然后再由一個匯編程序?qū)⑺g成目標(biāo)代碼。


(3) 連接程序（linker）
??? 編譯器和匯編程序都經(jīng)常依賴于連接程序，它將分別在不同的目標(biāo)文件中編譯或匯編的代碼收集到一個可直接執(zhí)行的文件中。在這種情況下，目標(biāo)代碼，即還未被連接的機(jī)器代碼，與可執(zhí)行的機(jī)器代碼之間就有了區(qū)別。連接程序還連接目標(biāo)程序和用于標(biāo)準(zhǔn)庫函數(shù)的代碼，以及連接目標(biāo)程序和由計算機(jī)的操作系統(tǒng)提供的資源（例如，存儲分配程序及輸入與輸出設(shè)備）。有趣的是，連接程序現(xiàn)在正在完成編譯器最早的一個主要活動（這也是“編譯”一詞的用法，即通過收集不同的來源來構(gòu)造）。連接過程對操作系統(tǒng)和處理器有極大的依賴性。

?


(4) 裝入程序（loader）
??? 編譯器、匯編程序或連接程序生成的代碼經(jīng)常還不完全適用或不能執(zhí)行，但是它們的主要存儲器訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關(guān)。這樣的代碼被稱為是可重定位的（relocatable），而裝入程序可處理所有的與指定的基地址或起始地址有關(guān)的可重定位的地址。裝入程序使得可執(zhí)行代碼更加靈活，但是裝入處理通常是在后臺（作為操作環(huán)境的一部分）或與連接相聯(lián)合時才發(fā)生，裝入程序極少會是實際的獨(dú)立程序。


(5) 預(yù)處理器（preprocessor）
??? 預(yù)處理器是在真正的翻譯開始之前由編譯器調(diào)用的獨(dú)立程序。預(yù)處理器可以刪除注釋、包含其他文件以及執(zhí)行宏（宏macro是一段重復(fù)文字的簡短描寫）替代。預(yù)處理器可由語言（如C）要求或以后作為提供額外功能（諸如為FORTRAN提供Ratfor預(yù)處理器）的附加軟件。


(6) 編輯器（editor）
??? 編譯器通常接受由任何生成標(biāo)準(zhǔn)文件（例如ASCII文件）的編輯器編寫的源程序。最近，編譯器已與另一個編輯器和其他程序捆綁進(jìn)一個交互的開發(fā)環(huán)境——IDE中。此時，盡管編輯器仍然生成標(biāo)準(zhǔn)文件，但會轉(zhuǎn)向正被討論的程序設(shè)計語言的格式或結(jié)構(gòu)。這樣的編輯器稱為基于結(jié)構(gòu)的（structure based），且它早已包括了編譯器的某些操作；因此，程序員就會在程序的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調(diào)用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執(zhí)行程序。


(7) 調(diào)試程序（debugger）
??? 調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯誤的程序，它也經(jīng)常與編譯器一起放在IDE中。運(yùn)行一個帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因為調(diào)試程序保存著所有的或大多數(shù)源代碼信息（諸如行數(shù)、變量名和過程）。它還可以在預(yù)先指定的位置（稱為斷點（breakpoint））暫停執(zhí)行，并提供有關(guān)已調(diào)用的函數(shù)以及變量的當(dāng)前值的信息。為了執(zhí)行這些函數(shù)，編譯器必須為調(diào)試程序提供恰當(dāng)?shù)姆栃畔?，而這有時卻相當(dāng)困難，尤其是在一個要優(yōu)化目標(biāo)代碼的編譯器中。因此，調(diào)試又變成了一個編譯問題。


(8) 描述器（profiler）
??? 描述器是在執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計的程序。程序員特別感興趣的統(tǒng)計是每一個過程的調(diào)用次數(shù)和每一個過程執(zhí)行時間所占的百分比。這樣的統(tǒng)計對于幫助程序員提高程序的執(zhí)行速度極為有用。有時編譯器也甚至無需程序員的干涉就可利用描述器的輸出來自動改進(jìn)目標(biāo)代碼。


(9) 項目管理程序（project manager）
??? 現(xiàn)在的軟件項目通常大到需要由一組程序員來完成，這時對那些由不同人員操作的文件進(jìn)行整理就非常重要了，而這正是項目管理程序的任務(wù)。例如，項目管理程序應(yīng)將由不同的程序員制作的文件的各個獨(dú)立版本整理在一起，它還應(yīng)保存一組文件的更改歷史，這樣就能維持一個正在開發(fā)的程序的連貫版本了（這對那些由單個程序員管理的項目也很有用）。項目管理程序的編寫可與語言無關(guān)，但當(dāng)其與編譯器捆綁在一起時，它就可以保持有關(guān)特定的編譯器和建立一個完整的可執(zhí)行程序的鏈接程序操作的信息。在Unix系統(tǒng)中有兩個流行的項目管理程序：sccs（source code control system）和rcs（revision control system）。

?

?

?

??? 詞法分析器可有兩種:一種是把詞法分析器作為語法分析的一個子程序,一種是把詞法分析器作為編譯程序的獨(dú)立一遍.在前一種情況下,詞法分析器不斷地被語法分析器調(diào)用,每調(diào)用一次詞法分析器將從源程序的字符序列拼出一個單詞,并將其Token值返回給語法分析器.后一種情況則不同,詞法分析器不是被語法分析器不斷地調(diào)用,而是一次掃描全部單詞完成編譯器的獨(dú)立一遍任務(wù).

??? 詞法分析器的本質(zhì)：基本任務(wù)是進(jìn)行模式匹配,其關(guān)鍵在于分析過程中的模式說明和模式識別方法,在編譯分析中即正規(guī)表達(dá)式和有限自動機(jī)。

??? 構(gòu)造詞法分析器方法：1、手工構(gòu)造；2、利用自動生成工具LEX。但是無論用那種方法，其內(nèi)在工作原理都是相同的，都要經(jīng)過正規(guī)式到最小狀態(tài)DFA的轉(zhuǎn)換。

?

?

1.1.1???? 正規(guī)表達(dá)式、有限自動機(jī)與詞法分析的關(guān)系

?

??? 正規(guī)表達(dá)式與有限自動機(jī)的關(guān)系：（1）、字母表Σ上的有限自動機(jī)M所接受的語言L（M）是Σ上的一個正規(guī)集；（2）、對于Σ上的每一個正規(guī)式r，存在一個Σ上的非確定有限自動機(jī)M，使得L（M）=L（r）。這就是說，正規(guī)式所表示的語言即正規(guī)集與有限自動機(jī)所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用FA描述，也可以用正規(guī)式描述。而詞法分析器則是根據(jù)它們的規(guī)則構(gòu)造的。

?

?

1.1.2???? 編譯系統(tǒng)概述

?

編譯器是將一種語言翻譯為另一種語言的計算機(jī)程序。編譯器將源程序（source language）編寫的程序作為輸入，而產(chǎn)生用目標(biāo)語言（target language）編寫的等價程序。通常地，源程序為高級語言（high-level language），如C或C++，而目標(biāo)語言則是目標(biāo)機(jī)器的目標(biāo)代碼（object code，有時也稱作機(jī)器代碼（machine code）），也就是寫在計算機(jī)機(jī)器指令中的用于運(yùn)行的代碼。

編譯器是一種相當(dāng)復(fù)雜的程序，其代碼的長度可從10000行到1000000行不等。編寫甚至讀懂這樣的一個程序都非易事，大多數(shù)的計算機(jī)科學(xué)家和專業(yè)人員也從來沒有編寫過一個完整的編譯器。但是，幾乎所有形式的計算均要用到編譯器，而且任何一個與計算機(jī)打交道的專業(yè)人員都應(yīng)掌握編譯器的基本結(jié)構(gòu)和操作。除此之外，計算機(jī)應(yīng)用程序中經(jīng)常遇到的一個任務(wù)就是命令解釋程序和界面程序的開發(fā)，這比編譯器要小，但使用的卻是相同的技術(shù)。因此，掌握這一技術(shù)具有非常大的實際意義。

?

一、 編譯系統(tǒng)的 發(fā)展：

上世紀(jì)50年代，IBM的John Backus帶領(lǐng)一個研究小組對FORTRAN語言及其編譯器進(jìn)行開發(fā)。但由于當(dāng)時人們對編譯理論了解不多，開發(fā)工作變得既復(fù)雜又艱苦。與此同時， Noam Chomsky開始了他對自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編譯器的結(jié)構(gòu)異常簡單，甚至還帶有了一些自動化。Chomsky的研究導(dǎo)致了根據(jù)語言文法的難易程度以及識別它們所需要的算法來對語言分類。正如現(xiàn)在所稱的Chomsky架構(gòu)（Chomsky Hierarchy），它包括了文法的四個層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法（或上下文無關(guān)文法）被證明是程序設(shè)計語言中最有用的，而且今天它已代表著程序設(shè)計語言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。分析問題（parsing problem，用于上下文無關(guān)文法識別的有效算法）的研究是在60年代和70年代，它相當(dāng)完善的解決了這個問題。現(xiàn)在它已是編譯原理中的一個標(biāo)準(zhǔn)部分。
??? 有限狀態(tài)自動機(jī)（Finite Automaton）和正則表達(dá)式（Regular Expression）同上下文無關(guān)文法緊密相關(guān)，它們與Chomsky的3型文法相對應(yīng)。對它們的研究與Chomsky的研究幾乎同時開始，并且引出了表示程序設(shè)計語言的單詞的符號方式。
??? 人們接著又深化了生成有效目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優(yōu)化技術(shù)（Optimization Technique），但因其從未真正地得到過被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實際上應(yīng)稱作代碼改進(jìn)技術(shù)（Code Improvement Technique）。
??? 當(dāng)分析問題變得好懂起來時，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一部分的編譯器自動構(gòu)造。這些程序最初被稱為編譯器的編譯器（Compiler-compiler），但更確切地應(yīng)稱為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統(tǒng)編寫的。類似的，有限狀態(tài)自動機(jī)的研究也發(fā)展了一種稱為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時，由Mike Lesk為Unix系統(tǒng)開發(fā)）是這其中的佼佼者。
??? 在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復(fù)雜而人們又對其不甚了解。
??? 編譯器設(shè)計最近的發(fā)展包括：首先，編譯器包括了更加復(fù)雜算法的應(yīng)用程序它用于推斷或簡化程序中的信息；這又與更為復(fù)雜的程序設(shè)計語言的發(fā)展結(jié)合在一起。其中典型的有用于函數(shù)語言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。其次，編譯器已越來越成為基于窗口的交互開發(fā)環(huán)境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調(diào)試程序以及項目管理程序。這樣的IDE標(biāo)準(zhǔn)并沒有多少，但是對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行開發(fā)已成為方向。另一方面，盡管近年來在編譯原理領(lǐng)域進(jìn)行了大量的研究，但是基本的編譯器設(shè)計原理在近20年中都沒有多大的改變，它現(xiàn)在正迅速地成為計算機(jī)科學(xué)課程中的中心環(huán)節(jié)。
??? 在九十年代，作為GNU項目或其它開放源代碼項目的一部分，許多免費(fèi)編譯器和編譯器開發(fā)工具被開發(fā)出來。這些工具可用來編譯所有的計算機(jī)程序語言。它們中的一些項目被認(rèn)為是高質(zhì)量的，而且對現(xiàn)代編譯理論感性趣的人可以很容易的得到它們的免費(fèi)源代碼。
??? 大約在1999年，SGI公布了他們的一個工業(yè)化的并行化優(yōu)化編譯器Pro64的源代碼，后被全世界多個編譯器研究小組用來做研究平臺，并命名為Open64。Open64的設(shè)計結(jié)構(gòu)好，分析優(yōu)化全面，是編譯器高級研究的理想平臺。

?

?

二、與編譯器相關(guān)的程序：

?

(1) 解釋程序（interpreter）
??? 解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執(zhí)行源程序而不是生成在翻譯完成之后才執(zhí)行的目標(biāo)代碼。從原理上講，任何程序設(shè)計語言都可被解釋或被編譯，但是根據(jù)所使用的語言和翻譯情況，很可能會選用解釋程序而不用編譯器。例如，我們經(jīng)常解釋BASIC語言而不是去編譯它。類似地，諸如LISP的函數(shù)語言也常常是被解釋的。解釋程序也經(jīng)常用于教育和軟件的開發(fā)，此處的程序很有可能被翻譯若干次。而另一方面，當(dāng)執(zhí)行的速度是最為重要的因素時就使用編譯器，這是因為被編譯的目標(biāo)代碼比被解釋的源代碼要快得多，有時要快10倍或更多。但是，解釋程序具有許多與編譯器共享的操作，而兩者之間也有一些混合之處。

?

(2) 匯編程序（assembler）
??? 匯編程序是用于特定計算機(jī)上的匯編語言的翻譯程序。正如前面所提到的，匯編語言是計算機(jī)的機(jī)器語言的符號形式，它極易翻譯。有時，編譯器會生成匯編語言以作為其目標(biāo)語言，然后再由一個匯編程序?qū)⑺g成目標(biāo)代碼。


(3) 連接程序（linker）
??? 編譯器和匯編程序都經(jīng)常依賴于連接程序，它將分別在不同的目標(biāo)文件中編譯或匯編的代碼收集到一個可直接執(zhí)行的文件中。在這種情況下，目標(biāo)代碼，即還未被連接的機(jī)器代碼，與可執(zhí)行的機(jī)器代碼之間就有了區(qū)別。連接程序還連接目標(biāo)程序和用于標(biāo)準(zhǔn)庫函數(shù)的代碼，以及連接目標(biāo)程序和由計算機(jī)的操作系統(tǒng)提供的資源（例如，存儲分配程序及輸入與輸出設(shè)備）。有趣的是，連接程序現(xiàn)在正在完成編譯器最早的一個主要活動（這也是“編譯”一詞的用法，即通過收集不同的來源來構(gòu)造）。連接過程對操作系統(tǒng)和處理器有極大的依賴性。

?


(4) 裝入程序（loader）
??? 編譯器、匯編程序或連接程序生成的代碼經(jīng)常還不完全適用或不能執(zhí)行，但是它們的主要存儲器訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關(guān)。這樣的代碼被稱為是可重定位的（relocatable），而裝入程序可處理所有的與指定的基地址或起始地址有關(guān)的可重定位的地址。裝入程序使得可執(zhí)行代碼更加靈活，但是裝入處理通常是在后臺（作為操作環(huán)境的一部分）或與連接相聯(lián)合時才發(fā)生，裝入程序極少會是實際的獨(dú)立程序。


(5) 預(yù)處理器（preprocessor）
??? 預(yù)處理器是在真正的翻譯開始之前由編譯器調(diào)用的獨(dú)立程序。預(yù)處理器可以刪除注釋、包含其他文件以及執(zhí)行宏（宏macro是一段重復(fù)文字的簡短描寫）替代。預(yù)處理器可由語言（如C）要求或以后作為提供額外功能（諸如為FORTRAN提供Ratfor預(yù)處理器）的附加軟件。


(6) 編輯器（editor）
??? 編譯器通常接受由任何生成標(biāo)準(zhǔn)文件（例如ASCII文件）的編輯器編寫的源程序。最近，編譯器已與另一個編輯器和其他程序捆綁進(jìn)一個交互的開發(fā)環(huán)境——IDE中。此時，盡管編輯器仍然生成標(biāo)準(zhǔn)文件，但會轉(zhuǎn)向正被討論的程序設(shè)計語言的格式或結(jié)構(gòu)。這樣的編輯器稱為基于結(jié)構(gòu)的（structure based），且它早已包括了編譯器的某些操作；因此，程序員就會在程序的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調(diào)用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執(zhí)行程序。


(7) 調(diào)試程序（debugger）
??? 調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯誤的程序，它也經(jīng)常與編譯器一起放在IDE中。運(yùn)行一個帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因為調(diào)試程序保存著所有的或大多數(shù)源代碼信息（諸如行數(shù)、變量名和過程）。它還可以在預(yù)先指定的位置（稱為斷點（breakpoint））暫停執(zhí)行，并提供有關(guān)已調(diào)用的函數(shù)以及變量的當(dāng)前值的信息。為了執(zhí)行這些函數(shù)，編譯器必須為調(diào)試程序提供恰當(dāng)?shù)姆栃畔?，而這有時卻相當(dāng)困難，尤其是在一個要優(yōu)化目標(biāo)代碼的編譯器中。因此，調(diào)試又變成了一個編譯問題。


(8) 描述器（profiler）
??? 描述器是在執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計的程序。程序員特別感興趣的統(tǒng)計是每一個過程的調(diào)用次數(shù)和每一個過程執(zhí)行時間所占的百分比。這樣的統(tǒng)計對于幫助程序員提高程序的執(zhí)行速度極為有用。有時編譯器也甚至無需程序員的干涉就可利用描述器的輸出來自動改進(jìn)目標(biāo)代碼。


(9) 項目管理程序（project manager）
??? 現(xiàn)在的軟件項目通常大到需要由一組程序員來完成，這時對那些由不同人員操作的文件進(jìn)行整理就非常重要了，而這正是項目管理程序的任務(wù)。例如，項目管理程序應(yīng)將由不同的程序員制作的文件的各個獨(dú)立版本整理在一起，它還應(yīng)保存一組文件的更改歷史，這樣就能維持一個正在開發(fā)的程序的連貫版本了（這對那些由單個程序員管理的項目也很有用）。項目管理程序的編寫可與語言無關(guān)，但當(dāng)其與編譯器捆綁在一起時，它就可以保持有關(guān)特定的編譯器和建立一個完整的可執(zhí)行程序的鏈接程序操作的信息。在Unix系統(tǒng)中有兩個流行的項目管理程序：sccs（source code control system）和rcs（revision control system）。

?

?

?

1.2 地位與作用

?

編譯原理與技術(shù)的一整套理論在整個計算機(jī)科學(xué)領(lǐng)域占有相當(dāng)重要的地位。學(xué)習(xí)它，對程序設(shè)計人員有很大的幫助。我們考究歷史會發(fā)現(xiàn)那些人人稱頌的程序設(shè)計大師都是編譯領(lǐng)域的高手，像寫出BASIC語言的BILL GATES，SUN的JAVA之父等等，在編譯上都有很深的造詣。 我們知道，詞法分析在編譯器的設(shè)計過程中是非常重要的，研究編譯原理中的算法可以幫助我們更加深層次的理解程序語言和內(nèi)部機(jī)制，可以用來做簡單的命令解釋器，比如游戲的腳本引擎。而且，界面開發(fā)也需要編譯原理的知識。

正則表達(dá)式是一種可以用于模式匹配和替換的強(qiáng)有力的工具。例如搜索引擎就用到正則表達(dá)式的模式匹配功能。同時我們可以在幾乎所有的基于UNIX系統(tǒng)的工具中找到正則表達(dá)式的身影，例如，vi編輯器，Perl或PHP腳本語言，以及awk或sed shell程序等。此外，象JavaScript這種客戶端的腳本語言也提供了對正則表達(dá)式的支持。由此可見，對正則表達(dá)式的研究已經(jīng)超出了某種語言或某個系統(tǒng)的局限。

編譯技術(shù)幾乎是所有計算機(jī)高級編程語言（諸如C、C++、JAVA等）所必須的，盡管有些（如BASIC）用解釋程序，但解釋程序的前端與編譯器是相通的，因此研究編譯技術(shù)是非常必要的。

編譯原理的相關(guān)技術(shù)還可應(yīng)用于其它許多領(lǐng)域，例如文本編輯器、信息檢索系統(tǒng)、模式識別器；排版、繪圖系統(tǒng)；程序驗證器；集成電路設(shè)計；外文翻譯等等。

英特爾公司與中國合作項目中最顛峰的技術(shù)是中科院計算所與英特爾公司共同合作的IA-64位開放源代碼編譯系統(tǒng)。編輯器接受以高級程序設(shè)計語言(如C、C++和Fortran)編寫的程序，并將其轉(zhuǎn)換為處理器能夠識別的機(jī)器指令。像安騰這樣的處理器擁有多個功能部件，能夠并行地執(zhí)行多條指令。因此，要求現(xiàn)代編譯器也能夠識別源代碼中的并行性，對指令流進(jìn)行高度，以縮短程序的執(zhí)行時間，提高處理器的性能。隨著微處理器體系結(jié)構(gòu)的升級換代，同步提高編譯器技術(shù)也變得越來越重要。中國科學(xué)院計算技術(shù)研究所李國杰院士說：“隨著微處理器技術(shù)的飛速發(fā)展，處理器性能在很大程度上取決于編譯器的質(zhì)量，編譯技術(shù)成為計算機(jī)的核心技術(shù)，地位變得越來越重要。我國要發(fā)展自己的微處理器事業(yè)，必然要有自己的編譯技術(shù)作為后盾。”“IA-64開放源代碼編譯系統(tǒng)的研究，有助于掌握先進(jìn)的處理器和編譯器的設(shè)計技術(shù)以及產(chǎn)品軟件開發(fā)過程的管理技術(shù)和先進(jìn)的軟件工程技術(shù)，為研制自有知識產(chǎn)權(quán)的微處理器和編譯器提供技術(shù)儲備。”而且，中國的龍芯的成功，應(yīng)該歸功于好的技術(shù)路線和編譯技術(shù)的突破。

?

?

3. 程序設(shè)計及實現(xiàn)過程

?

3.1??????? 總體分析與規(guī)劃

?

??? 要把正規(guī)表達(dá)式轉(zhuǎn)換為最小化狀態(tài)DFA，可以直接通過相關(guān)算法轉(zhuǎn)換，但是這將會使得設(shè)計過程非常復(fù)雜，而且程序的可理解性將會大大降低。所以整個程序通過下列三個步驟實現(xiàn)：

(一)??????????? 由正規(guī)表達(dá)式構(gòu)造NFA；

(二)??????????? 把NFA轉(zhuǎn)化為與其等價的DFA；

(三)??????????? 把DFA最小化；

?

?

?

3.1??????? 程序設(shè)計過程

程序設(shè)計過程主要是分析各階段設(shè)計過程要用到的相關(guān)算法。

3.2.1.??????????? 正則表達(dá)式轉(zhuǎn)換為NFA的分析設(shè)計過程

(一)??????????? 由正規(guī)表達(dá)式構(gòu)造NFA：使用Thompson構(gòu)造法

??? 輸入：字母表∑上的一個正規(guī)表達(dá)式r。

??? 輸出：接受L(r)的NFA N。

?

?

?

3.2.1.??????????? NFA 轉(zhuǎn)換為DFA的分析設(shè)計過程

?

??? 使用子集構(gòu)造算法

??? 輸入：一個NFA N；

??? 輸出：一個接受同樣語言的DFA D。

??? 方法：為D構(gòu)造轉(zhuǎn)換表Dtran，DFA的每個狀態(tài)是NFA的狀態(tài)集，D將并行地模擬N對輸入串的所有可能的移動。

??? a 、構(gòu)造NFA? N的狀態(tài)K的子集的算法：

??? 假定所構(gòu)造的子集族為C（D的狀態(tài)集合），即C= (T1, T2,,... TI),其中T1, T2,,... TI為狀態(tài)S的子集。

??? 開始，令 e -closure(S0) 為C中唯一成員，并且它是未被標(biāo)記的。

??? while （C中存在尚未被標(biāo)記的子集T）do? begin?? {????? 標(biāo)記T；?????????????????????? for 每個輸入字母a?? do ? begin{

??????????????????? U:= e -closure(move(T,a)) ；????????? ?????

?????????????????? if? U 不在C中?? then ???????????

??????????????????? 將U作為未標(biāo)記的子集加在C中；

??? Dtran[T ，a]:=U??? } }

??? b 、 e -closure 的計算

??? 將T中所有的狀態(tài)壓入棧stack中；

??? 將 e -closure （T）初始化為T；

??? While 棧stack不空do begin

??? 將棧頂元素t彈出棧；

? ?? for 每個這樣的狀態(tài)u：從t到u有一條標(biāo)記為 e 的邊do

?????? if u 不在 e -closure （T）內(nèi) do begin

?????????? 將u添加到 e -closure （T）；

?????????? 將u壓入棧stack中

?????? End

End

?

3.2.2.??????????? 最小化DFA狀態(tài)數(shù)的分析設(shè)計過程

?

??? 最小化DFA狀態(tài)數(shù)的算法：

??? 輸入：DFA M（其狀態(tài)集合為S），輸入符號為 ∑，轉(zhuǎn)換函數(shù)為f：S×∑--〉S，開始狀態(tài)為s0? ，接受狀態(tài)集為F。

??? 輸出：一個DFA M’，它和M接受同樣的語言，且狀態(tài)數(shù)最少。

??? 方法：

1、 構(gòu)造具有兩個組的狀態(tài)集合的初始劃分∏：接受狀態(tài)組F，非接受狀態(tài)組S-F。

2、 對∏采用下面所述的過程來構(gòu)造新的劃分∏new。

??? for ∏中的每個組G? do begin

?????? 當(dāng)且僅當(dāng)對任意輸入符號a，狀態(tài)s和t在a上的轉(zhuǎn)換到達(dá)∏中的同一組中???? 的狀態(tài)時，才把G劃分成小組，以便G的兩個狀態(tài)s和t在同一小組中；

?????? /* 最壞情況下，一個狀態(tài)就可能成為一個組*/

?????? 用所有新形成的小組集代替∏new中的G；

??? end

3、 如果∏new=∏，令∏final=∏，再執(zhí)行步驟4；否則，令∏:=∏new，重復(fù)步驟2。

4、 在劃分∏final的每個狀態(tài)組中選一個狀態(tài)作為該組的代表，這些代表構(gòu)成了簡化后的DFA M’的狀態(tài)。令s是一個代表狀態(tài)，而且假設(shè)：在DFA M中，在輸入a上有從s到t的轉(zhuǎn)換。令t所在組的代表是r（r可能就是t），那么在M’中有一個從s到r的a上的轉(zhuǎn)換。令包含s0的狀態(tài)組的代表是M’的開始狀態(tài)，并令M’的接受狀態(tài)是那些屬于F集的狀態(tài)所在組的代表。注意，∏final的每個組或者僅含F中的狀態(tài)，或者不含F中的狀態(tài)。

5、 如果M’含有死狀態(tài)（即一個對所有輸入符號都有到自身的轉(zhuǎn)換的非接受狀態(tài)d），即從M’中去掉它；刪除從開始狀態(tài)不可到達(dá)的狀態(tài)；取消從任何其它狀態(tài)到死狀態(tài)的轉(zhuǎn)換定義。

?

?

3.2.3.??????????? 詞法分析器的設(shè)計過程

?

??? 詞法分析的任務(wù)是對輸入的字符串形式的源程序按順序進(jìn)行掃描，在掃描的同時，根據(jù)源語言的詞法規(guī)則識別具有獨(dú)立意義的單詞（符號），并產(chǎn)生與其等價的屬性字流（內(nèi)部編碼）作為輸出。通常屬性字流即是對識別的單詞給出的標(biāo)記符號的集合。

??? 詞法分析程序一般具有如下功能:讀入字符串形式的源程序;識別出具有獨(dú)立意義的最小語法單位:單詞。

??? 事實上，由正規(guī)表達(dá)式到最小化DFA的轉(zhuǎn)換源程序中的測試生成串部分就是對所輸入的單詞進(jìn)行判斷，看其是否能被生成的DFA接受（也就是這個單詞是否符合正規(guī)式定義的要求）。這本質(zhì)上就是一個簡單的詞法分析。為了更好地說明做這個題目的目的和意義，也為了使本文的主題得到升華，我另外設(shè)計了一個用于分析C語言詞法的簡單的詞法分析器，過程如下。

??? 定義某種語言的單詞，并給出編號。該語言單詞包括：保留字、運(yùn)算符、標(biāo)識符、常量、格式符等。根據(jù)給定的語言子集構(gòu)造詞法分析器。輸出為中間文件。在設(shè)計時為了便于理解，不使用內(nèi)部編碼而用中文字符對同類型的單詞進(jìn)行標(biāo)識。例如所有定義的關(guān)鍵字（保留字）統(tǒng)一用“關(guān)鍵字”對其進(jìn)行標(biāo)識，當(dāng)掃描時遇到關(guān)鍵字就輸出該關(guān)鍵字的字符串和“關(guān)鍵字”標(biāo)識。

?

?

?

詞法分析程序的一般設(shè)計方法：
??? 1、根據(jù)要求寫出詞法分析的正規(guī)文法G；
??? 2、根據(jù)正規(guī)文法G，寫出正則式RE；
??? 3、根據(jù)正則式RE，畫出NFA；
??? 4、將NFA轉(zhuǎn)化為DFA；
??? 5、將DFA轉(zhuǎn)化為mininum state DFA；
??? 6、mininum state? DFA就是詞法分析程序的流程圖，根據(jù)此流程圖編寫相應(yīng)的詞???????? 法分析程序。