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

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

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

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

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

6、要設11個狀態和20個函數，若是用DFA那就更復雜了。o要用一個正則表達式來代表S，就簡單多了：(0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)9正則表達式 - 字符串集合01*(01*)(01)0 后面跟上任意多個1= 0(1*)= 0, 01, 011, 0111, = 001, 0101, 01101, 011101, 0后面跟上任意多個1，然后以01結尾S = 0, 110正則表達式 - 字符串集合(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 結尾的字符串11正則表達式 - 字符串集合(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)*串長為偶數(0+1)(0+1)(0+1)*串長為3的倍數所有字符串長度是偶數或3的倍數= 串長為 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的子串正則表達式 - 字符串集合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之外的所有的字符串正則表達式 - 字符串集合14(1+01+001)*(e+0+00)最多兩個 0在兩個1之間的最多只有兩個0；結論：(1+01+001)*(e+0+00) = x:|x 不包含子串 000永遠不能出現連續的三個00110010110001001000e正則表達式 - 字

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

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

11、 對應的 NFA M是：因為q0既是初始狀態，又是終結狀態，同時M也沒有其他轉移動作，所以這個NFA 只能接受。o（3）r=a (a), 對應的 NFA M是：因為這個NFA只有一個轉移r函數(q0 ,a)=qf,而qf又是終結狀態，所以這個NFA 只接受a。20正則表達式-有窮自動機o歸納步驟歸納步驟 設對少于i(i1)次構造構成的正則表達式命題成立，現在的正則表達式r由i次構造構成。根據r最后一次構成的形式，分三種情況討論：o情況情況1 r = r1 + r2 。這里r1 和r2都是由少于i次構造構成的正則表達式，所以根據歸納法假設，存在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不相交，現構造新的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正則表達式-有窮自動機o對于新構造的這個-NFA M，用圖表示如下：oM從它的初始狀態q0出發，不用讀任何符號即可同時進入M1和

13、M2，然后，完全模擬M1和M2的動作，直到達到它們各自的終結狀態f1和f2 。M在這兩個狀態上，也不用讀任何符號即可進入它自己的終結狀態f0 。顯然，M接受的集合恰好是M1和M2接受的集合的并集，即L(M)= L(M1)L(M2)。22正則表達式-有窮自動機o情況情況2 r = r1 r2 。設M1和M2與在情況1中的表示相同，仍假定Q1 , Q2不相交，現構造新的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正則表達式-有窮自動機o情況情況3 r = r1* 。r1是由少于i次構造構成的正則表達式，所以根據歸納法假設，存在NFA M1 =（ Q1 ,1 ,1 ,q1 ,f1）,使得L(M1)=L(r1)。現在構造-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正則表達式-有窮自動機：q0eq0a Sq0q1aRSNFARNFASq0q1eee25正則表達式-有窮自動機：R + SNFARNFASq0q1eeeeR*NFARq

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

16、。n 引入記號R（k)ij ,是字符串的集合，具體定義如下： R（k）ij =x|(qi ,x)=qj ,且中間僅經過編號正則表達式o 對Rkij的k取值進行歸納證明：（k取值從0開始）nbasis：（k=0）o 當ij： o 當i=j ： ninduction:31有窮自動機-正則表達式o例4.6 給出一個由圖4.2表示的DFA M，按照定理4.2中的方法，構造一個正則表達式代表L(M)。o對于所有的i和j,以及k=0,1,2, rkij的值列在圖4.3中。其中某些正則表達式已被化簡。例如，根據定理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。更進一步，由于(00)*(+0)可以化簡為0*，于是r213可以化簡為00*1+1，最后化簡為0*1。32有窮自動機-正則表達式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問題：每次計算需要構造問題：每次計算需要構造n3個個rkij， 每次迭代時每次迭代時rkij長度增長長度增長4n33有窮自動機-正則表達式o 狀態消除法（構造GNFA,Generalized-NFA）相對每一個終結狀態相對每一個終結狀態q,都消除中間狀都消除中間狀態，只保留態，只保留q0 .34有窮自動機-正則表達式o 對于每一個 ,通過上述的狀態消除法，會得到以下：或者35有窮自動機-正則表達式 示例轉成GNFA消除狀態B36有窮自動機-正則表達式 示例37正則表達式的等價變換o+操作的交換律操作的交換律: R+S = S+R。因為

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

20、是連接構造的單位元。oR = R=。代表集合L(R)或L(R)，任何集合與空集的連接結果都是空集。這就說明是連接構造的零元。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發現正則表達式定律的一般方法o考慮一條所謂的定律：考慮一條所謂的定律：(R+S)* =(R* S*)* 這里R，S是任意兩個正則表達式。o一般方法一般方法：將每個變量都當做一

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

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

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

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

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

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

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

28、在我目前位置需10分鐘車程的飯館”這樣的模糊查詢。o要解決這樣的問題就會把注意力集中到街道的地址上。什么樣的字符串是街道的地址呢？這是要解決的中心問題。也許在測試軟件時發現遺漏了某些情形，就需要修改表達式以“捕捉”所遺漏情形。首先，街道地址可能以“Street（大街）”或縮寫“St.”來結尾。但是，有些人住在“Avenue（大道）”或“Road（大路）”上，這些也可能有縮寫。因此，可能把類似于Street St. Avenue Ave. Road Rd.這樣的東西做為正則表達式的結尾.在上述表達式中,使用了UNIX風格的記號,用垂直豎線而不是 + 號做為“并”運算符。還有，用前面加一個反斜杠對“.”進行轉義,使其恢復圓點“.”的原來的意義。因為在UNIX表達式中，圓點“.”已規定為具有“任意字符”的特殊含義。47查找文本中的模式o像Street這樣的稱乎前面必須有街道的名稱。在英美等國家，這個名稱通常是一個大寫字母后跟著一些小寫字母，可以用UNIX表達式 A-Za-z* 來描述這個模式。但是有些街道名稱包含多個單詞，比如美國華盛頓特區的Rhode Island Avenue（羅得島大道）就是這樣。因此，在發現遺漏了這種形式的地址之后，就可以把街道名稱的描述修訂為：