編譯原理第2講詞法分析

0

4

第二講詞法分析

?詞法分析器的構造

?正規(guī)表達式與有窮自動機

?詞法分析器的自動產生

§1.詞法分析器的構造

編譯程序首先在單詞級別上來分析

和翻譯源程序。詞法分析的任務是：從

左至右逐個字符地對源程序進行掃描，

產生一個個單詞符號，即把作為字符串

的源程序改造成為單詞符號串的中間程

序。因此，詞法分析是編譯的基礎。執(zhí)

行詞法分析的程序稱為詞法分析器（通常

又稱為掃描器,scanner）。

Compilerprinciples2

一、一般考慮：

1.詞法分析程序的主要任務：

9讀入字符串形式的源程序一輸入

9剔除非單詞符號一空格符、換行符，跳過注釋

力拼單詞符號一**、：二、FOR、BEGIN等

s捻接語句行并產生語句結束標志

4源程序的列表輸出

小宏展開，...

Compilerprinciples3

2.詞法分析器的輸入和輸出形式

?輸入一字符串形式的源程序

?輸出一單詞符號串。

?程序語言的單詞符號一般分為五種：

關鍵字、運算符、界符、標識符、常數(shù)

?詞法分析器輸出的單詞符號常常表示為二元

式：

（單詞種別，單詞符號的屬性值）

Compilerprinciples4

★單詞種別通常用整數(shù)編碼

單詞種別是對單詞符號的一種分類。一

個語言的單詞符號如何分種，分成幾種，怎樣

編碼是一個技術性問題。它取決于處理上的方

便。標識符一般統(tǒng)歸為一種。常數(shù)則宜按類型

（整、實、布爾等）分種。關鍵字可視其全體

為一種，也可以一字一神。采用一字一科的分

法實際處理起來較為方便。運算符可采用一符

一種的分法，但也可以把具有一定共性的運算

符視為一種。至于界符一般用一符一種的分法。

Compilerprinciples5

★單詞符號屬性信息記錄單詞符號的特征或特性

如果一個種別只含有一個單詞符號，那么

對于這個單詞符號，種別編碼就完全代表它自

身了，因此屬性值就沒有意義了。若同一個種

別含有多個單詞符號，那麼，對于它的每個單

詞符號，除了給出種別編碼之外，還應給出各

有關單詞符號的屬性信息。

屬性值是反映特性或特征的值。例如，對

于某個標識符，常將存放它有關信息的符號表

項的指針作為其屬性值；對于某個常數(shù)，則將

存放該常數(shù)二進制表項的指針作為其屬性值。

Compilerprinciples6

作為例子考慮下述C++語句：

while(i〉二j)i-一；

若while種別為01,(種別為11,標識符種別為20,＞二種別

為12,)種別為13,——種別為14,;種別為30,則經(jīng)詞法

分析器處理后，它將被轉換為如下的單詞符號序列：

(01,—)

(11,—)

(20，指向i的符號表項的指針)

(12,—)

(20，指向j的符號表項的指針)

(13,—)

(20，指向i的符號表項的指針)

(14,—)

(30,—)

Compilerprinciples7

3.詞法分析器與語法分析器的銜接

通常把詞法分析器安排成一個獨立子程序，

而不是單獨的一遍。這樣一來，就無須在外存中

保留整個源程序的內碼形式，而是每當語法分析

器需要單詞符號時就調用這個子程序。每一次調

用，詞法分析器就從源程序字符串中識別出一個

單詞符號，把它交給語法分析器。這樣做的好處

是：

?壓縮編譯時掃描字符的時間：編譯時大量時間花費在

字符的掃描上；

?詞法規(guī)則描述簡單，便于建立掃描器的自動方法，便

于獨立研究；

?使得語法分析獲得更多信息；

?便于處理同一語言的幾種不同表示形式；

Compilerprinciples8

?:?由以上考慮，可以初步設計為:

Compilerprinciples9

二、進一步考慮：

1.輸入、預處理

詞法分析器工作的第一步是輸入源程序文本。輸

入串一般放在一個緩沖區(qū)中，這個緩沖區(qū)稱源程序

輸入緩沖區(qū)。詞法分析器的工作可以直接在這個緩

沖區(qū)中進行。但在許多情況下，把輸入串預處理一

下，對單詞符號的識別工作將是比較方便的。

預處理工作包括對空白符、跳格符、回車符和換

行符等編輯性字符的處理，及刪除注解等。于是可

以設想構造一個預處理子程序，它完成上面的工作。

每當詞法分析器調用它時就處理出一串確定長度的

輸入字符，并將其裝入詞法分析器所指定的緩沖區(qū)

中（稱為掃描緩沖區(qū)）。這樣分析器就可以在此緩

沖區(qū)中直接而方便地進行單詞符號的識別工作。

Compilerprinciples10

2,對半互補緩沖區(qū)

分析器對掃描緩沖區(qū)進行掃描時一般使用兩個

指示器，一個指向當前正在識別單詞的開始位置

（指向新單詞的首字符），另一個用于向前搜索以

尋找單詞的終點。但是不論掃描緩沖區(qū)設得多大都

不能保證單詞符號不會被緩沖區(qū)的邊界所打斷。因

此，掃描緩沖區(qū)最好使用一分為二的區(qū)域，并使兩

區(qū)首尾相接，形成一個對半互補緩沖區(qū)。

例如：每半個區(qū)可容64個字符，而這兩個半?yún)^(qū)又

是互補的。如果搜索指示器從單詞起點出發(fā)搜索到

半?yún)^(qū)的邊緣但尚未達到單詞的終點，那么就調用預

處理子程序，令其把后續(xù)的64個字符裝入另半?yún)^(qū)。

可以認定在另半?yún)^(qū)一定可以達到單詞的終點。這意

味著標示符和常數(shù)的長度實際上必須加以限制，否

則即使緩沖區(qū)再大也無濟于事。

Compilerprinciples11

綜上所述，預處理子程序、掃描器和語

法分析器相互之間的關系及工作情況可圖示

如下：

Compilerprinciples12

源程序

3.單詞符號識別一超前搜索技術

問題發(fā)生在對基本字不加任何保護的語言中，基

本字及用戶自定義的標識符或標號之間無特殊分界

符，這使得關鍵字的識別甚為麻煩。

請看下面的例子：

1DO99K=1,10

2IF(5.EQ.M)l=10

3DO99K=1.10

4IF(5)=55

這四個語句都是正確的FORTRAN語句。語句1和2

分別是D0和IF語句，它們都是以某基本字開頭的。

語句3和4是賦值語句，它們都是以用戶自定義的標

識符開頭的。

Compilerprinciples14

為了從1、2中識別出關鍵字DO和IF,我們必須

要能夠區(qū)別1、3和區(qū)別2、4O語句1、3的區(qū)別在于

等號之后的第一個界符：一個為逗號，另一個為小

數(shù)點，語句2、4的主要區(qū)別在于右括號后的第一個

字符：一個為字母，另一個為等號。這就是說，為

了識別1、2句中的關鍵字，我們必須超前掃描許多

個字符，超前到能夠肯定詞性的地方為止。對于1、

3來說，盡管都以‘）和’0,兩個字母開頭，但不

能一見'DO,就認定是DO語句。而必須超前搜索，

跳過所有的字母和數(shù)字，看看是否有等號。如果有，

再向前搜索。若下一個界符是逗號，則可以肯定D0

應為關鍵字。否則，D0不構成關鍵字，它只是用戶

標識符的頭兩個字母。

Compilerprinciples15

所以為了區(qū)別1和3,必須超前掃描若

干字符直到等號后的第一個界符處。對于2

和4來說，同樣需超前掃描到與IF后的左括

號相對應的那個右括號之后的第一個字符

為止。若此字符是字母，則得邏輯IF。若

此字符為數(shù)字，則得算術IF。否則，應認

為是用戶自定義標識符IF。這種向前掃描

若干字符直到找到能區(qū)分單詞的字符為止

的技術就叫超前搜索。

Compilerprinciples16

標識符的識別：標識符是字母開頭的一個

字母數(shù)字串，一般有運算符和界符分開，與基

本字的區(qū)別前已談及，所以容易識別。

常數(shù)的識別：算術常數(shù)大多相似，只是轉

換二進制的問題，但像3.E5、3.EQ.5顯然也要

用到超前搜索技術。另有3HABC一類的常數(shù)需

要特殊處理。

算符和界符的識別：算符和界符一般是單

一的一個符號，如+、-、*、/等。當然對于復

合的運算符，如++、+=等也只是拚寫的問題。

Compilerprinciples17

三、狀態(tài)轉換圖

現(xiàn)在有關掃描器的輸入、處理、輸出等問題及相

關技術都清楚了，可以進行掃描器的設計了。

根據(jù)高級語言的知識，在進行程序設計之前，首

先要將有關算法的求解過程通過某種圖形工具表示出

來。顯然，常用的程序流程圖、N-S圖等都不適用于

掃描器的設計，其原因就是單詞的識別不唯一。為此,

介紹一種新的圖形工具一一狀態(tài)轉換圖。[

1.使用狀態(tài)轉換圖是設計詞法分析器的一種好途徑；

狀態(tài)轉換圖是一張有限個結點的有向圖，結點代表狀

態(tài)，用圓圈表示，狀態(tài)之間用帶標識的箭弧連結，箭

弧上的標識代表在射出結點（即箭弧始結點）狀態(tài)下

可能出現(xiàn)的輸入字符或字符類。

Compilerprinciples18

如右圖所示：

在狀態(tài)1下，若輸入字

符為a,則讀進a,并轉

換到狀態(tài)2。若輸入字

符為b,則讀進b,并轉

換到狀態(tài)3。一張轉換

圖只包含有限個狀態(tài)

（即有限個結點），其

中有一個被認為是初態(tài),狀態(tài)轉換圖

而且實際上至少要有一

個終態(tài)（用雙圈表示），

圖中3為終態(tài)。

Compilerprinciples19

2■狀態(tài)轉換圖可用來識別一定的字符串

r例如：

V標識符＞一字母|V標識符〉字母|v標識符＞數(shù)字

字母或數(shù)字

字母

——<1數(shù)字

數(shù)字D其他*

v整數(shù)〉一數(shù)字卜整數(shù)〉數(shù)字n16

終態(tài)上打個*號，表示多讀進了一個不屬于該標識符或數(shù)

字部分的字符，應把它退還給輸入串。

或D

數(shù)字數(shù)字數(shù)字

數(shù)字E或D+或?數(shù)字其它*

0十1

數(shù)字

其它

6

Compilerprinciples坐懸用啰Fortran里蔓您叫要換國20

工蟒轉醺思以用來識別程序語言的單詞符號

產無非字母與數(shù)逗例：假設某程序語言只有前

)述的五類單詞符號，運算符

3字與字非數(shù)字.您*只有+、*、=，界符只有#、

)(、)，那么就可以用左邊的狀

態(tài)轉換圖來識別其所有單詞

0—1-2識別的串是基本

k--@

字還是標識符，要查保留字

表區(qū)分。

這兒還要加上兩個限制：

?所有基本字都是保留的；

?所有單詞間若無明顯分界,

0)則用一分開；

〔其它.嘉

Compilerprinciples\C1_1))

’一廣—:—一一「一「一廣—4—21

?為什么要引入“狀態(tài)”這一概念?

因為在程序語言中對單詞符號的識別不唯

一，就像上次談到的例子DO99l=1,10與

DO99U1.10一樣，要真正識別一個單詞，必

須對上下文進行分析。這樣一來使用狀態(tài)變化

是再合適不過的了。如果能夠像電報文那樣做

到——對應，如'1331'—'學'、'5045’一

'習’在什么地方都一樣，則可很容易通過一個

對應表來實現(xiàn)，也就用不著“狀態(tài)轉換”了。

Compilerprinciples22

4?狀態(tài)轉換圖的程序實現(xiàn)一■每個狀態(tài)對應一小

干段程序即可

例：使用如下一組全局變量和過程，作為實現(xiàn)狀態(tài)轉換圖的基

本部分：

⑴CHAR：字符變量，存放最新讀進的源程序字符；

⑵Token：字符數(shù)組，存放構成單詞符號的符號串；

⑶GetChar：取字符過程，將下一個輸入字符讀到CHAR中，并

把搜索指示器的指針前移一個字符位置；

(4)GetBC：檢查CHAR中的字符是否為空白，若是則調用

GetChar直至CHAR中進入一個非空白字符；

⑸ConCat：拼單詞過程，每調用一次就將CHAR中的字符連接

到Token之后;

(6)IsLetter和IsDigit：兩個布爾函數(shù)，分別判斷CHAR中的字

符為字母或是數(shù)字而返回真假值；

⑺Reserve：整型函數(shù)，對Token中的字符串查保留字表，查

到則返回該保留字的整型編碼，否則返回0值；

.

Compilerprinciples23

(8)Retract：回退子程序，專門用來把搜索指示器

回調一個字符位置，并置CHAR為空；

(9)Error：出錯處理子程序；

⑩DTB：類型轉換函數(shù)，將Token中的十進制數(shù)轉

換為二進制數(shù)；

于是，可編出如下程序:

。Start:Token:=t5;

GetChar;GetBC;

Compilerprinciples24

CASECHAROF

A..z':BEGIN

WHILEIsLetterORIsDigitDOBEGINConCat;GetCharEND;

Retract;C:=Reserve;

IFC=0THENReturn($ID,Token)ELSEReturn(C-)

END;)

0.9:BEGINX

WHILEIsDigitDOBEGINConCat;GetCharEND;

Retract;Return($INT,DTB)

END;1

一:Return($ASSIGN,-);\

中：Return($PLUS,-);1

Return($START,-);j

t：Return($LPAR,-);

Return($RPAR,-);(

Return($,—);

CEbNmDpilerPPnFncipleCsASE;‘Error;'GotoStart;’2”5

§2.正規(guī)表達式與有窮自動機

RegularExpressionandFiniteAutomaton

上一節(jié)我們討論了掃描器的手工編制，是在討論了

Scanner的主要工作--拼單詞符號并進行相應的詞法

檢查-一的基礎上，通過狀態(tài)轉換圖來構造的。本節(jié)要

對狀態(tài)轉換圖稍加形式化，以便進一步討論詞法分析

程序的自動生成問題。

由于我們集中注意力于掃描器的自動生成，故對

有關結論一般不加形式證明，大家若對這方面感興趣,

可以查閱相關書籍，如《形式語言與自動機的關系》

-^書(FormalLanguageAndTheirRelationTo

Automaton)。

Compilerprinciples26

一、正規(guī)表達式和正規(guī)集

廠贏I知道，任何高級程序設計語言都有自己的字

母表，但并非字母表上的任何字符串都能稱為一個程

序，我們感興趣的是能稱為程序的那些串，它們的集

合稱為正規(guī)集。正規(guī)式是說明單詞的模式(pattern)的

一種重要的表示法(記號)，是定義正規(guī)集的數(shù)學工

具，可用以描述單詞符號。這同樣是一個無窮語言的

有窮描述的問題。

1.正規(guī)式(RE)的定義：

這是一種與我們以前常見的算術、邏輯等表達式

不同的表達式。設Z為字母表，

⑴￡和0都是Z上的正規(guī)式，它們所表示的正規(guī)集分別

為任｝和0；

⑵對于任何a都是Z上的一個正規(guī)式，它所表示

的正規(guī)集為｛a｝；

Compilerprinciples27

⑶假定U和V都是Z上的正規(guī)式，它們所表示的正規(guī)集

分別記為L(U)和L(V),那么，(U|V),(UV)*和(U)*也都

是正規(guī)式，它們所表示的正規(guī)集分別為L(U)UL(V),

L(U)L(V)(連接積)和(L(U))*(閉包)。

僅由有限次使用上述三步驟而得到的表達式才是

E上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是E

上的正規(guī)集。

*這個定義本身是構造型的，今后我們應該習慣這種

構造型定義及證明方式。

Compilerprinciples28

2,正規(guī)表達式的運算順序：

括號一*（閉包）f?（連接）fI（或）

例1：Z={a，b}o

都是正規(guī)式

二?a*是正規(guī)式，ba*也是正規(guī)式。

它所表示的正規(guī)集為：{b,ba,baa,......},也就

是Z上所有以b為首后跟著任意多個a的字。

同樣，a（a|b）*亦為Z上的正規(guī)式，其所表示的正

規(guī)集為Z上所有以a%首的字；（a|b）*（aabb）（a|b）*

對應的正規(guī)集是所有含有兩個相繼的a或相繼的b的

Compilerprinciples29

例2：令Z={A,BQ1},則：

(A|B)(A|B|0|1)*={A,B,AA,AB,A0,A1,BA,BB,

——Z上的“標識符”的全體

(0|1)(0|1)*={0100,01,10,11,…}——Z上

“數(shù)”的全體

*實際上可以說：正規(guī)式的值就是正規(guī)集。

Compilerprinciples30

3.正規(guī)表達式的等價：

若兩個正規(guī)式所表示的正規(guī)集(值)相同，則認

為二者等價，記為'二’。

例：Z={a,b}

Vb(ab)*={b,bab,babab,...}

(ba)*b={b,bab,babab,...}

b(ab)*=(ba)*b

Compilerprinciples31

4,正規(guī)表達式的運算律:

UIV=VIU（交換律）

UI(VIW)=(U|V)Iw（結合律）

U(VW)=(UV)w（結合律）

U(VIW)=UVIuw（分配律）

(UIV)W=UWIVW（分配律）

￡U=U￡=U（幺元）

3主意，這里的每條運算律都需要證明。

Compilerprinciples32

二、確定的有窮自動機(DFA)

1.問題的提出：上節(jié)我們介紹了狀態(tài)轉換圖:

......，⑤

我們也可以寫：

Sg^aSpS(So,a)=SX

Si-bS/b(Sb)=S

乙_nL乙2

于是我們可以認為所有狀態(tài)構成一個集合s,所有弧

的標識構成一個集合Z，函數(shù)6,起始狀態(tài)S。和所

有終態(tài)構成的集合F。這樣我們可以把狀態(tài)轉換圖

形式化為如下的數(shù)學系統(tǒng)一DFA。

Compilerprinciples33

2.形式定義：

I確定有限自動機(DFA)是一個五元式系統(tǒng)：

DFAM=(S,Z,6,s0,F)其中：

(1)S是一個有限集，它的每個元素稱為一個狀態(tài)。

(2)E是一個有窮字母集，它的每個元素稱為一個輸

入字符。

(3)6是一個從SxE-S的單值部分映射。

6(s,a)意味著：當現(xiàn)行狀態(tài)為s、輸入字符為a

時，將轉換到下一個狀態(tài)s)我們稱S為s的后繼狀

o

(4)s0eS,是唯一的初態(tài)。

(5)FoS,是一個終態(tài)集(可空)。

CompilerPrinciples34

3.DFA的表示形式：

由前所述，DFA是狀態(tài)轉換圖的抽象

模型。顯然DFA也可以表示成一張（確定

的）狀態(tài)轉換圖，它們是一一對應的。

假定DFAM含有m個狀態(tài)、n個輸入字

符，那末，這張圖含有m個狀態(tài)結點，每

個結點頂多有n條箭弧射出和別的結點相連

接，每條箭弧用，上的一個字符作標記，整

張圖含有唯一的初態(tài)和若干個（可以是。個）

終態(tài)結點。

Compilerprinciples35

$DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài),

列表示輸入字符，矩陣元素表示b(s,a)的值，該矩

陣稱為狀態(tài)轉換矩陣。

狀態(tài)轉換圖狀態(tài)轉換矩陣

Compilerprinciples36

對于E*中的任何一個字符串a,若存在一條

從初態(tài)結點到某一終態(tài)結點的通路，且這條通路

上所有箭弧的標記符連接成的字等于a,則稱a為

DFAM所識別(讀出或接受)。

若M的初態(tài)結點同時又是終態(tài)結點，則空字？

可以為M所識別。DFAM所能識別的字的全體記

為L(M).

DFA的確定性表現(xiàn)在6是一個從SxE-S的

單值部分映射。也就是說，對任何狀態(tài)s$S和輸

入符號awZ,6(s,a)唯一地確定了下一個狀態(tài)。

從狀態(tài)轉換圖的角度來看，任何狀態(tài)發(fā)出的弧具

有不同的標識。

Compilerprinciples37

例:

解：有0,1,2,3共四個狀態(tài)。

輸入字符為a,b兩個。其狀態(tài)轉

換圖如若

L(M)為在2上含相繼兩個a或相繼

而個b的字的集合。

Compilerprinciples38

三、不確定的有窮自動機(NFA)

1.形式定義

一個不確定有限自動機(NFA)是一個五元式系統(tǒng)

M=(S,Z,6,S0,F)其中：

(1)S是一個有限集，它的每個元素稱為一個狀態(tài)。

(2)￡是一個有窮字母集，它的每個元素稱為一個輸

入字符。

(3)6是一個從SxZ*-S的子集的映射，即

6：SxZ*一2s

(4)S0=S,是一個非空的初態(tài)集；

(5)FoS,是一個終態(tài)集(可空)

空不難看出，DFA是NFA的一個特例，而NFA在定理

證明中很有用。

Compilerprinciples39

顯然，NFA也可以表示成一張狀態(tài)轉換圖。假定NFA

含有m個狀態(tài)、n個輸入字符，那么，這張圖含有m個狀態(tài)

結點，每個結點可以射出若干條箭弧和別的結點相連接，每

條箭弧用尹上的一個字（不一定要不同的字而且可以是空字

E）作標記（稱為輸入字），整張圖至少含有一個初態(tài)和若

干個（可以是。個）終態(tài)結點。某些結點既可以是初態(tài)也可

以是終態(tài)結點。

對于中中的任何一個字符a,若存在一條從初態(tài)結點到

某一終態(tài)結點的通路，旦這條通路上所有箭弧的標記符連接

成的字（忽略那些標記為e的?。┑扔赼,則稱a為NFAM所

識別。也就是：6（S0,a）AF^（po

若M的初態(tài)結點同時又是終態(tài)結點，或者存在一條某初

態(tài)結點到某各終態(tài)結點的g通路，則空字￡可以為M所識別。

Compilerprinciples40

，例:M=({0,1,2,3,4},{a,b},6,{0},{2,4})，其中b：

6(0,a尸{0,3},5(1,a)=cp,5(2,a)={2},

5(3,a)={4},5(4,a)={4},6(0,b)={0,1},

5(1,b)={2},5(2,b)={2},5(3,b)=q),

5(4,b)={4}

Compilerprinciples41

2.有窮自動機的等價:

對于任何兩個有窮自動機M和M',如

果L(M尸L(M'),則稱M和M'是等價的。對

此我們有一個重要結論：判定任何兩個有

窮自動機等價的算法是存在的。

Compilerprinciples42

四、正規(guī)式與有窮自動機的等價性：

｛我們先來證明兩個重要的事實：

1,定理1：Z上的有窮自動機所接受的字的全體

13)是￡上的一個正規(guī)集。

⑴一般考慮：要證明L(M)是Z上的一個正規(guī)集，很容

易想到正規(guī)式。因為正規(guī)集是正規(guī)式的值。同時我

們又知道任何一個FAM都可以表示成一個狀態(tài)轉

換圖，而該圖中從某個初態(tài)結點到某個終態(tài)結點的

路上所有弧的標記連接而成的串，恰恰就是L(M)的

一個字，L(M)就是這樣一些字的全體，于是我們想，

是否能構造一個正規(guī)表達式V,使得L(V)=L(M)呢？

如果能構造出這樣的一個V,問題也就解決了。為此,

我們把轉換圖的概念加以拓廣y更每條弧g用一(

個正期疝耒標記，如fo)alb

這樣我們就可以借助M來構造Vf

Compilerprinciples43

(2)證明(簡略)：

a.在NFAM的狀態(tài)轉換圖上加入唯一的初態(tài)X和終態(tài)Y,從X

到M原來的每個初態(tài)用標有￡的弧相連接，而每個原終態(tài)則用

標有￡的弧與丫相連接。顯然這樣的NFAM與NFAM'是等

價的一L(M')=L(M)。

b.反復使用以下規(guī)則對M'中的所有狀態(tài)進行逐步消去：

由于M'的狀態(tài)集是有限則因此經(jīng)過有限次使用上述規(guī)則，

必然得到QV，顯然L(V)=L(M')=L(M)o

lpilerPrinciples對迪JpA典情加1二般性，凈用紳M則更簡單。44

例:a,b

⑤(a(ba)*(aIbb)Ib(ab)*(bIaa))(aIb)*包

這樣就得到了與所給DFA等價的正規(guī)式。

Compilerprinciples45

2,定理2：對于Z上的每個正規(guī)表達式V,存在

一個Z上的DFAM,使得L(M)=L(V)。

⑴一般考慮：由定理1的證明，我們很容易想到，對

z上的每個正規(guī)式V,可以畫出拓廣轉換圖：

然后我們與逐次減少緒冷過程相反，可以對V逐次

分裂并加入新結點和弧，直到每條弧的標記或者為

Z中的一個符號，或者為￡,這樣就構造了一個轉

換圖，也就是一個NFAM',然后再把M'確定化為DFA

就可以了。

Compilerprinciples46

(2)證明:

a.把正規(guī)式V表示成拓廣轉換圖

b.根據(jù)以下規(guī)則分裂V并加入新狀態(tài)結點和標識弧

整個分裂過程保戰(zhàn)"和①為唯一初態(tài)和終態(tài)，由

正規(guī)式定義，顯然經(jīng)過有限次分裂就可以構造出一

個NFAM'使得L(M0=L(V)o

Compilerprinciples47

c.對NFAM'確定化一構造一個DFAM使得L(M)=L(M‘)

*一般考慮：變多值映射為單值映射，可采用子集法。NFA

不確定的原因主要在于含有￡弧和從某結點經(jīng)由相同標識的

弧而到達不同的結點——結點集。這兩個問題解決了，NFA

也就確定了。

①預備定義L狀態(tài)集I的2閉包，記為

￡.CLOSURE(I),如下定義:

i.若sWl,貝出￡￡_CLOSURE(I)；

ii.若s￡l,則由s出發(fā)經(jīng)任意條g弧而能夠到

達的任何狀態(tài)s'￡￡_CLOSURE(I)；

②預備定義2：對狀態(tài)集I和,定義

I,氣_CLOSURE(J)；其中J是那些可從I中某一結點出發(fā)經(jīng)

過一條a弧(跳過a前的任意條￡弧)而到達的狀態(tài)結點的全

體。

Compilerprinciples48

。設I={1},則由I經(jīng)一條a弧而到達的狀態(tài)結點

的全體體{5,3,4},從而

I=8.CLOSURE(J)={5,6,2,3,8,4,7}

C-X

Compilerprinciples49

③W的確定化：從以上所談不難看出確定化的復雜程度

與符號個數(shù)密切相關，為此我們設Z二{a,b},并依如下過程

構造一個轉換矩陣。

該矩陣有三列，分別記為I,L，兒，第一行第一列置為

￡.CLOSURE({X}),其中X為M，的初態(tài)集。由此我們就可以

根據(jù)預備定義構造la和兒，然后檢查心、兒中是否有不同于

已構造出的I的，若有則將其作為新的I，又可以構造新的M

和lb。依次下去，直到不再有新的狀態(tài)子集出現(xiàn)為止。因為

的狀態(tài)數(shù)是有限的，故上述過程必在有限步內停止。把

上述表中第一列的狀態(tài)子集進行編號，最終可得到一個狀態(tài)

矩陣，該矩陣唯一地畫出了一個確定的有窮自動機M,其唯

一初態(tài)為E-CLOSURE({X}),終態(tài)是那些含有M，的終態(tài)Y的

子集。

由上述構造過程不難看出：L(M)=L(W),于是達到了確

定化的目的。

Compilerprinciples50

?例:設V=(a|b)*(aa|bb)(a|b)*

Ila

Ib

{X,5,1){5,3,1){5}4,1)

{5}3,1){5,1,326,Y}{5}4,1)

(5,4,1}{5}3,1){5,1,4,26Y}

{5,1,3,2,6,Y){5,1,326,丫}{5,1,4,6,Y)

{5,1,4,26丫}{5,136,Y}{5,1,4,26丫}

{5,1,4,6,Y}{5,1,3,6,Y){5,1,4,2,6,Y)

{5,1,3,6,Y}{5,1,3,2,6,Y){5,146,Y}

Compilerprinciples51

(3)重新編號的狀態(tài)矩陣：(4)DFAM的狀態(tài)轉換圖為:

a

Saba

15

072

132oaa

214

3352a

464

564

635

(5)DFAM=({0,1,2,3,4,5,6},{a,b},6,0,{3,4,5,6}),

其中b如左上表所示。

Compilerprinciples52

3.推論1：一個字集V是正規(guī)的仁會有二自動機M工使得

L(M)=L(V)O飛Ifandonlyif|

推論2：NFA與DFA接收相同的集合。

［定理］:推論2也可作為一個定理來證明：若L(M)被

NFAM接受，則必定存在一個DFAM'接受L(M)一

NFA與DFA接收相同的集合。

證明:設M=(SNb,S0,Z)為一接受L(M)的NFA,如下構

造DFAM'=(S'N6',So',Z)其中S'=2S,Z'為

一狀態(tài)集,它的每個元素都含有Z的一個狀態(tài)(注

意:Z'的元素亦為狀態(tài)集)且ZAS',而S2,-SJ

表示S'的一個元素,其中S1，S2,…Si都在S中，

S°二｛S。｝.

Compilerprinciples53

3(51，S2,-Si：,a)=[P],P2,…Pj]當且僅當

5({SpS2,-8^,3)={PpP2,-PJ,即通過把b作用到由

Q={S],S2,…SJ表示的S的每個狀態(tài)上，來計算&被應用到S'的

一個元素Q的結果。通過把5應用到Sp52,…Sj的每一個元素上

并求和，我們便得到狀態(tài)的某一個新集{Pi，P2,…PJ，這種狀態(tài)

的新集在S'中有一個代表[P”P2,…PJ,而它便是

Z

5([SPS2,-SJ,a)的值。剩下來的問題是證明L(M’尸L(M)!

下面我們通過對輸入字x的長度作歸納容易證明：

&(So',x)=[Si，S2,…SJ當且僅當b(So，x尸母1$2,…SJ.

由于So'={So},故對|x|=0結果顯然成立。現(xiàn)假設|x|二k時

成立，則對E中的a,5(S0,xa)=5(5(So,x),a)o由歸納假

設知S(So',x)=[P],P2,…PJ當且僅當b(So，x尸{P1F2,…PJ，但

由定義：&(產1,…Pj],a尸/怔2,…當且僅當“伊1,…即間=

{%「2,…7},因此b(So,xa尸…當且僅當b(So，xa尸

其次，僅當b(So，x)含有Z中的S的一種狀態(tài)時，3(So',x)便

在Z'中，因此L(M'尸L(M)。定理證畢。

Compilerprinciples54

Z*中的x被M接受,則譏S°,x)nZAp,又

據(jù)Z'是S中含有Z的一個狀態(tài)的集合，故

第60‘歡)在2'中，當然x為M'接受。

這個證明過程一般不預介紹。

由以上的定理及推論，我們知道任何一

正規(guī)集上，我們都可以構造一個NFAM接受

V,而對任何一個NFAM我們又都能構造一

個接收相同集合的DFAM',現(xiàn)在我們可能會

想到DFA是否可以化簡呢，或者說是否可以

找一個狀態(tài)最少的DFA接受相同的字集呢？

下面我們就來討論這個問題。

Compilerprinciples55

四、DFA的化簡

?:?所謂對一個DFAM的化簡，就是找一個DFA

M',使得L(M尸L(M')但是M'的狀態(tài)數(shù)比M少。

1,等價狀態(tài)和可區(qū)別狀態(tài)：若分別從狀態(tài)s和t

出發(fā)而停于終態(tài)能讀出同一個字a,則稱s,t為

等價狀態(tài)；不等價的兩個狀態(tài)稱為可區(qū)別狀

2.狀態(tài)的最小化過程

*所謂DFAM的狀態(tài)最小化過程就是找一個最

少狀態(tài)的DFAM'使得L(M尸L(M')。

。具體做法：把DFAM的狀態(tài)集分割成一些不

相交的子集，使得不同的兩個子集的狀態(tài)都

是可區(qū)別的，而同一子集中的任何兩個狀態(tài)

都是等價的，最后讓每個子集選出一個代表,

把所有與該子集相關的弧都與該代表相連接,

并消去其他等價狀態(tài)，即可求得最少狀態(tài)的

DFAM\——子集法

下面我們結合具體的例子說明該方法：

Compilerprinciples57

3.例：DFAM=({0,1,2,3,45,6},{a,b},6,0,{3,4,5,6})

其中b：6(0,a)=1,6(0,b)=2,6(1,a)=3,6(1,b)=2,

6(2,a)=1,6(2,b)=4,6(3,a)=3,6(3,b)=5,

6(4,a)=6,6(4,b)=4,6(5,a)=6,6(5,b)=4,

6(6,a)=3,6(6,b)=5.

(1)形成基本分

劃TT—分成兩個子

集:非終態(tài)子集I⑴

和終態(tài)子集I⑵即:

1(1)={0,1,2)

1(2)={3,4,5,6)

Compilerprinciples58

(2)對每個子集I⑴和每個a,來考察M⑴是否包含

在某個I。)中(F1,2,…n),若不是完全包含在某個

I(j)中則至少可一分為二，形成新的分劃。

(1)

例：Ia={0,1,2}a={l,3}而{1,3}不在rr的任一子

集中，故應分割。又因{0,2}『{1},故分成{0,2}和

口},顯然⑴是不能再分割的了。至此得到：

TTr={{0,2},{1},{3,4,5,6))

⑶重復⑵的工作直到所有子集不能再分割為止。

{0,2}『⑵4}不在任一子集中，故一分為二得：

TT'二{{0},{1},{2},{3,4,5,6}),而{3,4,5,6號

={3,6}c{3,4,5,6},{3,4,5,6}b={5,4}c{3,4,5,6),

不能再分割了。所以最后的分劃：

。

CompilerprinciplesTT={{0},{1},{2},{3,4,5,6}}59

(4)選等價狀態(tài)子集的代表，并重構狀態(tài)圖。

如｛3,4,5,6｝的代表為｛3｝,可得狀態(tài)圖：

(5)最后可得最少狀態(tài)自動機為：

DFAM'=({0,1,2,3},{a,b},6,0,{3}),其中6：

6(0,a)=1,6(0,b)=2,6(1,a)=3,6(1,b)=2,

6(2,a)=1,6(2,b)=3,6(3,a)=3,6(3,b)=3.

Compilerprinciples60

§3.詞法分析器的自動產生

前面我們已經(jīng)談了狀態(tài)轉換圖可以用

來識別單詞符號，DFA可以用一張確定的

狀態(tài)轉換圖來表示，而DFA又與正規(guī)式等

價，所以我們可以用正規(guī)式來描述程序

語言的詞法。這一節(jié)我們討論如何從正

規(guī)式產生掃描器。首先介紹一個描述掃

描器的語言一LEX(LexicalAnalyser),

討論其實現(xiàn)(即研究它的編譯器的構

造)，進而用它來描述并自動生成各種

掃描器。

Compilerprinciples61

一個描述掃描器的LEX程序由一組正規(guī)式以及

與每個正規(guī)式相對應的一個“動作"（Action）組成。

“動作”本身是一小段程序代碼，它指出了當按正

規(guī)式識別出一個單詞符號時應采取的行動。將LEX

程序編譯后所得的結果程序記為L,其作用就如同

一個有限自動機一樣，可用來識別和產生單詞符號。

該結果程序由一張狀態(tài)轉換表和一個控制程序組成。

LEX程序及其編譯程序的作用可圖示如下：

輸入串

_____SZ

Lex源程序-----"Lex編譯程序掃描器

單詞符號串。

Compilerprinciples62

一、LEX語言簡介

!LEX源程序由兩部分組成：正規(guī)式和識別規(guī)則。

1.正規(guī)(輔助定義)式：——相當于說明部分，放在

LEX語言程序的首部。

(1)作用：定義程序語言的各種單詞符號。

5稱為n的簡名。

Compilerprinciples63

?約定n中只許出現(xiàn)z中的字符和前面已經(jīng)定義的

簡名白,d2，??.4i,不得出現(xiàn)未定義的簡名，這樣就保

證了庫個n都臭一個正規(guī)式，一般用小寫字符串記熊

例如C語言的標識符可如下定義：

letter—AIB|...IZIa|b|???|z

digit-0|1|...|9

id-letter(letterIdigit)*

2.(單詞符號)識別規(guī)則：——相當于執(zhí)行語句。

(1)作用：用來識別單詞符號；

(2)語句形式：

Pi{AJ

P2{A2}

Pn6}

Compilerprinciples64

這兒Pj(j=1,2,…n)稱詞形,而Aj為動作。這一

小段程序代碼指出當識別出詞形Pj這種單詞后，掃

描器要采取的動作。當然這兒Pj必須是定義在

ZU{dl,…dn}上的正規(guī)式。顯然這樣所產生的掃描

器L只能識別具有詞形為Pl,P2,…Pn的單詞符號。

每個詞形Pj所對應的動作Aj的基本組成成分是

“返回Pj的種別碼和屬性值”----Return(Code,

Value)o如Pj是“標識符”，則Value為符號表入口

指針；若Pj是“常數(shù)”，則Value為常數(shù)表入口指針;

若Pj既不是標識符也不是某種常數(shù)，那么，Value便

無定義。

Compilerprinciples65

?：?L的工作是掃描輸入字符串，尋找一

個最長子串與Pj進行匹配，一旦匹配成功,

就調用相應的Aj；若找不到任何詞形與現(xiàn)

行輸入串相匹配，貝扎應報告輸入串含有

錯誤（如非法字符），并進行善后處理；

但也可能存在一個最長子串，可以匹配若

干個不同的Pj,此時就先匹配LEX程序中

出現(xiàn)在最前面的那個Pj。其他細節(jié)請見教

材P59?60。

Compilerprinciples66

二、LEX的實現(xiàn)

LEX程序的編譯過程是一目了然的。首先,

對每條識別規(guī)則Pj構造一個相應的NFAMj,

然后引入新的初態(tài)X,通過￡將這些自動機連

接成一個新的NFA（圖示如下）；

最后用子集法把這個NFA確定化為DFA,必要

時還可化簡。其他有關細節(jié)我們就不談了，

望大家下去自己看書。

Compilerprinciples67

小結

本講內容：

★詞法分析器的構造

★狀態(tài)轉換圖

★正規(guī)表達式與正規(guī)集

★DFA與NFA

★RE,RG,DFA,NFA的等價關系

★DFA的最小化

Compilerprinciples68

（功能：分割字符串形式的源程序，得到單詞符號串

輸入：字符串形式的源程序

詞

輸出：單詞符號串（二元式）

法--

分析技術f超前搜索

分<1對半互補緩沖區(qū)

析預處理子程序

設計,獨立子程序

器

狀態(tài)轉換圖一最小化DFA的狀態(tài)轉換圖

實現(xiàn)：最小化的DFA的每個狀態(tài)對應一小段程序

DFA化簡：

轉換規(guī)則

RE-----------

增加開始狀態(tài)、子集法劃分等.最小化

rAfBaa----------->NFA---------"DFA價類'DFA

RGJ增加終止狀與/

IAfaBa-----------/

Compilerprinciples69

例題與習題解答

［例1］寫能被5整除的十進制整數(shù)的文法及正則表

達式。

解：能被5整除的文法：

G［Z］：Z-(+k)A(0|5)

A一0|1|2|3|4|5|6|7|8191AA

正則表達式:(+|-)A*(0|5)

Ae{0,1,2,3,4,5,6,7,8,9}

如果要求：除零以外不以0開頭，則文法為：

G［Z］：Z->(+|-)A(0|5)

ARABICB—O|C|BB

C一1|2|3|4|5|6|7|8|9

Compilerprinciples70

[例2]

寫一個文法，使其語言是奇數(shù)集，且每個

奇數(shù)不以0開頭。

解：文法G(N)：

N—AB|B

A—AC|D

B一1|3|5|7|9

D—B|2|4|6|8

C—O|D

Compilerprinciples71

［例3］寫出能被3整除十進制整數(shù)的文法和正則表達式:

解：能被3整除的文法：

G=({0,1,2,3,4,5,6,7,8,9},{S,A,B),S,P),其中P為：

S