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

1、1形式語言與自動機 第四章 正則表達(dá)式南京航空航天大學(xué)南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)學(xué)院 胡胡 軍軍2第四章 正則表達(dá)式o 1.1 正則表達(dá)式的定義p 1.2 正則表達(dá)式和有窮自動機的關(guān)系p 1.3 正則表達(dá)式的等價變換p 1.4 正則表達(dá)式的應(yīng)用31.1 正則表達(dá)式定義o 正則表達(dá)式（Regular Expression:Regex）的由來n人類神經(jīng)系統(tǒng)如何工作的早期研究: Warren McCulloch 和 Walter Pitts 兩位神經(jīng)生理學(xué)家研究出一種數(shù)學(xué)方式來描述這些神經(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á)式的第一個實用應(yīng)用程序就是 Unix 中的 qed 編輯器;nJeffrey Friedl 在其著作Mastering Regular Expressions （中文版譯作：精通正則表達(dá)式，第三版）4正則表達(dá)式示例o例4.1 在字母表0，1上，0*1+1*0表示：n 出現(xiàn)若干個0后以一個1結(jié)尾，或者出現(xiàn)若干個1后以一個0結(jié)尾的一切字符串的集合。n 用集合的表示形式就是0*11*0；o例4.2 在字母表a，b上，(a+b)*aa

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

4、如果r和s是正則表達(dá)式，分別代表集合R和S，則 (r+s),(rs)和(r*)是正則表達(dá)式，分別代表集合RS, RS和R*。正則表達(dá)式R代表的字符串集合記為L(R)。6正則表達(dá)式示例o例4.3 給出=a，b,則對上的一些正則表達(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為了盡量減少括號，做如下的約定：（1）每個正則表達(dá)式最外層的一對括號可以省略。（2）規(guī)定正則表達(dá)式構(gòu)造的優(yōu)先次序為： * 最高級 連接（如 rs ） 次高級

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

6、要設(shè)11個狀態(tài)和20個函數(shù)，若是用DFA那就更復(fù)雜了。o要用一個正則表達(dá)式來代表S，就簡單多了：(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 后面跟上任意多個1= 0(1*)= 0, 01, 011, 0111, = 001, 0101, 01101, 011101, 0后面跟上任意多個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)*長度為1的

7、字符串集合包含 01 的所有字符串集合(0+1)*010以 010 結(jié)尾的字符串11正則表達(dá)式 - 字符串集合(0+1)(0+1)(0+1)(0+1)(0+1)串長為2串長為3(0+1)(0+1)*+(0+1)(0+1)(0+1)*(0+1)(0+1)*串長為偶數(shù)(0+1)(0+1)(0+1)*串長為3的倍數(shù)所有字符串長度是偶數(shù)或3的倍數(shù)= 串長為 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)長度為2的串長度為 3的串(0+1)(0+1)+(0+1)(0+1)(0+1)長

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

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

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

11、 對應(yīng)的 NFA M是：因為q0既是初始狀態(tài)，又是終結(jié)狀態(tài)，同時M也沒有其他轉(zhuǎn)移動作，所以這個NFA 只能接受。o（3）r=a (a), 對應(yīng)的 NFA M是：因為這個NFA只有一個轉(zhuǎn)移r函數(shù)(q0 ,a)=qf,而qf又是終結(jié)狀態(tài)，所以這個NFA 只接受a。20正則表達(dá)式-有窮自動機o歸納步驟歸納步驟 設(shè)對少于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）對于Q1-f1中的q ,1中的a： (q ,a)= 1(q ,a)；（3）對于Q2-f2中的q ,2中的a：(q ,a)= 2(q ,a)； （4）(f1 ,)=f0,(f2 ,)=f0。21正則表達(dá)式-有窮自動機o對于新構(gòu)造的這個-NFA M，用圖表示如下：oM從它的初始狀態(tài)q0出發(fā)，不用讀任何符號即可同時進(jìn)入M1和

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

14、)。23正則表達(dá)式-有窮自動機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)對于Q1-f1中的q ,1中的a， (q ,a)= 1(q ,a)；(3)(f1,)=q1,f0。24正則表達(dá)式-有窮自動機：q0eq0a Sq0q1aRSNFARNFASq0q1eee25正則表達(dá)式-有窮自動機：R + SNFARNFASq0q1eeeeR*NFARq

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

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

17、)*0+,顯然可以化簡為00+。又例如，r213= r112（r122）* r123 + r113 =0(+ 00)*(1+01)+1,由于(+ 00)*可以化簡成(00)*，(1+01)可以寫成(+0)1，我們可以有r213=0(00)*(+0)1+1。更進(jìn)一步，由于(00)*(+0)可以化簡為0*，于是r213可以化簡為00*1+1，最后化簡為0*1。32有窮自動機-正則表達(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問題：每次計算需要構(gòu)造問題：每次計算需要構(gòu)造n3個個rkij， 每次迭代時每次迭代時rkij長度增長長度增長4n33有窮自動機-正則表達(dá)式o 狀態(tài)消除法（構(gòu)造GNFA,Generalized-NFA）相對每一個終結(jié)狀態(tài)相對每一個終結(jié)狀態(tài)q,都消除中間狀都消除中間狀態(tài)，只保留態(tài)，只保留q0 .34有窮自動機-正則表達(dá)式o 對于每一個 ,通過上述的狀態(tài)消除法，會得到以下：或者35有窮自動機-正則表達(dá)式 示例轉(zhuǎn)成GNFA消除狀態(tài)B36有窮自動機-正則表達(dá)式 示例37正則表達(dá)式的等價變換o+操作的交換律操作的交換律: R+S = S+R。因為

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

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

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

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

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

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

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

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

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

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

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