編譯原理第2講詞法分析

0

4

第二講詞法分析

?詞法分析器的構(gòu)造

?正規(guī)表達(dá)式與有窮自動(dòng)機(jī)

?詞法分析器的自動(dòng)產(chǎn)生

§1.詞法分析器的構(gòu)造

編譯程序首先在單詞級(jí)別上來分析

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

左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，

產(chǎn)生一個(gè)個(gè)單詞符號(hào)，即把作為字符串

的源程序改造成為單詞符號(hào)串的中間程

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

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

又稱為掃描器,scanner）。

Compilerprinciples2

一、一般考慮：

1.詞法分析程序的主要任務(wù)：

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

9剔除非單詞符號(hào)一空格符、換行符，跳過注釋

力拼單詞符號(hào)一**、：二、FOR、BEGIN等

s捻接語句行并產(chǎn)生語句結(jié)束標(biāo)志

4源程序的列表輸出

小宏展開，...

Compilerprinciples3

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

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

?輸出一單詞符號(hào)串。

?程序語言的單詞符號(hào)一般分為五種：

關(guān)鍵字、運(yùn)算符、界符、標(biāo)識(shí)符、常數(shù)

?詞法分析器輸出的單詞符號(hào)常常表示為二元

式：

（單詞種別，單詞符號(hào)的屬性值）

Compilerprinciples4

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

單詞種別是對(duì)單詞符號(hào)的一種分類。一

個(gè)語言的單詞符號(hào)如何分種，分成幾種，怎樣

編碼是一個(gè)技術(shù)性問題。它取決于處理上的方

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

（整、實(shí)、布爾等）分種。關(guān)鍵字可視其全體

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

法實(shí)際處理起來較為方便。運(yùn)算符可采用一符

一種的分法，但也可以把具有一定共性的運(yùn)算

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

Compilerprinciples5

★單詞符號(hào)屬性信息記錄單詞符號(hào)的特征或特性

如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么

對(duì)于這個(gè)單詞符號(hào)，種別編碼就完全代表它自

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

別含有多個(gè)單詞符號(hào)，那麼，對(duì)于它的每個(gè)單

詞符號(hào)，除了給出種別編碼之外，還應(yīng)給出各

有關(guān)單詞符號(hào)的屬性信息。

屬性值是反映特性或特征的值。例如，對(duì)

于某個(gè)標(biāo)識(shí)符，常將存放它有關(guān)信息的符號(hào)表

項(xiàng)的指針作為其屬性值；對(duì)于某個(gè)常數(shù)，則將

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

Compilerprinciples6

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

while(i〉二j)i-一；

若while種別為01,(種別為11,標(biāo)識(shí)符種別為20,＞二種別

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

分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號(hào)序列：

(01,—)

(11,—)

(20，指向i的符號(hào)表項(xiàng)的指針)

(12,—)

(20，指向j的符號(hào)表項(xiàng)的指針)

(13,—)

(20，指向i的符號(hào)表項(xiàng)的指針)

(14,—)

(30,—)

Compilerprinciples7

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

通常把詞法分析器安排成一個(gè)獨(dú)立子程序，

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

保留整個(gè)源程序的內(nèi)碼形式，而是每當(dāng)語法分析

器需要單詞符號(hào)時(shí)就調(diào)用這個(gè)子程序。每一次調(diào)

用，詞法分析器就從源程序字符串中識(shí)別出一個(gè)

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

是：

?壓縮編譯時(shí)掃描字符的時(shí)間：編譯時(shí)大量時(shí)間花費(fèi)在

字符的掃描上；

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

于獨(dú)立研究；

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

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

Compilerprinciples8

?:?由以上考慮，可以初步設(shè)計(jì)為:

Compilerprinciples9

二、進(jìn)一步考慮：

1.輸入、預(yù)處理

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

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

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

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

下，對(duì)單詞符號(hào)的識(shí)別工作將是比較方便的。

預(yù)處理工作包括對(duì)空白符、跳格符、回車符和換

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

以設(shè)想構(gòu)造一個(gè)預(yù)處理子程序，它完成上面的工作。

每當(dāng)詞法分析器調(diào)用它時(shí)就處理出一串確定長度的

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

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

沖區(qū)中直接而方便地進(jìn)行單詞符號(hào)的識(shí)別工作。

Compilerprinciples10

2,對(duì)半互補(bǔ)緩沖區(qū)

分析器對(duì)掃描緩沖區(qū)進(jìn)行掃描時(shí)一般使用兩個(gè)

指示器，一個(gè)指向當(dāng)前正在識(shí)別單詞的開始位置

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

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

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

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

區(qū)首尾相接，形成一個(gè)對(duì)半互補(bǔ)緩沖區(qū)。

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

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

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

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

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

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

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

Compilerprinciples11

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

法分析器相互之間的關(guān)系及工作情況可圖示

如下：

Compilerprinciples12

源程序

3.單詞符號(hào)識(shí)別一超前搜索技術(shù)

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

本字及用戶自定義的標(biāo)識(shí)符或標(biāo)號(hào)之間無特殊分界

符，這使得關(guān)鍵字的識(shí)別甚為麻煩。

請(qǐng)看下面的例子：

1DO99K=1,10

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

3DO99K=1.10

4IF(5)=55

這四個(gè)語句都是正確的FORTRAN語句。語句1和2

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

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

識(shí)符開頭的。

Compilerprinciples14

為了從1、2中識(shí)別出關(guān)鍵字DO和IF,我們必須

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

等號(hào)之后的第一個(gè)界符：一個(gè)為逗號(hào)，另一個(gè)為小

數(shù)點(diǎn)，語句2、4的主要區(qū)別在于右括號(hào)后的第一個(gè)

字符：一個(gè)為字母，另一個(gè)為等號(hào)。這就是說，為

了識(shí)別1、2句中的關(guān)鍵字，我們必須超前掃描許多

個(gè)字符，超前到能夠肯定詞性的地方為止。對(duì)于1、

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

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

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

再向前搜索。若下一個(gè)界符是逗號(hào)，則可以肯定D0

應(yīng)為關(guān)鍵字。否則，D0不構(gòu)成關(guān)鍵字，它只是用戶

標(biāo)識(shí)符的頭兩個(gè)字母。

Compilerprinciples15

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

干字符直到等號(hào)后的第一個(gè)界符處。對(duì)于2

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

號(hào)相對(duì)應(yīng)的那個(gè)右括號(hào)之后的第一個(gè)字符

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

此字符為數(shù)字，則得算術(shù)IF。否則，應(yīng)認(rèn)

為是用戶自定義標(biāo)識(shí)符IF。這種向前掃描

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

的技術(shù)就叫超前搜索。

Compilerprinciples16

標(biāo)識(shí)符的識(shí)別：標(biāo)識(shí)符是字母開頭的一個(gè)

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

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

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

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

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

要特殊處理。

算符和界符的識(shí)別：算符和界符一般是單

一的一個(gè)符號(hào)，如+、-、*、/等。當(dāng)然對(duì)于復(fù)

合的運(yùn)算符，如++、+=等也只是拚寫的問題。

Compilerprinciples17

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

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

關(guān)技術(shù)都清楚了，可以進(jìn)行掃描器的設(shè)計(jì)了。

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

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

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

掃描器的設(shè)計(jì)，其原因就是單詞的識(shí)別不唯一。為此,

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

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

狀態(tài)轉(zhuǎn)換圖是一張有限個(gè)結(jié)點(diǎn)的有向圖，結(jié)點(diǎn)代表狀

態(tài)，用圓圈表示，狀態(tài)之間用帶標(biāo)識(shí)的箭弧連結(jié)，箭

弧上的標(biāo)識(shí)代表在射出結(jié)點(diǎn)（即箭弧始結(jié)點(diǎn)）狀態(tài)下

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

Compilerprinciples18

如右圖所示：

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

符為a,則讀進(jìn)a,并轉(zhuǎn)

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

符為b,則讀進(jìn)b,并轉(zhuǎn)

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

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

（即有限個(gè)結(jié)點(diǎn)），其

中有一個(gè)被認(rèn)為是初態(tài),狀態(tài)轉(zhuǎn)換圖

而且實(shí)際上至少要有一

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

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

Compilerprinciples19

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

r例如：

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

字母或數(shù)字

字母

——<1數(shù)字

數(shù)字D其他*

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

終態(tài)上打個(gè)*號(hào)，表示多讀進(jìn)了一個(gè)不屬于該標(biāo)識(shí)符或數(shù)

字部分的字符，應(yīng)把它退還給輸入串。

或D

數(shù)字?jǐn)?shù)字?jǐn)?shù)字

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

0十1

數(shù)字

其它

6

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

工蟒轉(zhuǎn)醺思以用來識(shí)別程序語言的單詞符號(hào)

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

)述的五類單詞符號(hào)，運(yùn)算符

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

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

態(tài)轉(zhuǎn)換圖來識(shí)別其所有單詞

0—1-2識(shí)別的串是基本

k--@

字還是標(biāo)識(shí)符，要查保留字

表區(qū)分。

這兒還要加上兩個(gè)限制：

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

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

0)則用一分開；

〔其它.嘉

Compilerprinciples\C1_1))

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

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

因?yàn)樵诔绦蛘Z言中對(duì)單詞符號(hào)的識(shí)別不唯

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

DO99U1.10一樣，要真正識(shí)別一個(gè)單詞，必

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

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

到——對(duì)應(yīng)，如'1331'—'學(xué)'、'5045’一

'習(xí)’在什么地方都一樣，則可很容易通過一個(gè)

對(duì)應(yīng)表來實(shí)現(xiàn)，也就用不著“狀態(tài)轉(zhuǎn)換”了。

Compilerprinciples22

4?狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn)一■每個(gè)狀態(tài)對(duì)應(yīng)一小

干段程序即可

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

本部分：

⑴CHAR：字符變量，存放最新讀進(jìn)的源程序字符；

⑵Token：字符數(shù)組，存放構(gòu)成單詞符號(hào)的符號(hào)串；

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

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

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

GetChar直至CHAR中進(jìn)入一個(gè)非空白字符；

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

到Token之后;

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

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

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

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

.

Compilerprinciples23

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

回調(diào)一個(gè)字符位置，并置CHAR為空；

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

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

換為二進(jìn)制數(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ī)表達(dá)式與有窮自動(dòng)機(jī)

RegularExpressionandFiniteAutomaton

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

Scanner的主要工作--拼單詞符號(hào)并進(jìn)行相應(yīng)的詞法

檢查-一的基礎(chǔ)上，通過狀態(tài)轉(zhuǎn)換圖來構(gòu)造的。本節(jié)要

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

程序的自動(dòng)生成問題。

由于我們集中注意力于掃描器的自動(dòng)生成，故對(duì)

有關(guān)結(jié)論一般不加形式證明，大家若對(duì)這方面感興趣,

可以查閱相關(guān)書籍，如《形式語言與自動(dòng)機(jī)的關(guān)系》

-^書(FormalLanguageAndTheirRelationTo

Automaton)。

Compilerprinciples26

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

廠贏I知道，任何高級(jí)程序設(shè)計(jì)語言都有自己的字

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

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

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

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

具，可用以描述單詞符號(hào)。這同樣是一個(gè)無窮語言的

有窮描述的問題。

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

這是一種與我們以前常見的算術(shù)、邏輯等表達(dá)式

不同的表達(dá)式。設(shè)Z為字母表，

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

為任｝和0；

⑵對(duì)于任何a都是Z上的一個(gè)正規(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))*(閉包)。

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

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

上的正規(guī)集。

*這個(gè)定義本身是構(gòu)造型的，今后我們應(yīng)該習(xí)慣這種

構(gòu)造型定義及證明方式。

Compilerprinciples28

2,正規(guī)表達(dá)式的運(yùn)算順序：

括號(hào)一*（閉包）f?（連接）fI（或）

例1：Z={a，b}o

都是正規(guī)式

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

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

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

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

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

對(duì)應(yīng)的正規(guī)集是所有含有兩個(gè)相繼的a或相繼的b的

Compilerprinciples29

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

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

——Z上的“標(biāo)識(shí)符”的全體

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

“數(shù)”的全體

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

Compilerprinciples30

3.正規(guī)表達(dá)式的等價(jià)：

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

為二者等價(jià)，記為'二’。

例：Z={a,b}

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

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

b(ab)*=(ba)*b

Compilerprinciples31

4,正規(guī)表達(dá)式的運(yùn)算律:

UIV=VIU（交換律）

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

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

U(VIW)=UVIuw（分配律）

(UIV)W=UWIVW（分配律）

￡U=U￡=U（幺元）

3主意，這里的每條運(yùn)算律都需要證明。

Compilerprinciples32

二、確定的有窮自動(dòng)機(jī)(DFA)

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

......，⑤

我們也可以寫：

Sg^aSpS(So,a)=SX

Si-bS/b(Sb)=S

乙_nL乙2

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

的標(biāo)識(shí)構(gòu)成一個(gè)集合Z，函數(shù)6,起始狀態(tài)S。和所

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

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

Compilerprinciples33

2.形式定義：

I確定有限自動(dòng)機(jī)(DFA)是一個(gè)五元式系統(tǒng)：

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

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

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

入字符。

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

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

時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)s)我們稱S為s的后繼狀

o

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

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

CompilerPrinciples34

3.DFA的表示形式：

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

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

的）狀態(tài)轉(zhuǎn)換圖，它們是一一對(duì)應(yīng)的。

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

符，那末，這張圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每

個(gè)結(jié)點(diǎn)頂多有n條箭弧射出和別的結(jié)點(diǎn)相連

接，每條箭弧用，上的一個(gè)字符作標(biāo)記，整

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

終態(tài)結(jié)點(diǎn)。

Compilerprinciples35

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

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

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

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

Compilerprinciples36

對(duì)于E*中的任何一個(gè)字符串a(chǎn),若存在一條

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

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

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

若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字？

可以為M所識(shí)別。DFAM所能識(shí)別的字的全體記

為L(M).

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

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

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

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

有不同的標(biāo)識(shí)。

Compilerprinciples37

例:

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

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

換圖如若

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

而個(gè)b的字的集合。

Compilerprinciples38

三、不確定的有窮自動(dòng)機(jī)(NFA)

1.形式定義

一個(gè)不確定有限自動(dòng)機(jī)(NFA)是一個(gè)五元式系統(tǒng)

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

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

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

入字符。

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

6：SxZ*一2s

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

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

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

證明中很有用。

Compilerprinciples39

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

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

結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以射出若干條箭弧和別的結(jié)點(diǎn)相連接，每

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

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

干個(gè)（可以是。個(gè)）終態(tài)結(jié)點(diǎn)。某些結(jié)點(diǎn)既可以是初態(tài)也可

以是終態(tài)結(jié)點(diǎn)。

對(duì)于中中的任何一個(gè)字符a,若存在一條從初態(tài)結(jié)點(diǎn)到

某一終態(tài)結(jié)點(diǎn)的通路，旦這條通路上所有箭弧的標(biāo)記符連接

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

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

若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，或者存在一條某初

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

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.有窮自動(dòng)機(jī)的等價(jià):

對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M',如

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

此我們有一個(gè)重要結(jié)論：判定任何兩個(gè)有

窮自動(dòng)機(jī)等價(jià)的算法是存在的。

Compilerprinciples42

四、正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性：

｛我們先來證明兩個(gè)重要的事實(shí)：

1,定理1：Z上的有窮自動(dòng)機(jī)所接受的字的全體

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

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

易想到正規(guī)式。因?yàn)檎?guī)集是正規(guī)式的值。同時(shí)我

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

換圖，而該圖中從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的

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

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

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

如果能構(gòu)造出這樣的一個(gè)V,問題也就解決了。為此,

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

個(gè)正期疝耒標(biāo)記，如fo)alb

這樣我們就可以借助M來構(gòu)造Vf

Compilerprinciples43

(2)證明(簡略)：

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

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

標(biāo)有￡的弧與丫相連接。顯然這樣的NFAM與NFAM'是等

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

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

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

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

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

例:a,b

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

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

Compilerprinciples45

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

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

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

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

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

分裂并加入新結(jié)點(diǎn)和弧，直到每條弧的標(biāo)記或者為

Z中的一個(gè)符號(hào)，或者為￡,這樣就構(gòu)造了一個(gè)轉(zhuǎn)

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

就可以了。

Compilerprinciples46

(2)證明:

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

b.根據(jù)以下規(guī)則分裂V并加入新狀態(tài)結(jié)點(diǎn)和標(biāo)識(shí)弧

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

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

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

Compilerprinciples47

c.對(duì)NFAM'確定化一構(gòu)造一個(gè)DFAM使得L(M)=L(M‘)

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

不確定的原因主要在于含有￡弧和從某結(jié)點(diǎn)經(jīng)由相同標(biāo)識(shí)的

弧而到達(dá)不同的結(jié)點(diǎn)——結(jié)點(diǎn)集。這兩個(gè)問題解決了，NFA

也就確定了。

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

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

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

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

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

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

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

過一條a弧(跳過a前的任意條￡弧)而到達(dá)的狀態(tài)結(jié)點(diǎn)的全

體。

Compilerprinciples48

。設(shè)I={1},則由I經(jīng)一條a弧而到達(dá)的狀態(tài)結(jié)點(diǎn)

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

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

C-X

Compilerprinciples49

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

與符號(hào)個(gè)數(shù)密切相關(guān)，為此我們?cè)O(shè)Z二{a,b},并依如下過程

構(gòu)造一個(gè)轉(zhuǎn)換矩陣。

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

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

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

已構(gòu)造出的I的，若有則將其作為新的I，又可以構(gòu)造新的M

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

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

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

矩陣，該矩陣唯一地畫出了一個(gè)確定的有窮自動(dòng)機(jī)M,其唯

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

子集。

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

定化的目的。

Compilerprinciples50

?例:設(shè)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)重新編號(hào)的狀態(tài)矩陣：(4)DFAM的狀態(tài)轉(zhuǎn)換圖為:

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：一個(gè)字集V是正規(guī)的仁會(huì)有二自動(dòng)機(jī)M工使得

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

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

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

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

NFA與DFA接收相同的集合。

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

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

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

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

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

S°二｛S。｝.

Compilerprinciples53

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

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

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

一個(gè)元素Q的結(jié)果。通過把5應(yīng)用到Sp52,…Sj的每一個(gè)元素上

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

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

Z

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

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

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

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

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

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

由定義：&(產(chǎn)1,…Pj],a尸/怔2,…當(dāng)且僅當(dāng)“伊1,…即間=

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

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

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

Compilerprinciples54

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

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

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

這個(gè)證明過程一般不預(yù)介紹。

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

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

V,而對(duì)任何一個(gè)NFAM我們又都能構(gòu)造一

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

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

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

下面我們就來討論這個(gè)問題。

Compilerprinciples55

四、DFA的化簡

?:?所謂對(duì)一個(gè)DFAM的化簡，就是找一個(gè)DFA

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

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

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

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

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

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

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

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

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

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

都是等價(jià)的，最后讓每個(gè)子集選出一個(gè)代表,

把所有與該子集相關(guān)的弧都與該代表相連接,

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

DFAM\——子集法

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

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—分成兩個(gè)子

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

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

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

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

Compilerprinciples58

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

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

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

(1)

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

集中，故應(yīng)分割。又因{0,2}『{1},故分成{0,2}和

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

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

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

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

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

={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)選等價(jià)狀態(tài)子集的代表，并重構(gòu)狀態(tài)圖。

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

(5)最后可得最少狀態(tài)自動(dòng)機(jī)為：

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.詞法分析器的自動(dòng)產(chǎn)生

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

來識(shí)別單詞符號(hào)，DFA可以用一張確定的

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

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

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

規(guī)式產(chǎn)生掃描器。首先介紹一個(gè)描述掃

描器的語言一LEX(LexicalAnalyser),

討論其實(shí)現(xiàn)(即研究它的編譯器的構(gòu)

造)，進(jìn)而用它來描述并自動(dòng)生成各種

掃描器。

Compilerprinciples61

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

與每個(gè)正規(guī)式相對(duì)應(yīng)的一個(gè)“動(dòng)作"（Action）組成。

“動(dòng)作”本身是一小段程序代碼，它指出了當(dāng)按正

規(guī)式識(shí)別出一個(gè)單詞符號(hào)時(shí)應(yīng)采取的行動(dòng)。將LEX

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

一個(gè)有限自動(dòng)機(jī)一樣，可用來識(shí)別和產(chǎn)生單詞符號(hào)。

該結(jié)果程序由一張狀態(tài)轉(zhuǎn)換表和一個(gè)控制程序組成。

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

輸入串

_____SZ

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

單詞符號(hào)串。

Compilerprinciples62

一、LEX語言簡介

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

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

LEX語言程序的首部。

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

5稱為n的簡名。

Compilerprinciples63

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

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

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

例如C語言的標(biāo)識(shí)符可如下定義：

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

digit-0|1|...|9

id-letter(letterIdigit)*

2.(單詞符號(hào))識(shí)別規(guī)則：——相當(dāng)于執(zhí)行語句。

(1)作用：用來識(shí)別單詞符號(hào)；

(2)語句形式：

Pi{AJ

P2{A2}

Pn6}

Compilerprinciples64

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

小段程序代碼指出當(dāng)識(shí)別出詞形Pj這種單詞后，掃

描器要采取的動(dòng)作。當(dāng)然這兒Pj必須是定義在

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

器L只能識(shí)別具有詞形為Pl,P2,…Pn的單詞符號(hào)。

每個(gè)詞形Pj所對(duì)應(yīng)的動(dòng)作Aj的基本組成成分是

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

Value)o如Pj是“標(biāo)識(shí)符”，則Value為符號(hào)表入口

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

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

無定義。

Compilerprinciples65

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

個(gè)最長子串與Pj進(jìn)行匹配，一旦匹配成功,

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

行輸入串相匹配，貝扎應(yīng)報(bào)告輸入串含有

錯(cuò)誤（如非法字符），并進(jìn)行善后處理；

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

干個(gè)不同的Pj,此時(shí)就先匹配LEX程序中

出現(xiàn)在最前面的那個(gè)Pj。其他細(xì)節(jié)請(qǐng)見教

材P59?60。

Compilerprinciples66

二、LEX的實(shí)現(xiàn)

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

對(duì)每條識(shí)別規(guī)則Pj構(gòu)造一個(gè)相應(yīng)的NFAMj,

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

接成一個(gè)新的NFA（圖示如下）；

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

時(shí)還可化簡。其他有關(guān)細(xì)節(jié)我們就不談了，

望大家下去自己看書。

Compilerprinciples67

小結(jié)

本講內(nèi)容：

★詞法分析器的構(gòu)造

★狀態(tài)轉(zhuǎn)換圖

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

★DFA與NFA

★RE,RG,DFA,NFA的等價(jià)關(guān)系

★DFA的最小化

Compilerprinciples68

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

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

詞

輸出：單詞符號(hào)串（二元式）

法--

分析技術(shù)f超前搜索

分<1對(duì)半互補(bǔ)緩沖區(qū)

析預(yù)處理子程序

設(shè)計(jì),獨(dú)立子程序

器

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

實(shí)現(xiàn)：最小化的DFA的每個(gè)狀態(tài)對(duì)應(yīng)一小段程序

DFA化簡：

轉(zhuǎn)換規(guī)則

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

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

rAfBaa----------->NFA---------"DFA價(jià)類'DFA

RGJ增加終止?fàn)钆c/

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

Compilerprinciples69

例題與習(xí)題解答

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

達(dá)式。

解：能被5整除的文法：

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

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

正則表達(dá)式:(+|-)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]

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

奇數(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整除十進(jìn)制整數(shù)的文法和正則表達(dá)式:

解：能被3整除的文法：

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

S