第04章正則表達(dá)式

1、1形式語(yǔ)言與自動(dòng)機(jī) 第四章 正則表達(dá)式南京航空航天大學(xué)南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 胡胡 軍軍2第四章 正則表達(dá)式o 1.1 正則表達(dá)式的定義p 1.2 正則表達(dá)式和有窮自動(dòng)機(jī)的關(guān)系p 1.3 正則表達(dá)式的等價(jià)變換p 1.4 正則表達(dá)式的應(yīng)用31.1 正則表達(dá)式定義o 正則表達(dá)式（Regular Expression:Regex）的由來(lái)n人類神經(jīng)系統(tǒng)如何工作的早期研究: Warren McCulloch 和 Walter Pitts 兩位神經(jīng)生理學(xué)家研究出一種數(shù)學(xué)方式來(lái)描述這些神經(jīng)網(wǎng)絡(luò);n1956 年, 一位Stephen Kleene 的數(shù)學(xué)家在 McCulloc

2、h 和 Pitts 早期工作的基礎(chǔ)上，發(fā)表了標(biāo)題為“神經(jīng)網(wǎng)事件的表示法”的論文，引入了正則表達(dá)式的概念;n Ken Thompson 是 Unix 的主要發(fā)明人;正則表達(dá)式的第一個(gè)實(shí)用應(yīng)用程序就是 Unix 中的 qed 編輯器;nJeffrey Friedl 在其著作Mastering Regular Expressions （中文版譯作：精通正則表達(dá)式，第三版）4正則表達(dá)式示例o例4.1 在字母表0，1上，0*1+1*0表示：n 出現(xiàn)若干個(gè)0后以一個(gè)1結(jié)尾，或者出現(xiàn)若干個(gè)1后以一個(gè)0結(jié)尾的一切字符串的集合。n 用集合的表示形式就是0*11*0；o例4.2 在字母表a，b上，(a+b)*aa

3、a(a+b)*表示：n 字符串中至少要連續(xù)出現(xiàn)三個(gè)a。n 用集合的表示形式就是a,b*aaaa,b*o正則表達(dá)式和它所代表的集合形式上有很大的相似性正則表達(dá)式和它所代表的集合形式上有很大的相似性。大致上，正則表達(dá)式的“+”相當(dāng)于集合中的并運(yùn)算符“”，正則表達(dá)式的“*”與集合中的閉包運(yùn)算符一致，正則表達(dá)式的“連接”相當(dāng)于集合的連接運(yùn)算。5正則表達(dá)式的遞歸定義o 定義 4.1 設(shè)是一個(gè)字母表，上的正則表達(dá)式正則表達(dá)式以及由它們代表的集合代表的集合，遞歸定義如下：(1) 是一個(gè)正則表達(dá)式，代表空集。(2) 是一個(gè)正則表達(dá)式，代表集合。(3) 對(duì)于中每個(gè)符號(hào)a , a是正則表達(dá)式，代表集合a。(4)

4、如果r和s是正則表達(dá)式，分別代表集合R和S，則 (r+s),(rs)和(r*)是正則表達(dá)式，分別代表集合RS, RS和R*。正則表達(dá)式R代表的字符串集合記為L(zhǎng)(R)。6正則表達(dá)式示例o例4.3 給出=a，b,則對(duì)上的一些正則表達(dá)式與它們各自所代表的集合列表示于圖4.1中：正則表達(dá)式r代表的集合L(r)ab(a+b)(ab)（a*）(a+b)*)(a(b*)(a*)b)(a*)aba,baba*a,b*ab*a*ba*7正則表達(dá)式表示的約定o為了盡量減少括號(hào)，做如下的約定：（1）每個(gè)正則表達(dá)式最外層的一對(duì)括號(hào)可以省略。（2）規(guī)定正則表達(dá)式構(gòu)造的優(yōu)先次序?yàn)椋?* 最高級(jí) 連接（如 rs ） 次高級(jí)

5、 + 最低級(jí)凡是符合此種順序的，括號(hào)可以省略。（3）同一種構(gòu)造（如同為 +，連接或 *）連續(xù)出現(xiàn)時(shí)，規(guī)定從左到右依次構(gòu)造，中間的括號(hào)可以省略。o例如（0（1*）+0）就可寫成01*+0，(a*)(b)(a*)就可寫成a*ba*。但是，(a+b)* 不可寫成a+b*，因?yàn)榍罢弑硎鞠葮?gòu)造(a+b)，后構(gòu)造(a+b)*，結(jié)果代表集合a,b*；而后者根據(jù)優(yōu)先次序的約定，表示先構(gòu)造b*, 再構(gòu)造a+b*，結(jié)果代表集合a,b*；這兩個(gè)集合顯然是不相等的。8正則表達(dá)式的示例o例4.5 構(gòu)造一個(gè)正則表達(dá)式，使它能代表如下的集合S：S的每個(gè)元素都是倒數(shù)第十個(gè)字符是1的0、1串。o即使構(gòu)造一個(gè)NFA接受這個(gè)S，也

6、要設(shè)11個(gè)狀態(tài)和20個(gè)函數(shù)，若是用DFA那就更復(fù)雜了。o要用一個(gè)正則表達(dá)式來(lái)代表S，就簡(jiǎn)單多了：(0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)9正則表達(dá)式 - 字符串集合01*(01*)(01)0 后面跟上任意多個(gè)1= 0(1*)= 0, 01, 011, 0111, = 001, 0101, 01101, 011101, 0后面跟上任意多個(gè)1，然后以01結(jié)尾S = 0, 110正則表達(dá)式 - 字符串集合(0+1)*= e, 0, 1, 00, 01, 10, 11, 任意的字符串0+1= 0, 1(0+1)*01(0+1)*長(zhǎng)度為1的

7、字符串集合包含 01 的所有字符串集合(0+1)*010以 010 結(jié)尾的字符串11正則表達(dá)式 - 字符串集合(0+1)(0+1)(0+1)(0+1)(0+1)串長(zhǎng)為2串長(zhǎng)為3(0+1)(0+1)*+(0+1)(0+1)(0+1)*(0+1)(0+1)*串長(zhǎng)為偶數(shù)(0+1)(0+1)(0+1)*串長(zhǎng)為3的倍數(shù)所有字符串長(zhǎng)度是偶數(shù)或3的倍數(shù)= 串長(zhǎng)為 0, 2, 3, 4, 6, 8, 9, 10, 12, .12(0+1)(0+1)+(0+1)(0+1)(0+1)*(0+1)(0+1)(0+1)(0+1)(0+1)長(zhǎng)度為2的串長(zhǎng)度為 3的串(0+1)(0+1)+(0+1)(0+1)(0+1)長(zhǎng)

8、度為2或3的串字符串可以劃分為長(zhǎng)度為2或3的子串正則表達(dá)式 - 字符串集合13(0+1)(0+1)+(0+1)(0+1)(0+1)*字符串可以劃分為長(zhǎng)度為2或3的子串0011010011e1011010110包括了所有的字符串，除了長(zhǎng)度為1的串(0+1)(0+1)+(0+1)(0+1)(0+1)*= 除了0，1之外的所有的字符串正則表達(dá)式 - 字符串集合14(1+01+001)*(e+0+00)最多兩個(gè) 0在兩個(gè)1之間的最多只有兩個(gè)0；結(jié)論：(1+01+001)*(e+0+00) = x:|x 不包含子串 000永遠(yuǎn)不能出現(xiàn)連續(xù)的三個(gè)00110010110001001000e正則表達(dá)式 - 字

9、符串集合15字符串集合-正則表達(dá)式o 構(gòu)造一個(gè)包含連續(xù)兩個(gè)0的字符串集合的正則表達(dá)式.S = 0, 1(0+1)*00(0+1)*(任意符號(hào)串) 00 (任意符號(hào)串)16o 構(gòu)造一個(gè)不包含兩個(gè)連續(xù)0的字符串集合的正則表達(dá)式：S = 0, 1. 每個(gè)0后面跟上至少一個(gè)1. 在末尾最多只能有一個(gè)0(011*) (e + 0)1*(011*)*(e + 0)1110110101101010每個(gè)0后面跟上至少一個(gè)1結(jié)尾有可能是一個(gè)0開(kāi)始的的時(shí)候可能有多個(gè)1字符串集合-正則表達(dá)式17o 構(gòu)造一個(gè)字符串中包含偶數(shù)個(gè)0的集合的正則表達(dá)式：S = 0, 1偶數(shù)個(gè)0 = (包含兩個(gè)0的子串)* 包含兩個(gè)0的串

10、= 1*01*01* (1*01*01*)*字符串集合-正則表達(dá)式181.2 正則表達(dá)式和有窮自動(dòng)機(jī)的關(guān)系o定理定理4.1 設(shè)設(shè)r是一個(gè)正則表達(dá)式，則存在一個(gè)具有是一個(gè)正則表達(dá)式，則存在一個(gè)具有-轉(zhuǎn)移的有窮轉(zhuǎn)移的有窮自動(dòng)機(jī)接受自動(dòng)機(jī)接受L（r）。）。o證明 ： （結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法）歸納基礎(chǔ)歸納基礎(chǔ) 設(shè)構(gòu)成r的構(gòu)造數(shù)目為0，即r是沒(méi)有經(jīng)過(guò)任何“+”、“連接”和“*”構(gòu)造的正則表達(dá)式，因此它只能是 ， 或 中的某個(gè)符號(hào)a，下面針對(duì)這三種情況分別討論。（1）r=, 對(duì)應(yīng)的 NFA M是：不能從初始狀態(tài)q0到達(dá)終結(jié)狀態(tài)qf ，所以這個(gè)NFA 只能接受空集。19正則表達(dá)式 -有窮自動(dòng)機(jī)o（2）r=,

11、 對(duì)應(yīng)的 NFA M是：因?yàn)閝0既是初始狀態(tài)，又是終結(jié)狀態(tài)，同時(shí)M也沒(méi)有其他轉(zhuǎn)移動(dòng)作，所以這個(gè)NFA 只能接受。o（3）r=a (a), 對(duì)應(yīng)的 NFA M是：因?yàn)檫@個(gè)NFA只有一個(gè)轉(zhuǎn)移r函數(shù)(q0 ,a)=qf,而qf又是終結(jié)狀態(tài)，所以這個(gè)NFA 只接受a。20正則表達(dá)式-有窮自動(dòng)機(jī)o歸納步驟歸納步驟 設(shè)對(duì)少于i(i1)次構(gòu)造構(gòu)成的正則表達(dá)式命題成立，現(xiàn)在的正則表達(dá)式r由i次構(gòu)造構(gòu)成。根據(jù)r最后一次構(gòu)成的形式，分三種情況討論：o情況情況1 r = r1 + r2 。這里r1 和r2都是由少于i次構(gòu)造構(gòu)成的正則表達(dá)式，所以根據(jù)歸納法假設(shè)，存在NFA M1 =（ Q1 ,1 ,1 ,q1 ,f1

12、）,使得L(M1)=L(r1)；存在NFA M2 =（ Q2 ,2 ,2 ,q2 ,f2）,使得L(M2)=L(r2)。不妨假定Q1 , Q2不相交，現(xiàn)構(gòu)造新的NFA M = (Q1 Q2q0 ,f0, 12 ,q0 ,f0),其中定義為：（1）(q0 ,)=q1 ,q2；（2）對(duì)于Q1-f1中的q ,1中的a： (q ,a)= 1(q ,a)；（3）對(duì)于Q2-f2中的q ,2中的a：(q ,a)= 2(q ,a)； （4）(f1 ,)=f0,(f2 ,)=f0。21正則表達(dá)式-有窮自動(dòng)機(jī)o對(duì)于新構(gòu)造的這個(gè)-NFA M，用圖表示如下：oM從它的初始狀態(tài)q0出發(fā)，不用讀任何符號(hào)即可同時(shí)進(jìn)入M1和

13、M2，然后，完全模擬M1和M2的動(dòng)作，直到達(dá)到它們各自的終結(jié)狀態(tài)f1和f2 。M在這兩個(gè)狀態(tài)上，也不用讀任何符號(hào)即可進(jìn)入它自己的終結(jié)狀態(tài)f0 。顯然，M接受的集合恰好是M1和M2接受的集合的并集，即L(M)= L(M1)L(M2)。22正則表達(dá)式-有窮自動(dòng)機(jī)o情況情況2 r = r1 r2 。設(shè)M1和M2與在情況1中的表示相同，仍假定Q1 , Q2不相交，現(xiàn)構(gòu)造新的NFA M = (Q1 Q2 , 12 ,q1 ,f2),其中定義為：(1)對(duì)于Q1-f1中的q ,1中的a，(q ,a)= 1(q ,a)；(2)(f1 ,)=q2；(3) 對(duì)于Q2中的q ,2中的a，(q ,a)= 2(q ,a

14、)。23正則表達(dá)式-有窮自動(dòng)機(jī)o情況情況3 r = r1* 。r1是由少于i次構(gòu)造構(gòu)成的正則表達(dá)式，所以根據(jù)歸納法假設(shè)，存在NFA M1 =（ Q1 ,1 ,1 ,q1 ,f1）,使得L(M1)=L(r1)。現(xiàn)在構(gòu)造-NFA M =（Q1 q0,f0,1 ,1 ,q0 ,f0）,其中定義為：(1)(q0 ,)=q1,f0；(2)對(duì)于Q1-f1中的q ,1中的a， (q ,a)= 1(q ,a)；(3)(f1,)=q1,f0。24正則表達(dá)式-有窮自動(dòng)機(jī)：q0eq0a Sq0q1aRSNFARNFASq0q1eee25正則表達(dá)式-有窮自動(dòng)機(jī)：R + SNFARNFASq0q1eeeeR*NFARq

15、0q1eeee26正則表達(dá)式-有窮自動(dòng)機(jī)o例4.6 根據(jù)定理4.1給出的構(gòu)造方法，對(duì)正則表達(dá)式10*+0構(gòu)造一個(gè)對(duì)應(yīng)的NFA。27Road mapregularexpressionNFA28Road mapregularexpressionNFA2-stateGNFAGNFA29有窮自動(dòng)機(jī)-正則表達(dá)式o定理定理4.2 如果如果L被一個(gè)被一個(gè)DFA接受，則接受，則L可用一個(gè)正則表達(dá)式代表?？捎靡粋€(gè)正則表達(dá)式代表。o證明 設(shè)DFA: A =(q1,q2,qn,q1 ,F)中的狀態(tài)進(jìn)行狀態(tài)進(jìn)行1,2,3,.,n編號(hào)編號(hào)。編號(hào)可以是任意的，但是編號(hào)一旦定好，在定理證明過(guò)程中不能改變；其中1表示起始狀態(tài)

16、。n 引入記號(hào)R（k)ij ,是字符串的集合，具體定義如下： R（k）ij =x|(qi ,x)=qj ,且中間僅經(jīng)過(guò)編號(hào)正則表達(dá)式o 對(duì)Rkij的k取值進(jìn)行歸納證明：（k取值從0開(kāi)始）nbasis：（k=0）o 當(dāng)ij： o 當(dāng)i=j ： ninduction:31有窮自動(dòng)機(jī)-正則表達(dá)式o例4.6 給出一個(gè)由圖4.2表示的DFA M，按照定理4.2中的方法，構(gòu)造一個(gè)正則表達(dá)式代表L(M)。o對(duì)于所有的i和j,以及k=0,1,2, rkij的值列在圖4.3中。其中某些正則表達(dá)式已被化簡(jiǎn)。例如，根據(jù)定理4.2中的（4-1）式，r122 = r021(r011)* r012 + r022 = 0(

17、)*0+,顯然可以化簡(jiǎn)為00+。又例如，r213= r112（r122）* r123 + r113 =0(+ 00)*(1+01)+1,由于(+ 00)*可以化簡(jiǎn)成(00)*，(1+01)可以寫成(+0)1，我們可以有r213=0(00)*(+0)1+1。更進(jìn)一步，由于(00)*(+0)可以化簡(jiǎn)為0*，于是r213可以化簡(jiǎn)為00*1+1，最后化簡(jiǎn)為0*1。32有窮自動(dòng)機(jī)-正則表達(dá)式o圖4.2中DFA的rkij表k=0k=1k=2rk11rk12rk13rk21rk22rk23rk31rk32rk3301010+1010+001+010+1(00)*0(00)*0*10(00)*(00)*0*1

18、(0+1)(00)*0(0+1)(00)*+(0+1)0*1問(wèn)題：每次計(jì)算需要構(gòu)造問(wèn)題：每次計(jì)算需要構(gòu)造n3個(gè)個(gè)rkij， 每次迭代時(shí)每次迭代時(shí)rkij長(zhǎng)度增長(zhǎng)長(zhǎng)度增長(zhǎng)4n33有窮自動(dòng)機(jī)-正則表達(dá)式o 狀態(tài)消除法（構(gòu)造GNFA,Generalized-NFA）相對(duì)每一個(gè)終結(jié)狀態(tài)相對(duì)每一個(gè)終結(jié)狀態(tài)q,都消除中間狀都消除中間狀態(tài)，只保留態(tài)，只保留q0 .34有窮自動(dòng)機(jī)-正則表達(dá)式o 對(duì)于每一個(gè) ,通過(guò)上述的狀態(tài)消除法，會(huì)得到以下：或者35有窮自動(dòng)機(jī)-正則表達(dá)式 示例轉(zhuǎn)成GNFA消除狀態(tài)B36有窮自動(dòng)機(jī)-正則表達(dá)式 示例37正則表達(dá)式的等價(jià)變換o+操作的交換律操作的交換律: R+S = S+R。因?yàn)?/p>

19、：R+S代表集合L(R)L(S),而S+R代表集合L(S)L(R)，集合的并運(yùn)算是滿足交換律的;o+操作的結(jié)合律操作的結(jié)合律: (R+S)+T = R+(S+T)；o“連接”構(gòu)造的結(jié)合律：結(jié)合律： (RS)T = R(ST)。o“連接連接”構(gòu)造不滿足交換律：構(gòu)造不滿足交換律：n 對(duì)于一般的正則表達(dá)式R和S，不能寫RS = SR。n 反例，如：R=1,S=0,它們分別代表集合1和0，RS代表集合10，而SR代表集合01，顯然這兩個(gè)集合是不相等的。38正則表達(dá)式的化簡(jiǎn)：o +R = R+ = R。根據(jù)正則表達(dá)式與它們所代表的集合的對(duì)應(yīng)關(guān)系，等式正確; 是構(gòu)造符“+”的單位元。oR = R = R。

20、是連接構(gòu)造的單位元。oR = R=。代表集合L(R)或L(R)，任何集合與空集的連接結(jié)果都是空集。這就說(shuō)明是連接構(gòu)造的零元。oR(S+T)=RS+RT。 這一條稱為“連接”對(duì)于“+”的左分配左分配律律。o(S+T)R=SR+TR。 這一條稱為“連接”對(duì)于“+”的右分配右分配律律。o(R*)* = R* ；o* =；o* =；o擴(kuò)充定義擴(kuò)充定義R+：代表集合：L(R)+ 。定律：+ R+ = R* ， R+ = RR* 39發(fā)現(xiàn)正則表達(dá)式定律的一般方法o考慮一條所謂的定律：考慮一條所謂的定律：(R+S)* =(R* S*)* 這里R，S是任意兩個(gè)正則表達(dá)式。o一般方法一般方法：將每個(gè)變量都當(dāng)做一

21、個(gè)不同的符號(hào)，即可將任何帶變量的一般的正則表達(dá)式都看做一個(gè)具體的正則表達(dá)式，即一個(gè)沒(méi)有變量的正則表達(dá)式。o例如，把表達(dá)式把表達(dá)式(R+S)*中的變量中的變量R和和S分別換成符號(hào)分別換成符號(hào)a和和b,就得就得出正則表達(dá)式出正則表達(dá)式(a+b)*。而這個(gè)正則表達(dá)式所代表的語(yǔ)言L(a+b)*)，顯然是字符a和b組成的一切串的集合。另一方面，把表達(dá)式(R* S*)*的變量R和S也分別換成符號(hào)a和b, 就得出正則表達(dá)式(a* b*)*。而這個(gè)正則表達(dá)式所代表的語(yǔ)言L(a* b*)*)，顯然也是字符a和b組成的一切串的集合。左右相等成立。o定理 4.4 設(shè)E是帶有變量V1，V2，Vm 的正則表達(dá)式，通過(guò)把

22、Vi的每次出現(xiàn)，都換成符號(hào)ai（i=1，2，,m）得到具體的表達(dá)式C。則從每個(gè)屬于L(C)的串a(chǎn)1a2ak出發(fā)，把每個(gè)符號(hào)ai（1ik）都換成對(duì)應(yīng)語(yǔ)言L(Vi)，就構(gòu)造出L(E)。401.4 正則表達(dá)式的應(yīng)用o UNIX中的正則表達(dá)式o 詞法分析o 查找文本中的模式o .41UNIX中的正則表達(dá)式o對(duì)正則表達(dá)式記號(hào)的第一項(xiàng)擴(kuò)展是：大多數(shù)實(shí)際應(yīng)用都處理ASC字符集，這是比較大的字母表。如果有一種需要在表達(dá)式中把所有字符都列出來(lái)，書寫起來(lái)就非常不方便。因此，UNIX中的正則表達(dá)式允許書寫字符類來(lái)盡可能緊湊地表示大的字符集。字符類的規(guī)則是： 符號(hào)“.”(圓點(diǎn))表示任意字符。(真正的小數(shù)點(diǎn)要用其它辦法

23、區(qū)分) 序列a1a2ak表示正則表達(dá)式a1+a2+ak 。利用這個(gè)記號(hào)大約節(jié)省一半字符，因?yàn)椴恍枰獙懗?+ 號(hào)。例如，C語(yǔ)言中的比較運(yùn)算所用的4種運(yùn)算符可表示成 = ！。42UNIX中的正則表達(dá)式o 在方括號(hào)之內(nèi)規(guī)定形如x-y的范圍，表示ASC序列中從x到y(tǒng)的所有字符。由于數(shù)字是按順序編號(hào)的，大寫字母和小寫字母也是這樣，所以只用很少的輸入就能表示真正關(guān)心的許多字符。例如，十個(gè)數(shù)字表示成0-9，大寫字母表示成A-Z，所有字母和數(shù)字的集合表示成A-Za-z0-9。如果要在字符列表中包含負(fù)號(hào)，就放在開(kāi)頭或結(jié)尾，這就不會(huì)和字母范圍的表示形式混淆。例如，要形成帶符號(hào)的十進(jìn)制整數(shù)，所用的數(shù)字集合以及正號(hào)和

24、負(fù)號(hào)等表示成- + 0-9。o 幾種最常見(jiàn)的字符類有特殊記號(hào)。例如： a):digit: 表示十進(jìn)制數(shù)字的集合,和0-9意義相同。 b):alpha: 表示字母字符的集合,和A-Za-z意義相同。 c):alnum: 表示字母和數(shù)字字符的集合,和A-Za-z0-9意義相同。43UNIX中的正則表達(dá)式o另外，有幾個(gè)在UNIX正則表達(dá)式中使用的運(yùn)算符，這些運(yùn)算符不擴(kuò)大所表示的語(yǔ)言范圍，但有時(shí)更容易表達(dá)所要表達(dá)的內(nèi)容。它們是：（1）用 代替 + 來(lái)表示并。（2）運(yùn)算符?表示“0個(gè)或1個(gè)”。因此在UNIX中，R？與本書中定義的正則表達(dá)式的+R是一樣的。（3）運(yùn)算符 + 表示“1個(gè)或多個(gè)”。因此在UNI

25、X中，R+ 與本書中的正則表達(dá)式RR*是一樣的。（4）運(yùn)算符n表示“n個(gè)副本”。 因此在UNIX中，R5是RRRRR的縮寫。44詞法分析o例 4.9 圖4.4中是lex命令的部分輸入的一個(gè)例子,描述了C語(yǔ)言中一些單詞。其中第一行處理關(guān)鍵字else，要執(zhí)行的動(dòng)作是返回一個(gè)符號(hào)常量（在這里是ELSE），交給語(yǔ)法分析器進(jìn)一步處理。第二行包含一個(gè)描述標(biāo)識(shí)符的正則表達(dá)式：定義標(biāo)識(shí)符為一個(gè)字母后跟零個(gè)或多個(gè)字母或數(shù)字。要執(zhí)行的動(dòng)作是首先把這個(gè)標(biāo)識(shí)符輸入到符號(hào)表（如果這個(gè)標(biāo)識(shí)符還沒(méi)有在表中出現(xiàn)的話）；lex還在一個(gè)緩沖區(qū)記下所發(fā)現(xiàn)的這個(gè)單詞，所以這段代碼確切地知道發(fā)現(xiàn)了什么標(biāo)識(shí)符；最后，詞法分析器返回符號(hào)常

26、量ID（在本例中用ID表示標(biāo)識(shí)符）。45詞法分析o圖4.4第三項(xiàng)是符號(hào) =，這是一個(gè)雙字符運(yùn)算符，圖中顯示的最后一行是一個(gè)單字符運(yùn)算符 =，這種單詞都將轉(zhuǎn)化為內(nèi)部符號(hào)（本例中分別用GE和ASGN表示）。在實(shí)際上在圖中可能出現(xiàn)每一個(gè)關(guān)鍵字，每一個(gè)運(yùn)算符和每一個(gè)標(biāo)點(diǎn)符號(hào)（如逗號(hào)和括號(hào)），以及各種常量（如數(shù)與串）的表達(dá)式。這些表達(dá)式大多是非常簡(jiǎn)單的，只是一個(gè)或多個(gè)具體的字符的序列。但是，有一部分帶有一些標(biāo)識(shí)符的風(fēng)格，需要用正則表達(dá)式記法的所有能力來(lái)描述。整數(shù)、浮點(diǎn)數(shù)、字符串以及注釋都是串的例子，它們都是用正則表達(dá)式描述的。o把一組表達(dá)式（如圖中所顯示的這些）轉(zhuǎn)化為有窮自動(dòng)機(jī)，原則上像在定理4.2.1

27、所述的形式化方法那樣，先把正則表達(dá)式化為具有轉(zhuǎn)移的NFA，必要時(shí)可化為DFA。o現(xiàn)在唯一的問(wèn)題是一次可能識(shí)別出多個(gè)單詞。例如串else不僅匹配關(guān)鍵字else，而且也匹配標(biāo)識(shí)符表達(dá)式else，標(biāo)準(zhǔn)的解決辦法是讓詞法分析器優(yōu)先處理先列出的表達(dá)式。因此，如果要讓像else這樣的關(guān)鍵字成為保留的（即不能用做標(biāo)識(shí)符），就簡(jiǎn)單地把這些關(guān)鍵字列在所有標(biāo)識(shí)符表達(dá)式的前面。當(dāng)然，要想不發(fā)生這種問(wèn)題，最好在語(yǔ)言中規(guī)定不能將關(guān)鍵字做為標(biāo)識(shí)符使用。46查找文本中的模式o假設(shè)要掃描非常大的Web頁(yè)面并探測(cè)出個(gè)人或單位地址?？赡苤皇窍虢⑧]件地址表，或者也許是在嘗試根據(jù)地點(diǎn)來(lái)對(duì)業(yè)務(wù)進(jìn)行分類，使得系統(tǒng)能夠回答像“替我找一家

28、在我目前位置需10分鐘車程的飯館”這樣的模糊查詢。o要解決這樣的問(wèn)題就會(huì)把注意力集中到街道的地址上。什么樣的字符串是街道的地址呢？這是要解決的中心問(wèn)題。也許在測(cè)試軟件時(shí)發(fā)現(xiàn)遺漏了某些情形，就需要修改表達(dá)式以“捕捉”所遺漏情形。首先，街道地址可能以“Street（大街）”或縮寫“St.”來(lái)結(jié)尾。但是，有些人住在“Avenue（大道）”或“Road（大路）”上，這些也可能有縮寫。因此，可能把類似于Street St. Avenue Ave. Road Rd.這樣的東西做為正則表達(dá)式的結(jié)尾.在上述表達(dá)式中,使用了UNIX風(fēng)格的記號(hào),用垂直豎線而不是 + 號(hào)做為“并”運(yùn)算符。還有，用前面加一個(gè)反斜杠對(duì)

29、“.”進(jìn)行轉(zhuǎn)義,使其恢復(fù)圓點(diǎn)“.”的原來(lái)的意義。因?yàn)樵赨NIX表達(dá)式中，圓點(diǎn)“.”已規(guī)定為具有“任意字符”的特殊含義。47查找文本中的模式o像Street這樣的稱乎前面必須有街道的名稱。在英美等國(guó)家，這個(gè)名稱通常是一個(gè)大寫字母后跟著一些小寫字母，可以用UNIX表達(dá)式 A-Za-z* 來(lái)描述這個(gè)模式。但是有些街道名稱包含多個(gè)單詞，比如美國(guó)華盛頓特區(qū)的Rhode Island Avenue（羅得島大道）就是這樣。因此，在發(fā)現(xiàn)遺漏了這種形式的地址之后，就可以把街道名稱的描述修訂為：A-Za-z*（ A-Za-z*）*上述表達(dá)式以包含一個(gè)大寫字母和零個(gè)或多個(gè)小寫字母的一組字符開(kāi)頭，后面跟著零個(gè)或多個(gè)同樣的組，但后面這些組的前面都有一個(gè)空格。因?yàn)榭崭褚彩荱NIX中的一個(gè)字符，為了避免上述表達(dá)式看起來(lái)像一條UNIX命令行中用空格分開(kāi)的兩個(gè)表達(dá)式，所以用引號(hào)把整個(gè)表達(dá)式都括起來(lái)，但引