編譯程序構(gòu)造與實(shí)踐教程第三章

第三章詞法分析3.1概況1.詞法分析與詞法分析程序

編譯程序的功能是把高級(jí)程序設(shè)計(jì)語言源程序翻譯成等價(jià)的低級(jí)語言目標(biāo)程序，而源程序本身是一個(gè)基本符號(hào)序列或字符序列。為此，首先必須進(jìn)行詞法分析，編譯程序中完成詞法分析工作的部分稱為詞法分析程序，或稱掃描程序。

其功能有三：

?掃描(讀入)源程序字符序列，

?識(shí)別開符號(hào)(單詞)并轉(zhuǎn)換為等價(jià)的內(nèi)部中間表示(屬性字)，

?進(jìn)行一些簡(jiǎn)單而有利于下一階段之處理的工作(刪除注解與空格等無效字符、某些預(yù)處理)。輸入：源程序字符序列輸出：屬性字序列基礎(chǔ)文法：正則文法2.符號(hào)的識(shí)別與重寫規(guī)則的關(guān)系

C語言符號(hào)：標(biāo)識(shí)符、常量、字符串、標(biāo)號(hào)、界限符（關(guān)鍵字，專用符號(hào)）符號(hào)都可用正則文法規(guī)則來定義：

U::=VTU::=T（U、VVN，TVT）<標(biāo)識(shí)符>::=<標(biāo)識(shí)符>字母|<標(biāo)識(shí)符>數(shù)字|字母

<整數(shù)>::=<整數(shù)>數(shù)字|數(shù)字

<邏輯與>::=<&符號(hào)>&<&符號(hào)>::=&其中字母是具體的英文字母，數(shù)字是具體的數(shù)字。即使關(guān)鍵字，如int等也可以用正則文法規(guī)則來定義：<int符號(hào)>::=<int-2>t<int-2>::=<int-1>n<int-1>::=i因此，關(guān)鍵字的定義都可采用正則文法規(guī)則形式。詞法分析程序可以手工實(shí)現(xiàn)，也可自動(dòng)生成。3.2詞法分析程序的手工實(shí)現(xiàn)3.2.1實(shí)現(xiàn)要點(diǎn)

實(shí)現(xiàn)詞法分析程序的大致步驟如下：

確定程序設(shè)計(jì)語言(或其子集)，明確相應(yīng)的字符集、符號(hào)及其構(gòu)造

總體設(shè)計(jì)

?設(shè)計(jì)各類數(shù)據(jù)結(jié)構(gòu)，包括輸入(源程序字符序列)與輸出(屬性字序列)，以及各類表格的數(shù)據(jù)結(jié)構(gòu)

?

功能模塊分解，明確各個(gè)模塊(子程序)的功能與相互接口,畫出總控流程圖及各個(gè)子程序的控制流程圖

編程，并設(shè)計(jì)調(diào)試實(shí)例，進(jìn)行調(diào)試，完成研制。實(shí)現(xiàn)的要點(diǎn)是如下兩方面，即，屬性字的設(shè)計(jì)與標(biāo)識(shí)符的處理。3.2.2屬性字的設(shè)計(jì)屬性字是符號(hào)的內(nèi)部中間表示,對(duì)其設(shè)計(jì)要求，一是不同的符號(hào)都有唯一的表示，能彼此區(qū)分開，二是便于后繼編譯階段的處理。

為此，所有屬性字是等長(zhǎng)、定長(zhǎng)的。屬性字指明是什么符號(hào)，且刻劃了符號(hào)的屬性。

1.屬性字的一般結(jié)構(gòu)

符號(hào)類識(shí)別開不同類的符號(hào)，符號(hào)值識(shí)別開同一類中不同的符號(hào)。例如標(biāo)識(shí)符類。

當(dāng)詞法分析程序掃描到一個(gè)標(biāo)識(shí)符時(shí)，把它的相關(guān)條目登錄在標(biāo)識(shí)符表中，以所登錄的條目的序號(hào)或指針作為相應(yīng)屬性字的符號(hào)值，通過此序號(hào)或指針可以很方便地存取該標(biāo)識(shí)符。關(guān)于無正負(fù)號(hào)整數(shù)，情況類似。

符號(hào)類符號(hào)值2.屬性字的設(shè)計(jì)屬性字的設(shè)計(jì)是詞法分析程序之實(shí)現(xiàn)的重要方面。它的設(shè)計(jì)要有利于語法分析階段的處理。

符號(hào)編碼表如下。

符號(hào)類編碼助記憶名符號(hào)類編碼

助記憶名

無定義

標(biāo)識(shí)符

整數(shù)

+

-

*/%<<=>>===!=&&&||!=0123456789101112131415161718$UND$ID$NUM$PLUS$MINUS$STAR$SLASH$MOD$LT$LE$GT$GE$EQ$NEQ&ADDR$AND$OR$NOT$ASSIGN()[]{},;void

intfloatchar

structifelsewhiledoforreturn19202122232425262728293031323334353637$LPAR$RPAR$LS$RS$LB$RB$COMMA$SEMICOLON$VOID$INT$FLOAT$CHAR$STRUCT$IF$ELSE$WHILE$DO$FOR$RETURN例屬性字序列之例

voidmain(){inti,j,d;if(i>j)d=i-j;elsed=j-i;d=d/4;}

輸入符號(hào)屬性字序列

輸入符號(hào)屬性字序列voidmain(){inti,j,d;if(i>j)d27,"void"1,"main"19,"("20,")"23,"{"28,"int"1,"i"25,","1,"j"25,","1,"d"26,";"32,"if"19,"("1,"i"10,">"j,"j"20,")"1,"d"=i-j;elsed=j-i;d=d/4;}18,"="1,"i"4,"-"1,"j"26,";"33,"else"1,"d"18,"="1,"j"4,"-"1,"i"26,";"1,"d"18,"="1,"d"6,"/"2,"4"26,";“24,"}"相應(yīng)的屬性序列:屬性字結(jié)構(gòu)的改進(jìn)·

分成兩大類：特定符號(hào)、非特定符號(hào)·

指明說明符還是運(yùn)算符·

運(yùn)算符時(shí)給出優(yōu)先級(jí)特定符號(hào)類符號(hào)的屬性字可有如下的構(gòu)造。

01234567…1516…31特定符號(hào)說明符運(yùn)算符運(yùn)算符優(yōu)先級(jí)

符號(hào)類編碼符號(hào)值

運(yùn)算符優(yōu)先級(jí)定義如下：8：&!+-

（單目）7：*

/%6：+

-

（雙目）5：<<=>>=4:==!=3:&&2:||1:=

符號(hào)類符號(hào)值

符號(hào)類符號(hào)值100027"void"101118"="00001"main"00001"i"100019"("10164"-"100020")"00001"j"100023"{"100026";"110028"int"100033"else"00001"i"00001"d"100025","101118"="00001"j"00001"j"100025","10164"-"00001"d"00001"i"100026";"100026";"100032"if"00001"d"100019"("101118"="00001"i"00001"d"101510">"10176"/"00001"j"00002"4"100020"("100026";"00001"d"100024"}"例改進(jìn)的屬性字序列3.2.3標(biāo)識(shí)符的處理標(biāo)識(shí)符是源程序中出現(xiàn)最頻繁的符號(hào)，編譯程序處理的重點(diǎn)是標(biāo)識(shí)符。對(duì)標(biāo)識(shí)符的處理涉及下列三方面：1.區(qū)分標(biāo)識(shí)符的定義性出現(xiàn)與使用性出現(xiàn)2.確定標(biāo)識(shí)符的作用域3.確定標(biāo)識(shí)符屬性字的符號(hào)值1.區(qū)分標(biāo)識(shí)符的定義性出現(xiàn)與使用性出現(xiàn)1）定義性出現(xiàn)時(shí)填標(biāo)識(shí)符表（符號(hào)表）應(yīng)用性出現(xiàn)時(shí)查標(biāo)識(shí)符表（符號(hào)表）2）定義性出現(xiàn)一般在程序的說明部分應(yīng)用性出現(xiàn)一般在程序的控制部分例見下頁(yè)。例設(shè)有C程序如下：intmax3(inta,intb,intc){intmax;

if(a>b)max=a;elsemax=b;

if(c>max)max=c;returnmax;}main(){int

x,y,z,max;

printf(″Inputvaluesofx,y,andz:″);

scanf(″%d%d%d″,&x,&y,&z);max=max3(x,y,z);

printf(″max(%d,%d,%d)=%d\n″,x,y,z,max);}定義性出現(xiàn)？使用性出現(xiàn)？符號(hào)類符號(hào)值符號(hào)類符號(hào)值110028″int″101118″=″00001″max3″00001″a″100019″(″100026″;″110028″int″100033″e(cuò)lse″00001″a″00001″max″100025″,″101118″=″110028″int″00001″b″00001″b″100026″;″100025″,″100032″if″110028″int″100019″(″00001″c″00001″c″100020″)″101510″>″100023″{″00001″max″110028″int″100020″)″00001″max″00001″max″100026″;″101118″=″100032″if″00001″c″100019″(″100026″;″00001″a″100037″return″101510″>″00001″max″00001″b″100026″;″100020″)″100024″}″00001″max″max3之函數(shù)定義的屬性字序列

標(biāo)識(shí)符表

max300001max3a00001ab00001bc00001cmax00001maxx00001xy00001yz

00001z問題是：在函數(shù)max3與main函數(shù)中都有標(biāo)識(shí)符max，它們?cè)诳刂撇糠种谐霈F(xiàn)時(shí)代表不同的數(shù)據(jù)對(duì)象，如何區(qū)分?2.確定標(biāo)識(shí)符的作用域作用域：標(biāo)識(shí)符與某類型屬性相關(guān)聯(lián)的有效范圍。同一個(gè)標(biāo)識(shí)符出現(xiàn)在不同的作用域中將代表不同的數(shù)據(jù)對(duì)象。

/*Scopeforidentifier*/intm=3;int

fun(inta,intb){intm=4,x=5;return(a+m)*(x-b)-m;}main(){intx=1,y=1;

printf(″fun(%d,%d)/%d=%d\n″,x,y,m,fun(x,y)/m);}

請(qǐng)指明各個(gè)標(biāo)識(shí)符的作用域，并說明運(yùn)行結(jié)果。確定標(biāo)識(shí)符的作用域，作用在于：當(dāng)詞法分析程序掃描到某個(gè)標(biāo)識(shí)符的使用性出現(xiàn)時(shí)，通過確定其作用域，能確定該標(biāo)識(shí)符所代表的數(shù)據(jù)對(duì)象，從而能確定其具有的類型等屬性。為了確切地確定一個(gè)使用性出現(xiàn)的標(biāo)識(shí)符的作用域，采用靜態(tài)作用域法則，并按“最接近的嵌套”約定來確定作用域。

為了實(shí)現(xiàn)正確地確定標(biāo)識(shí)符的作用域，簡(jiǎn)單而可行的辦法是利用后進(jìn)先出棧。確定標(biāo)識(shí)符屬性字的符號(hào)值

不同的符號(hào)應(yīng)有不同的屬性字。

對(duì)于特定符號(hào)類，一個(gè)符號(hào)類也就是一個(gè)符號(hào)，即，有唯一的屬性字。

對(duì)于非特定符號(hào)類，同一個(gè)符號(hào)類可以有多個(gè)不同的符號(hào)，確切地說，對(duì)于標(biāo)識(shí)符，同為標(biāo)識(shí)符類，卻可以有多個(gè)不同的標(biāo)識(shí)符。常量情況類似。

符號(hào)值區(qū)分同一類中不同的符號(hào)。

可如下地處理。

?簡(jiǎn)單變量為標(biāo)識(shí)符表序號(hào)；

?常量為常量表序號(hào)；

?其它各類標(biāo)識(shí)符為相應(yīng)信息表之序號(hào)。

3.2.4詞法分析程序的設(shè)計(jì)和編寫

1.總控流程圖

總控程序流程示意圖入口置初值

源程序結(jié)束是出口

否取符號(hào)，并

生成屬性字

輸出屬性字取符號(hào)置初值返回返回

重查sym=“”

放過空字符生成屬性字生成屬性字

是是

字母是ch拼入sym取字符字母數(shù)字否關(guān)鍵字否查造標(biāo)識(shí)符表

否

數(shù)字是ch拼入sym取字符數(shù)字否查造常量表生成屬性字

否是

S[1]:=ch

返回

取字符

S[2]:=ch

重查

查符號(hào)機(jī)查到否S[2]:=′′查符號(hào)機(jī)查到否出錯(cuò)

內(nèi)表示表是內(nèi)表示表是

取字符生成屬性字返回

取符號(hào)子程序的程序控制流程示意圖詞法分析程序的基本子程序（函數(shù)）取符號(hào)子程序、

取字符子程序、

查造標(biāo)識(shí)符表子程序、查造常量表子程序、

查關(guān)鍵字表子程序、查符號(hào)機(jī)內(nèi)表示表子程序重點(diǎn)：取符號(hào)子程序的編寫。注意：取字符子程序的編寫。

取符號(hào)子程序的約定:

約定1進(jìn)入時(shí)已取到當(dāng)前符號(hào)的第一個(gè)字符；約定2在離開時(shí)已取到當(dāng)前符號(hào)的后繼字符。2.數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)手工實(shí)現(xiàn)詞法分析程序的基本思路

·確定所要實(shí)現(xiàn)的語言（或其子集）

·設(shè)計(jì)屬性字，并設(shè)計(jì)各類表格標(biāo)識(shí)符表、常量表、關(guān)鍵字表、符號(hào)機(jī)內(nèi)表示表等

·畫出總控流程圖及各子程序的流程圖

·最終完成詞法分析程序的編程及其調(diào)試要點(diǎn)是數(shù)據(jù)結(jié)構(gòu)（包括表格）的設(shè)計(jì)。

詞法分析時(shí)使用的數(shù)據(jù)結(jié)構(gòu)（表）：屬性字序列

字符表符號(hào)機(jī)內(nèi)表示表關(guān)鍵字表標(biāo)識(shí)符表（符號(hào)表）無正負(fù)號(hào)整數(shù)表（常量表）重點(diǎn)是屬性字的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。屬性字的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：

typedef

struct

屬性字{符號(hào)類類型

屬性字符號(hào)類；符號(hào)值類型符號(hào)值；/*可以是字符數(shù)組類型*/}屬性字類型；其中符號(hào)類類型可定義如下：

typedef

struct

{int

符號(hào)大類；/*1：特定符號(hào)類0：非特定符號(hào)類*/

int

說明符標(biāo)志；

/*1：說明符，

0：非說明符*/

int

運(yùn)算符標(biāo)志；

/*1：運(yùn)算符，

0：非運(yùn)算符*/

int

運(yùn)算符優(yōu)先級(jí)；

int

符號(hào)類編碼；

}符號(hào)類類型；

屬性字序列可以用數(shù)組類型定義如下：

屬性字類型屬性字序列[MaxAttriWordLength];

其中,MaxAttriWordLength是可允許的屬性字序列最大長(zhǎng)度。

標(biāo)識(shí)符表?xiàng)l目的數(shù)據(jù)結(jié)構(gòu)可設(shè)計(jì)如下。

typedef

struct

{char標(biāo)識(shí)符[MaxIdLength];

/*當(dāng)符號(hào)值為符號(hào)本身時(shí)此成員變量可刪*/

屬性字類型標(biāo)識(shí)符屬性字；

int

條目序號(hào)；/*當(dāng)符號(hào)值為序號(hào)時(shí)此成員變量可刪*/

}標(biāo)識(shí)符表?xiàng)l目類型；

標(biāo)識(shí)符表的數(shù)據(jù)結(jié)構(gòu)可設(shè)計(jì)如下：

標(biāo)識(shí)符表?xiàng)l目類型標(biāo)識(shí)符表[MaxIDTLength];

表格的輸入，可以以賦初值方式給出。屬性字類型符號(hào)機(jī)內(nèi)表示表[22]={{{1,0,1,6,3},"+"},{{1,0,1,6,4},"-"},{{1,0,1,7,5},"*"},{{1,0,1,7,6},"/"},{{1,0,1,7,7},"%"},{{1,0,1,5,8},"<"},{{1,0,1,5,9},"<="},{{1,0,1,5,10},">"},{{1,0,1,5,11},">="},{{1,0,1,4,12},"=="},{{1,0,1,4,13},"!="},{{1,0,1,3,14},"&"},

{{1,0,1,4,15},"&&"},{{1,0,1,3,16},"||"},{{1,0,1,2,17},"!"},{{1,0,1,1,18},"="},{{1,0,0,0,19},"("},{{1,0,0,0,20},")"},{{1,0,0,0,21},"["},{{1,0,0,0,22},"]"},{{1,0,0,0,23},"{"},{{1,0,0,0,24},"}

"},{{1,0,0,0,25},","},{{1,0,0,0,26},";"}};屬性字類型關(guān)鍵字表[10]={{0},{{1,0,0,0,27},"void"},{{1,1,0,0,28},"int"},{{1,1,0,0,29},"float"},{{1,1,0,0,29},"char"},

{{1,1,0,0,31},"struct"},{{1,0,0,0,32},"if"},{{1,0,0,0,33},"else"},{{1,0,0,0,34},"while"},{{1,0,0,0,35},"do"},{{1,0,0,0,36},"for"}，{{1,0,0,0,37},"return"}};3.各子程序的實(shí)現(xiàn)

子程序包括：

取符號(hào)子程序、

取字符子程序、

查造常量表子程序、

查造標(biāo)識(shí)符表子程序、

查符號(hào)機(jī)內(nèi)表示表子程序

這些子程序的實(shí)現(xiàn)都是容易的，只是指出：

?取字符子程序，當(dāng)取到標(biāo)志輸入結(jié)束的字符時(shí)，需給出相應(yīng)信息。

?查符號(hào)機(jī)內(nèi)表示表分成2個(gè)子程序，分別查關(guān)鍵字表與查單雙字符表。

?查造標(biāo)識(shí)符表，查是使用性出現(xiàn)時(shí)進(jìn)行，而造是定義性出現(xiàn)時(shí)進(jìn)行。一般要涉及標(biāo)識(shí)符的作用域問題。

?宜加入出錯(cuò)處理功能。3.3詞法分析程序的自動(dòng)生成

3.3.1詞法分析程序自動(dòng)生成的基本思想

?引進(jìn)通用掃描算法，進(jìn)行詞法分析

基于與程序設(shè)計(jì)語言相關(guān)的一些表

不同的語言有不同的表

?引進(jìn)構(gòu)造程序，生成表

根據(jù)語言的特定符號(hào)說明書

其中指明符號(hào)的組成與機(jī)內(nèi)表示等詞法分析程序自動(dòng)生成的構(gòu)造程序與通用掃描算法及程序設(shè)計(jì)語言的符號(hào)說明書之間的聯(lián)系如下所示。

關(guān)于某程序設(shè)計(jì)語言的符號(hào)說明書

構(gòu)造程序

通用掃描算法

各類表掃描程序語言符號(hào)說明書描述的內(nèi)容：

1.語言中允許哪些字符？

2.有哪幾類符號(hào)，各類符號(hào)如何組成？

3.各類符號(hào)的機(jī)內(nèi)表示是什么？

符號(hào)的結(jié)構(gòu)與字符類1)標(biāo)識(shí)符或保留字構(gòu)形:<開始字符>{<其他字符>}2)整數(shù)構(gòu)形:<數(shù)字>{<數(shù)字>}3)單字符界限符構(gòu)形:<字符>4)雙字符界限符構(gòu)形:<字符><字符>5)關(guān)鍵字構(gòu)形:<括號(hào)><開始字符>{<其他字符>}<括號(hào)>五類構(gòu)形：DELIMDELIMDELIMDIGIT｛DIGIT｝IDBEG｛IDCHAR｝DELIMIDBEG｛IDCHAR｝DELIM通用掃描算法功能：處理五類構(gòu)形2.*

掃描程序定義與構(gòu)造程序掃描程序定義〈掃描程序〉∷=BEGIN<標(biāo)識(shí)符1>[<標(biāo)識(shí)符2>]{<類定義>}{<符號(hào)定義>}END〈類定義〉∷=〈類名字〉〈字符表〉〈類名字〉∷=IDBEG｜IDCHAR｜DIGIT｜IGNORE

｜INVISICHAR｜DELIM〈字符表〉∷=［ALLBUT］〈字符〉｛〈字符〉｝〈符號(hào)定義〉∷=RES〈整數(shù)〉〈符號(hào)〉｛〈符號(hào)〉｝〈符號(hào)〉∷=〈字符〉｛“｜”〈字符〉｝｜“不包含空白字符的EBCDIC字符序列”〈字符〉∷=“除空白字符外的EBCDIC字符”｜〈十六進(jìn)制數(shù)字〉〈十六進(jìn)制數(shù)字〉〈十六進(jìn)制數(shù)字〉∷=0｜1｜2｜3｜4｜5｜6｜7｜8｜9

｜A｜B｜C｜D｜E｜F說明：標(biāo)識(shí)符1是掃描程序的名稱，標(biāo)識(shí)符2是詞法分析時(shí)查看源程序的程序名。某程序設(shè)計(jì)語言的符號(hào)說明書之例。

BEGINSCANNER

DIGIT0123

IDBEGABCDEFG

IDCHARabcdefg0123456789

INVISICHARX20

DELIM+-*/%<<=>>===!=&&&||!=

DELIM()[]{},;

RES3+-*/%

RES8<<=>>===!=

RES14&&&||!=

RES19()[]{},;

KEY27voidintfloatcharstruct

KEY32ifelsewhiledoforreturn

END

為了描述更一般的符號(hào)，

?引進(jìn)正則表達(dá)式描述符號(hào)的表示法。

例如，L{L|D}D{D}

構(gòu)造程序構(gòu)造程序的功能：讀入掃描程序定義，并由此建立通用掃描算法所用的內(nèi)部表。輸入：掃描程序定義輸出：通用掃描算法所使用的內(nèi)部表構(gòu)造程序的功能決定于所處理的正則表達(dá)式，上述掃描程序定義描述的是5類正則表達(dá)式：

IDBEG{IDCHAR}DIGIT{DIGIT}DELIMDELIMDELIMDELIMIDBEG{IDCHAR}DELIM

只要構(gòu)造程序能處理某正則表達(dá)式，就能處理相應(yīng)的一類符號(hào)。為了實(shí)現(xiàn)詞法分析，

?引進(jìn)狀態(tài)轉(zhuǎn)換圖

與有窮狀態(tài)自動(dòng)機(jī)

3.*

自動(dòng)生成系統(tǒng)LEX簡(jiǎn)介

LEX是當(dāng)前廣泛應(yīng)用的詞法分析程序自動(dòng)生成系統(tǒng)，本質(zhì)是從正則表達(dá)式來生成等價(jià)的確定有窮狀態(tài)自動(dòng)機(jī)。特點(diǎn)是能靈活地和足夠強(qiáng)有力地表達(dá)各種正則表達(dá)式，因此能適應(yīng)各種程序設(shè)計(jì)語言。

LEX系統(tǒng)由三部分組成：?

說明部分：

letter[A-Z,a-z]digit[0-9]idletter{letter|digit}integerdigit{digit}*?

翻譯部分：

while{return($WHILE);}if{return($IF);}id{csidt();return($ID,sym);}?

輔助過程部分：

csidt(){查造標(biāo)識(shí)符表函數(shù)實(shí)現(xiàn)細(xì)節(jié)}3.3.2正則表達(dá)式

1.正則表達(dá)式的概念

這是一種適合于描述符號(hào)的表示法：

?易理解正被定義的是什么符號(hào)集合；

?更容易構(gòu)造高效識(shí)別程序；

?有利于自動(dòng)地構(gòu)造識(shí)別程序；

?可用于其他各種信息流的處理。

例如，L{L|D}表示標(biāo)識(shí)符的組成，D{D}表示整數(shù)的組成。而可以用

D{D}.D{D}[E[+|-]D{D}]|D{D}E[+|-]D{D}

表示實(shí)數(shù)的組成。

正則表達(dá)式是描述程序設(shè)計(jì)語言符號(hào)之組成的好工具。

1.正則表達(dá)式的概念及其性質(zhì)(1)概念設(shè)有字母表Σa.a∈Σ，則a是字母表Σ上的正則表達(dá)式；(原子正則表達(dá)式)

b.若e、e1與e2都是字母表Σ上的正則表達(dá)式，則(e)、e1e2、e1｜e2

與｛e｝都是字母表Σ上的正則表達(dá)式；

按照嚴(yán)格的定義，空串ε與空集?也是字母表Σ上的正則表達(dá)式；上述概念表明：一般的正則表達(dá)式可以從原子正則表達(dá)式或較小的正則表達(dá)式通過加括號(hào)或一些運(yùn)算來構(gòu)造。例

設(shè)Σ1={0,1},則(0|1){0|1}是Σ1上的正則表達(dá)式。例

設(shè)Σ2={A,B,0,1}，則(A|B){A|B|0|1}是Σ2上的正則表達(dá)式。

(2)

正則表達(dá)式e的值是字母表上的正則集，記作｜e｜。||=||={}|a|={a}|(e)|=|e||e1e2|=|e1||e2|={xy|x|e1|,且y|e2|}|e1|e2|=|e1||e2|={x|x|e1|或x|e2|}|{e}|=|e|*即，|e|的閉包例如，|a|={a}|D{D}|=|D||{D}|=|D||D|*={D}{D}*={D}+

所以，|D{D}|={x|x是整數(shù)}，（D是數(shù)字）請(qǐng)自行計(jì)算|(0|1){0|1}|與|(A|B){A|B|0|1}|

(3)等價(jià):若|e1|=|e2|,則稱e1與e2是等價(jià)的,記為e1=e2(4)正則表達(dá)式與語法規(guī)則的聯(lián)系重寫規(guī)則（擴(kuò)充表示法）：

〈標(biāo)識(shí)符〉∷=字母｛字母｜數(shù)字｝

〈整數(shù)〉∷=數(shù)字｛數(shù)字｝

正則表達(dá)式：

字母｛字母｜數(shù)字｝數(shù)字｛數(shù)字｝顯然，|字母｛字母｜數(shù)字｝|={x|<標(biāo)識(shí)符>=>*x,x是標(biāo)識(shí)符}|數(shù)字｛數(shù)字｝|={x|<整數(shù)>=>*x,x是整數(shù)}因此正則表達(dá)式與擴(kuò)充表示法的正則文法重寫規(guī)則之右部相當(dāng)。但正則表達(dá)式更明確直觀地描述了一類符號(hào)的結(jié)構(gòu)。

正則表達(dá)式與詞法分析程序的實(shí)現(xiàn)

自動(dòng)構(gòu)造的詞法分析程序應(yīng)能識(shí)別程序設(shè)計(jì)語言中的任何符號(hào)，包括即將可能擴(kuò)充的符號(hào)。這意指，程序設(shè)計(jì)語言的符號(hào)說明書中應(yīng)能描述任何希望包含的符號(hào)。正則表達(dá)式是描述符號(hào)之結(jié)構(gòu)的好工具，因此，可以把正則表達(dá)式應(yīng)用于程序設(shè)計(jì)語言的符號(hào)說明書。

如何應(yīng)用正則表達(dá)式實(shí)現(xiàn)詞法分析程序的自動(dòng)生成？

應(yīng)用正則表達(dá)式實(shí)現(xiàn)詞法分析程序自動(dòng)生成的思路大致如下。

·讓正則表達(dá)式對(duì)應(yīng)于一個(gè)狀態(tài)轉(zhuǎn)換圖或有窮狀態(tài)自動(dòng)機(jī)

·從狀態(tài)轉(zhuǎn)換圖或有窮狀態(tài)自動(dòng)機(jī)對(duì)應(yīng)到詞法分析程序

從正則表達(dá)式生成狀態(tài)轉(zhuǎn)換圖，思路如下：首先建立一個(gè)有向圖，它只有開始狀態(tài)結(jié)點(diǎn)與終止?fàn)顟B(tài)結(jié)點(diǎn)，兩結(jié)點(diǎn)用一弧相連，弧上標(biāo)記就是所給的正則表達(dá)式。然后應(yīng)用下列三個(gè)轉(zhuǎn)換規(guī)則（見圖3-5）對(duì)所給出的正則表達(dá)式進(jìn)行轉(zhuǎn)換，還可應(yīng)用轉(zhuǎn)換規(guī)則時(shí)，繼續(xù)應(yīng)用轉(zhuǎn)換規(guī)則進(jìn)行轉(zhuǎn)換，直到一切弧上的標(biāo)記都是原子正則表達(dá)式，而不能再應(yīng)用轉(zhuǎn)換規(guī)則時(shí)結(jié)束。

Se2e1e1|e2ZSZ轉(zhuǎn)換為轉(zhuǎn)換為SZe1e2Se2e1Ze1e3SZe2SZe1{e2}e3轉(zhuǎn)換為最終所得的是相應(yīng)的狀態(tài)轉(zhuǎn)換圖。從正則表達(dá)式到狀態(tài)轉(zhuǎn)換圖的例子。L轉(zhuǎn)換為轉(zhuǎn)換為(d)(e)LDDNSDIDLSZLIDDN（a）(b)(c)SZL{L|D}D{D}SZL{L|D}|D{D}轉(zhuǎn)換為轉(zhuǎn)換為L(zhǎng)|DSDLZDNI(e)中為所求的狀態(tài)轉(zhuǎn)換圖。下面討論如何從正則文法出發(fā)生成狀態(tài)轉(zhuǎn)換圖。(1)從正則表達(dá)式到狀態(tài)轉(zhuǎn)換圖a.狀態(tài)轉(zhuǎn)換圖的引進(jìn)

<id>::=L|<id>L|<id>D

Y

Y

Y

入口L取符號(hào)LNDN

出口

N

出口

L,D

抽象成：SLI其他

E稱狀態(tài)轉(zhuǎn)換圖引進(jìn)目的：識(shí)別正則文法的句子。狀態(tài)轉(zhuǎn)換圖：為識(shí)別正則文法的句子而專門設(shè)計(jì)的有向圖。如何理解狀態(tài)轉(zhuǎn)換圖？例正則文法G[Z]：

Z∷=Za｜Ab｜Ba

A∷=Bb｜aB∷=Aa｜b狀態(tài)轉(zhuǎn)換圖：

AabSabZabaB

b.狀態(tài)轉(zhuǎn)換圖的構(gòu)造狀態(tài)轉(zhuǎn)換圖構(gòu)造步驟如下：步驟1以符號(hào)S為開始狀態(tài)作結(jié)點(diǎn)(假定文法的字匯表中不包含符號(hào)S)；步驟2以每一個(gè)非終結(jié)符號(hào)為狀態(tài)作結(jié)點(diǎn)；步驟3對(duì)于形如Q∷=T的每個(gè)規(guī)則，引一條從開始狀態(tài)S到狀態(tài)Q的弧，其標(biāo)記為T；而對(duì)于形如Q∷=RT的規(guī)則引一條從狀態(tài)R到Q的弧，其標(biāo)記為T。其中R為非終結(jié)符號(hào)，T為終結(jié)符號(hào)；步驟4識(shí)別符號(hào)相應(yīng)的狀態(tài)作為終止?fàn)顟B(tài)。c.應(yīng)用狀態(tài)轉(zhuǎn)換圖來識(shí)別句子一般地識(shí)別步驟如下。步驟1從開始狀態(tài)開始，以它作為當(dāng)前狀態(tài)，并從輸入字符串x的最左字符開始，重復(fù)步驟2直到達(dá)到x的右端為止。步驟2掃描x的下一字符(當(dāng)前字符)，在當(dāng)前狀態(tài)射出的各個(gè)弧中找出標(biāo)記有該字符的弧，并沿此弧前進(jìn)，以所達(dá)到的狀態(tài)作為下一當(dāng)前狀態(tài)。假定有輸入字符串a(chǎn)ababb，要識(shí)別它是否是相應(yīng)正則文法的句子。

例正則文法G[Z]：

K∷=If｜SeI::=i

S∷=LsL::=ElE::=e

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

I

if

AELSK

else

當(dāng)識(shí)別一個(gè)字符串x時(shí)，如果能從狀態(tài)轉(zhuǎn)換圖的開始狀態(tài)出發(fā)，行進(jìn)達(dá)到x的右端,x為句子的充分必要條件是最后的當(dāng)前狀態(tài)為終止?fàn)顟B(tài)。輸入字符串x=else,是否是該正則文法的句子？

elseAELSK或?qū)憺椋?/p>

(A)e→(E)l→(L)s→(S)e→(K)K是終止?fàn)顟B(tài)，所以，輸入字符串else是上述正則文法的句子。

為什么可以通過運(yùn)行狀態(tài)轉(zhuǎn)換圖來識(shí)別正則文法的句子？步驟

當(dāng)前狀態(tài)

輸入的其余部分

1AelseK2ElseS3LseL4SeE5Kelse運(yùn)行狀態(tài)轉(zhuǎn)換圖：利用狀態(tài)轉(zhuǎn)換圖識(shí)別正則文法句子的過程。例正則文法G[Z]：

Z∷=Za｜Aa｜BbA∷=Ba｜aB∷=Ab｜b

AaaSbaZabbB

輸入字符串：ababaaa

(2)確定有窮狀態(tài)自動(dòng)機(jī)DFA概念狀態(tài)轉(zhuǎn)換圖是一種有向圖，由5個(gè)要素組成，把它們抽象，便到得有窮狀態(tài)自動(dòng)機(jī)FA。一個(gè)確定的有窮狀態(tài)自動(dòng)機(jī)DFA是五元組

DFAD=(K，Σ，M，S，F(xiàn)),其中,K：狀態(tài)集，Σ：字母表，

M：K×Σ→K映象，

S∈K開始狀態(tài)，F(xiàn)K終止?fàn)顟B(tài)集例DFAD=({A,I,E,L,S,K},{i,f,e,l,s,e},M,A,{K})其中,M：M(A,i)=I

M(I,f)=KM(A,e)=EM(E,l)=LM(L,s)=SM(S,e)=K例

設(shè)有正則文法G[Z]:

Z::=Aa|BbA::=a|BaB::=Ab|b

可為其構(gòu)造狀態(tài)轉(zhuǎn)換圖如圖所示。

相應(yīng)的DFAD=(K,{a,b},M,S,{Z})，

其中，

K={S，A，B，Z}

M：M(S,a)=AM(S,b)=B

M(A,a)=ZM(A,b)=B

M(B,a)=AM(B,b)=ZAZSBabbabab.運(yùn)行DFA擴(kuò)充了的映象M：

M(R,ε)=R，其中R為任意狀態(tài)；

M(R,Tt)=M(M(R,T)，t)，其中t∈Σ*，T∈Σ。接受：對(duì)于某個(gè)DFAD=(K,Σ,M,S,F)，如果M(S,t)=P,P∈F,則稱字符串t可被該DFAD所接受。例識(shí)別字符串a(chǎn)babaa

是否可為上述DFA所接受。

M(S,ababaa)=M(M(S,a),babaa)=M(M(A,b),abaa)=M(M(B,a),baa)=M(M(A,b),aa)=M(M(B,a),a)=M(A,a)=ZZ是終止?fàn)顟B(tài)，所以,字符串a(chǎn)babaa可為該DFA所接受。運(yùn)行DFA：識(shí)別輸入字符串是否可被DFA所接受的過程。(3)不確定有窮狀態(tài)自動(dòng)機(jī)NFAa.NFA的引進(jìn)例設(shè)有正則文法G3.3[Z]：

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0相應(yīng)的FA如下：存在U∷=WT和V∷=WTTUW

TV映像不唯一：狀態(tài)W，字符T下映像到U或V。a,0aa,000a,0ZSNI0不確定的有窮狀態(tài)自動(dòng)機(jī)通常定義如下。

NFA是一個(gè)五元組(K,Σ,M,S,F)，其中,K:狀態(tài)集Σ：字母表

M:K×Σ→K的子集所組成集合

SK開始狀態(tài)集

FK終止?fàn)顟B(tài)集文法G[Z]:

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0

NFAN=（{S，I，N，Z}，{a,0},M,{S},{Z}）其中，M:M(S,a)={I,Z}M(S,0)={N,Z}M(I,a)={I,Z}M(I,0)={I,Z}M(N,a)={}M(N,0)={N,Z}M(Z,a)={}M(Z,0)={}NFA與DFA的區(qū)別主要在于兩方面:

開始狀態(tài)與映像文法G[Z]:

Z∷=Z0｜T1｜0｜1T∷=Z0｜0

NFAN=

({S,T,Z},{0,1},M,{S},{Z})

其中M=？b.運(yùn)行NFA擴(kuò)充了的映象M：

M(R,ε)={R},其中R是任意的狀態(tài)；

M(R,Tt)=M(Q1,t)∪M(Q2,t)∪…∪M(Qn,t)，其中，M(R,T)={Q1，Q2，…，Qn

}接受：若對(duì)于某NFA存在狀態(tài)P,P∈F,有P∈M(S′,t)，S′∈S，則說字符串t可被該NFA所接受。當(dāng)一個(gè)輸入字符串為NFA所接受時(shí)，它就是相應(yīng)文法的句子。關(guān)于輸入字符串a(chǎn)0a00，運(yùn)行NFA的過程如下：步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1Sa0a00I,ZI2I0a00I,ZI3Ia00I,ZI4I00I,ZI5I0I,ZZ文法G[Z]:

Z::=a|Ia|I0|0|N0I::=a|Ia|I0N::=0|N0G[Z]：

Z::=Z0|T1|0|1T::=Z0|0關(guān)于輸入字符串1010010,運(yùn)行相應(yīng)NFA的過程如下：步驟當(dāng)前狀態(tài)輸入的其余部分可能的選擇選擇1S1010010ZZ2Z

010010T，ZT3T

10010ZZ4Z

0010T，ZZ5Z

010T，ZT6T

10ZZ7Z

0T，ZZc.從NFA生成DFA思路：假定對(duì)于一個(gè)NFA，存在狀態(tài)R，對(duì)于它有：

M(R,T)=｛Q1,Q2,…,Qn｝即，轉(zhuǎn)換到的狀態(tài)可能是Q1或Q2，…，也可能是Qn。為使NFA成為等價(jià)的DFA,把狀態(tài)集合{Q1,Q2,…,Qn｝看成單個(gè)狀態(tài)，用[Q1,Q2,…,Qn]表示這單個(gè)狀態(tài)，如:

M(S,0)={T,Z}M'([S],0)=[T，Z]

注意：DFA的狀態(tài)名中所包含的原有狀態(tài)名按字典順序排列。NFAN=(K,∑,M,S,F)確定化為：DFAN'=(K',∑,M',S',F')其中，K'=K的一切子集組成的集合

S'=[S1,S2,…,Sn],這里S={S1，S2，…，Sn}M'：M([R1，R2，…，Rm],T)=[Q1,Q2,…,Qj]j這里M({R1,R2,…,Rm},T)=

M(Ri,T)={Q1,Q2,…,Qj}i=1F={