簡介：
本文是系列部落格的第一篇，主要講解和分析正規表達式規則以及JAVA中原生正規表達式引擎的使用。在後續的文章中會涉及基于NFA的正規表達式引擎内部的工作原理，并在此基礎上用1000行左右的JAVA代碼,實作一個支援常用功能的正規表達式引擎。它支援貪婪比對和懶惰比對；支援零寬度字元（如“\b”， “\B”）；支援常用字元集（如“\d”， “\s”等）；支援自定義字元集（“[a-f]”，“[^b-k] ”等）；支援所有重複操作（“*”，“+”，“?”，“{n，m}”等）；支援通配符（“. ”）；支援運算符本身的轉義字元（“\*”，“\.”等）；支援命名捕獲組。本系列部落格的目的是了解正規表達式的内部工作原理，是以沒有考慮正規表達式引擎的工作效率以及正負斷言和非命名捕獲組等不常用的功能，後續的工作将會對其優化并完備其功能。由于正規表達式引擎的實作需要運用資料結構中的相關内容，閱讀本系列部落格前請熟悉棧，隊列，圖以及JAVA中容器等相關知識。
歡迎探讨，如有錯誤敬請指正
如需轉載，請注明出處 http://www.cnblogs.com/nullzx/
1. 正規表達式的作用
正規表達式的功能就是在文本串中搜尋特定模式的字元串。我們以下面方框中豆瓣電影網頁中給出的資訊為例，我們想在這些文本中找出所有的日期資訊，我們發現日期資訊的字元格式在以下文本串中具有特定的格式，都是xxxx-xx-xx的模式（比如2017-01-27），這裡的x表示一個具體的數字。是以我們搜尋的字元串的格式就是“\d{4}-\d{2}-\d{2}”，在正規表達式中\d表示數字，{n}表示重複n次。
| 猜火車2 猜火車2 / 迷幻列車2(港) / T2:Trainspotting 2017-01-27(英國) / 伊萬·麥克格雷格 / 約翰尼·李·米勒 / 羅伯特·卡萊爾 / 艾文·布萊納 / 雪莉·亨德森 / 安傑拉·奈迪亞科娃 / 史蒂文·羅伯特森 / 戈登·肯尼迪 / 西蒙·韋爾 / 詹姆斯·卡沙莫 / 梁佩詩 / 阿塔·雅谷伯 / 埃文·威爾什 /... ... 7.8 (5392人評價) 寶貝老闆 寶貝老闆 / 娃娃老闆 / 波士BB(港) 2017-03-12(邁阿密電影節) / 2017-03-31(美國) / 亞曆克·鮑德溫 / 邁爾斯·克裡斯托弗·巴克什 / 吉米·坎摩爾 / 麗莎·庫卓 / 史蒂夫·布西密 / 托比·馬奎爾 / 詹姆斯·麥格拉思 / 康拉德·弗農 / 薇薇安·葉 / 小埃裡克·貝爾 / 大衛·索倫 / 伊迪·米爾曼... 8.3 (184408人評價) 逃出絕命鎮 逃出絕命鎮 / 訪‧吓(港) 2017-01-23(聖丹斯電影節) / 2017-02-24(美國) / 丹尼爾·卡盧亞 / 艾莉森·威廉姆斯 / 凱瑟琳·基納 / 布萊德利·惠特福德 / 卡賴伯·蘭德裡·瓊斯 / 馬庫斯·亨德森 / 貝蒂·加布裡埃爾 / 勒凱斯·斯坦菲爾德 / 斯蒂芬·魯特 / 李雷爾·哈瓦瑞... 7.5 (51576人評價) |
由于排版的需要，以上文本框中的内容比下圖實際處理資料中的内容為基礎進行了删減
我們通過正規表達式測試工具進行文本串中特定模式串\d{4}-\d{2}-\d{2}比對，結果如下圖所示
通過得到的處理結果，我們搜尋到了文本串中所有的日期資訊。從這個例子我們可以看出正規表達式引擎的主要功能就是在給定的文本串中搜尋符合正則表達規則的特定模式的字元串，而這個特定的模式是我們通過分析文本串中感興趣的資訊總結得到的一般規律。比如要得到文本中電影的評分，字元串的格式就是“\d.\d”。
除了上述例子外，正規表達式還有很多應用。例如，在注冊使用者時，驗證使用者輸入的郵箱是否合法；在網絡爬蟲技術中，爬取我們感興趣的相關内容；編譯器設計中，我們還可以将正規表達式作為詞法分析器，等等。使用正規表達式能夠使我們更友善，更加高效的解決字元串模式比對的相關問題，而不必為每一個問題單獨寫一個程式。這裡我們所說的效率高，是指編寫程式的效率更高，而非程式的運作效率。
我們的目的是寫一個正規表達式引擎，是以我們接下來就非常有必要了解一下正規表達式的一般規則。
2. JAVA正規表達式的規則
2.1 自定義字元集
| [abc] | a或b或c |
| [^abc] | 除了a，b，c的其它字元 |
| [a-zA-Z] | 滿足a-z範圍的字元或A-Z範圍的字元 |
例子：下面的正規表達式會比對兩個字元，第一個為小寫字母，第二個為數字，文本串中已捕獲的内容用紅色表示。
正規表達式：“[a-z][0-9]”
文本串内容：“absef809sefdk1dfes12389”
2.2 已定義字元集
| . | 可以比對非換行符以外的任何字元,能否比對換行符是可配置的 |
| \d | 數字，等價于[0-9] |
| \D | 非數字，等價于[^0-9] |
| \s | 空白符，等價于[ \t\n\x0B\f\r] |
| \S | 非空白符，等價于[^\s] |
| \w | 字母、數字或下劃線，等價于[a-zA-Z_0-9] |
| \W | 非字母和數字，等價于[^\w] |
例子：下面的正規表達式會比對以非空白字元開頭和非空白字元結尾，中間是“abc”的字元串，總共需要捕獲5個字元，文本串中已捕獲的内容用紅色表示。
正規表達式：“\Sabc\S”
文本串内容：“abcd abc defabcyjkabc”
2.3 轉義字元（不解釋）
| \t | The tab character ('\u0009') |
| \n | The newline (line feed) character ('\u000A') |
| \r | The carriage-return character ('\u000D') |
| \f | The form-feed character ('\u000C') |
| \a | The alert (bell) character ('\u0007') |
| \e | The escape character ('\u001B') |
| \cx | The control character corresponding to x |
2.4 零寬度邊界字元
零寬度邊界字元，隻會比對一個位置而不會占有字元
| ^ | 行開始 |
| $ | 行結束 |
| \b | 單詞的開始邊界或結束邊界 |
| \B | 非單詞的邊界 |
例子：下面的正規表達式會比對字元串“abc”，并且要求第一個字元‘a’的前面不是字母字元和數字字元，最後一個字元‘c’的後面不是字母字元和數字字元。正規表達式總共需要捕獲3個字元，文本串中已捕獲的内容用紅色表示。
正規表達式：“\babc\b”
文本串内容：“abc dabcd abc abcd -abc”
2.5 貪婪重複模式（盡量多重複）
X表示一個合法的正規表達式
| X? | X重複一次或0次 |
| X* | X,重複0次或多次 |
| X+ | X重複至少1次 |
| X{n} | X重複剛好n次 |
| X{n,} | X重複至少n次 |
| X{n,m} | X重複至少n次，最多m次 |
例子：下面的正規表達式會比對以a開頭和a界結尾的,中間有盡可能多的其它字元，且其它字元要求至少有一次，文本串中已捕獲的内容用紅色表示。
正規表達式：“a.+a”
文本串内容：“zxyabcdefasseaa09876”
2.6 懶惰重複模式（盡量少重複）
| X?? | |
| X*? | |
| X+? | |
| X{n}? | |
| X{n,}? | |
| X{n,m}? |
例子：下面的正規表達式會比對以a開頭和a界結尾的,中間有盡可能少的其它任意字元，且其它任意字元要求至少有一次。文本串中已捕獲的内容用紅色表示。
正規表達式：“a.+?a”
2.7 邏輯運算符
X和Y分别表示兩個正規表達式
XY先滿足正規表達式X，然後滿足正規表達式Y的正規表達式
X|Y 滿足正規表達式X或滿足正規表達式Y的正規表達式
注意優先級，X|YZ 等價于 X|(YZ)，而（X|Y）Z表示XZ|YZ
正規表達式：“a(b|c)d”
文本串内容：“zxyabcdefacdeaabd876”
2.8 括号
在正規表達式中的作用有兩個，一個和四則運算中的括号相同，用來改變優先級，另一個用于分組捕獲。分組捕獲又分為兩種，一種是自定義命名的分組，還有一種是未命名的分組（或者稱為自動編号分組）。
命名分組的格式為：（?<name>X），其中X表示一個正規表達式
例子：下面的正規表達式表示已數字開頭，中間是字母，以數字結尾的字元串。名為letter的捕獲組捕獲符合該正規表達式中間為字母的部分。文本串中捕獲的内容用紅色表示。
正規表達式：“\d+(?<letter>[a-zA-Z]+)\d+”
文本串内容：“0123ab456def gisd4ZDG6zz”
名為letter的捕獲組中的内容為：“0123ab456def gisd4ZDG6zz”
對于未命名分組，每一對括号實際上都是一對分組，正規表達式引擎會在編譯該表達式的時候會從左到右掃描正規表達式，對未命名分組進行編号。遇到的第1個左括号（和相應比對的右括号）是第1組，遇到的第2個左括号（和相應比對的右括号）是第2組，……。第0組的内容比對的是整個正規表達式。實際上組号配置設定過程是要從左向右掃描兩遍的：第一遍隻給未命名組配置設定，第二遍隻給自定義命名組配置設定，也就是說自定義命名分組也是有編号的，且所有自定義命名組的組号都大于未命名的組号。
2.9 特殊字元的比對
對于一些在正規表達式中具有特殊含義的特殊字元，比如“{”，“*”“\”等等，如果我們想在文本串中捕獲它們，就隻能通過轉義的方式。比如我們想比對文本串中以“{”花括号開頭，花括号結尾“}”，中間有任意數量其它字元,且其它任意字元盡可能少。我們的正規表達式就可以寫成“\{.*？\}”，它可以比對以下字元串中的“abcde{fghi{jklmn}op}xyz”。
正規表達式：“\\.*？\\” 表示已“\”開頭和“\”結尾中間為任意數量且盡可能少的其它字元。它可以比對以下字元串中的“abcde\fghi\jklmn\op\xyz”
2.10 零寬斷言
在某些特殊的情況下，如果我們隻是想要比對某個字元有（或者沒有）出現，但并不想去捕獲它的時候，我們就需要零寬度斷言。零寬度斷言和\b等零寬度字元一樣，都是比對一個位置，并不消耗字元，但零寬度斷言可以是由表達式構成，功能也就更加強大。零寬度斷言分為四種情況。
零寬度正預測斷言
“預測”表示向比對内容的後方看，“正”表示比對的意思
一般格式：“exp1(?=exp2)”
含義：比對文本串中符合正規表達式exp1的内容，且文本串中已比對exp1的字元串的後面必須比對exp2，但不消耗文本串中比對exp2的字元，且結果中不捕獲exp2比對的内容。不消耗比對exp2的字元的意思是，下一次搜尋從文本串中比對exp1的後面開始，而不是從比對exp2的後面開始。注意，exp2右括号後面一般不能再跟正規表達式否則，不會比對到任何東西。
例子：下面的正規表達式會比對一個單詞，且這個單詞必須以ing結尾。文本串中捕獲的内容用紅色标示，綠色表示正預言的比對。
正規表達式："\b\w+(?=ing\b)"
文本串内容："i am singing while you are dancing"
注意，正規表達式不能寫成"\b\w+(?=ing)\b"，這樣不會比對任何字元串，因為不存在任何一個字元串後面是ing，同時又要求ing是結束的邊界（由于不消耗文本串中的ing）。
同理，"\b\w+(?=ing)ing" 等價于 "\b\w+ing"
零寬度正回顧斷言
“回顧”表示向比對内容的前方看，“正”表示比對的意思
一般格式：“(?<=exp2)exp1”
含義：比對文本串中符合正規表達式exp1的内容，且文本串中已比對exp1的内容前面必須比對exp2，但在結果中不捕獲exp2的比對内容。注意，exp2左括号前面不能再跟正規表達式否則，不會比對到任何東西。
例子：下面的正規表達式會比對一個單詞，且這個單詞必須以anti開頭。文本串中捕獲的内容用紅色标示，綠色表示正回顧的比對。
正規表達式："(?<=\banti)\w+\b"
文本串内容："this is an antibody, not an antivirus"
注意，正規表達式不能寫成"\b(?<=anti)\w+\b"，原因和正預測是一樣的，因為“\b”和“anti”是互斥的，也就是說沒有一個字元同時滿足即使“\b”又是“anti”。
零寬度負預測斷言
“預測”表示向比對内容的後方看，“負”表示不比對的意思
一般格式：“exp1(?!exp2)”
含義：比對文本串中符合正規表達式exp1的内容，且比對exp1的内容後面不能比對exp2。和正預測不同，我們一般可以構成如下的正規表達式exp1(?!exp2)exp3，隻要exp2和exp3不相同就不會構成互斥。
例子：下面的正規表達式會比對一個單詞，且這個單詞不能以ing結尾。文本串中捕獲的内容用紅色标示。
例子：下面的正規表達式會比對一個單詞，且這個單詞不能以anti開頭。文本串中捕獲的内容用紅色标示。
正規表達式："\\b(?!anti)\\w+\\b"
文本串："this is an antibody, not an antivirus"
零寬度負回顧斷言
“回顧”表示向比對内容的前方看，“負”表示不比對的意思
一般格式：“(?<!exp2)exp1”
含義：捕獲文本串中符合正規表達式exp1的内容，且捕獲的内容前面不能比對exp2。和正回顧不同，我們一般可以構成如下的正規表達式“exp3(?<!exp2)exp1”，隻要exp2和exp3不相同就會構成互斥。
正規表達式："\\b\\w+(?<!ing)\\b";
文本串："i am singing , you are danceing";
3. JAVA中正規表達式引擎的使用
對同一個正規表達式，從鍵盤上輸入的形式和程式中由字元串表示的正規表達式的形式是不同的。比如我們最開始舉例時使用的正規表達式 \d{4}-\d{2}-\d{2} ，在JAVA中用字元串表示的形式如下
String reg = “\\d{4}-\\d{2}-\\{2}”
因為在字元串中，需要用兩個“\\”表示一個“\”
JAVA中使用正規表達式主要涉及到兩個類，一個是Pattern類，另一個是Matcher類，他們都位于java.util.regex包中。Pattern主要的功能就是将正規表達式轉換成NFA（不确定有限自動狀态機）或者DFA（确定有限自動狀态機）。Matcher的作用是通過Pattern産生的FNA或DFA對文本串進行比對。
Pattern類的構造函數：
public static Pattern compile(String regex)
public static Pattern compile(String regex, int flags)
第二個構造函數中的flag，可以是下列屬性值的組合，它們會影響比對結果。
| CANON_EQ Enables canonical equivalence. |
| CASE_INSENSITIVE 大小寫不敏感 |
| COMMENTS 允許正規表達式中出現注釋 預設情況下正規表達式中不允許出現正規表達式規定的注釋 |
| DOTALL “.”可以比對任何字元 預設情況下不能比對 “\r\n”和“\n” |
| LITERAL 該模式下将轉義字元就表示字元本身 “\\d”就表示一個“\”和“d”而不表示數字的字元集 |
| MULTILINE 多行模式：^表示字元串中每一行的開始，$表示字元串中每一行的結束 預設情況下：^表示字元串的開始，$表示字元串的結束 |
| UNICODE_CASE Enables Unicode-aware case folding. |
| UNICODE_CHARACTER_CLASS 使用該選項使得原先已定義好的字元集相容Unicode編碼 |
| UNIX_LINES 類Unix下的換行：“\n” 預設情況下使用Windows下的換行，即：“\r\n”或者 “\n” |
Pattern類下還有一個matcher方法，我們通過該matcher方法産生Matcher對象，該方法參數表示待比對的文本串。
public Matcher matcher(CharSequence input)
Matcher下的find方法用于對文本串的比對，如果發現比對就傳回真，當再次調用find函數時，會從上次已比對的位置繼續搜尋。
Matcher下的group方法用于傳回比對的字元串，start和end方法用于傳回比對的字元串在文本串中的開始和結束位置，注意不包含結束位置。
package javalearning;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class RegularExpTest {
public static void main(String[] args){
String reg = "[a-z]((?<digtal>\\d+)(b|c)d)[A-Z]";
String txt = "zdfasdfre1234bdXrt";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(txt);
while(m.find()){
System.out.println("--------比對結果----------");
System.out.printf("[%2d, %2d) : %s\n", m.start(), m.end(), m.group());
System.out.println("--------自動命名組比對結果--------");
for(int i = 0; i < m.groupCount(); i++){
System.out.printf("group %2d [%2d, %2d) : %s\n",i, m.start(i), m.end(i), m.group(i));
}
System.out.println("--------自定義命名組比對結果--------");
System.out.printf("digtal [%2d, %2d) : %s\n", m.start("digtal"), m.end("digtal"), m.group("digtal"));
System.out.println();
System.out.println();
System.out.println();
}
}
}
運作結果
| --------比對結果---------- [ 8, 16) : e1234bdX --------自動命名組比對結果-------- group 0 [ 8, 16) : e1234bdX group 1 [ 9, 15) : 1234bd group 2 [ 9, 13) : 1234 --------自定義命名組比對結果-------- digtal [ 9, 13) : 1234 |
4. 參考内容
[1] 30分鐘學會正規表達式
[2] 正規表達式線上測試工具
[3] 正規表達式線上測試工具