正則表達式轉NFA代碼

1. 如何將正則表達式轉換為NFA

正則表達式轉換NFA演算法

基礎的正則表達式：

2. 請問java中正則表達式匹配怎麼實現的!

Java中正則表達式匹配的語法規則：

packageorg.luosijin.test;
importjava.util.regex.Matcher;
importjava.util.regex.Pattern;

/**
*正則表達式
*@versionV5.0
*@authorAdmin
*@date2015-7-25
*/
publicclassRegex{

/**
*@paramargs
*@authorAdmin
*@date2015-7-25
*/

publicstaticvoidmain(String[]args){
Patternpattern=Pattern.compile("b*g");
Matchermatcher=pattern.matcher("bbg");
System.out.println(matcher.matches());
System.out.println(pattern.matches("b*g","bbg"));
//驗證郵政編碼
System.out.println(pattern.matches("[0-9]{6}","200038"));
System.out.println(pattern.matches("//d{6}","200038"));
//驗證電話號碼
System.out.println(pattern.matches("[0-9]{3,4}//-?[0-9]+","02178989799"));
getDate("Nov10,2009");
charReplace();
//驗證身份證:判斷一個字元串是不是身份證號碼，即是否是15或18位數字。
System.out.println(pattern.matches("^//d{15}|//d{18}$","123456789009876"));
getString("D:/dir1/test.txt");
getChinese("welcometochina,江西奉新,welcome,你!");
validateEmail("[email protected]");
}
/**
*日期提取:提取出月份來
*@paramstr
*@authorAdmin
*@date2015-7-25
*/
publicstaticvoidgetDate(Stringstr){
StringregEx="([a-zA-Z]+)|//s+[0-9]{1,2},//s*[0-9]{4}";
Patternpattern=Pattern.compile(regEx);
Matchermatcher=pattern.matcher(str);
if(!matcher.find()){
System.out.println("日期格式錯誤!");
return;
}
System.out.println(matcher.group(1));//分組的索引值是從1開始的，所以取第一個分組的方法是m.group(1)而不是m.group(0)。
}
/**
*字元替換:本實例為將一個字元串中所有包含一個或多個連續的「a」的地方都替換成「A」。
*
*@authorAdmin
*@date2015-7-25
*/
publicstaticvoidcharReplace(){
Stringregex="a+";
Patternpattern=Pattern.compile(regex);
Matchermatcher=pattern.matcher("okaaaaLetmeAseeaaaaabooa");
Strings=matcher.replaceAll("A");
System.out.println(s);
}
/**
*字元串提取
*@paramstr
*@authorAdmin
*@date2015-7-25
*/
publicstaticvoidgetString(Stringstr){
Stringregex=".+/(.+)$";
Patternpattern=Pattern.compile(regex);
Matchermatcher=pattern.matcher(str);
if(!matcher.find()){
System.out.println("文件路徑格式不正確！");
return;
}
System.out.println(matcher.group(1));
}
/**
*中文提取
*@paramstr
*@authorAdmin
*@date2015-7-25
*/
publicstaticvoidgetChinese(Stringstr){
Stringregex="[//u4E00-//u9FFF]+";//[//u4E00-//u9FFF]為漢字
Patternpattern=Pattern.compile(regex);
Matchermatcher=pattern.matcher(str);
StringBuffersb=newStringBuffer();
while(matcher.find()){
sb.append(matcher.group());
}
System.out.println(sb);
}
/**
*驗證Email
*@paramemail
*@authorAdmin
*@date2015-7-25
*/
publicstaticvoidvalidateEmail(Stringemail){
Stringregex="[0-9a-zA-Z]+@[0-9a-zA-Z]+//.[0-9a-zA-Z]+";
Patternpattern=Pattern.compile(regex);
Matchermatcher=pattern.matcher(email);
if(matcher.matches()){
System.out.println("這是合法的Email");
}else{
System.out.println("這是非法的Email");
}
}
}

3. 正則表達式

首先我們要了解正則表達式是什麼，它是一種匹配模式， 不僅能匹配匹配字元，還能匹配位置 ，不少人忽略了匹配字元這個作用，往往碰到這種問題就手足無措。

如果正則只有精確匹配是沒有多大意義的，比如：

正則表達式的強大之處在於它的模糊匹配，分為橫向模糊和縱向模糊

橫向模糊：一個正則可匹配的字元串的長度不是固定的，可以是多種情況的
其實現的方式是使用量詞：

比如：

橫向模糊匹配到了多種情況，案例中用的正則是/ab{2,5}c/g，後面多了g，它是正則的一個修飾符。表示全局匹配，即在目標字元串中按順序找到滿足匹配模式的所有子串，強調的是「所有」，而不只是「第一個」。

縱向模糊：一個正則匹配的字元串，具體到某一位字元時，它可以不是某個確定的字元，可以有多種可能
其實現的方式是使用范圍類

-表示連字元，在此處作特殊用處，但是如果我要匹配'a-z'這三個字元呢？可以這么寫：

這樣引擎就不會認為它們是一個氛圍了， ^{符號在范圍類中起取反的作用，} a表示除了a的所有字元。

系統根據范圍類又預定義了一些類方便我們使用：

不加g就是惰性匹配，我匹配完一個就不敢了，懶得再干其他事兒了，加了g就是貪婪模式了,我現在精力無限，會盡可能的幹事兒，但是我還有些理智，不會干超出能力之外的事兒，比如你給我的范圍是{2,5}，我會盡可能做5件事兒，但是不會超過5件事,反正只要在能力范圍內，越多越好

此時我既想盡可能的匹配又想讓它不那麼貪婪有沒有辦法呢？辦法是有的, 貪婪模式一般作用在量詞這里，限制在量詞這里就好了 ，可以在量詞這里加一個？即可搞定。

其中/d{2,5}?/表示，雖然2到5次都行，當2個就夠的時候，就不在往下嘗試了。
此時就達到了我們的要求,不過這里完全是為了講解貪婪模式和惰性模式，並不推薦這么做，我完全可以將{2,5}改成{2}，一樣的效果

知道了惰性模式的原理，我們完全可以鼓搗出其他的各式各樣的情形：

一個模式可以實現橫向和縱向模糊匹配。而多選分支可以支持多個子模式任選其一
具體形式如下：(p1|p2|p3)，其中p1、p2和p3是子模式，用「|」（管道符）分隔，表示其中任何之一

但有個事實我們應該注意，比如我用/good|goodbye/，去匹配"goodbye"字元串時，結果是"good"

而把正則改成/goodbye|good/，結果是

也就是說，分支結構也是惰性的，即當前面的分支匹配上了，後面的就不再嘗試了

並且，使用分支的時候注意使用括弧，

匹配字元，無非就是范圍類、量詞和分支結構的組合使用罷了

分析：

表示一個16進制字元，可以用范圍類[0-9a-fA-F]
其中字元可以出現3或6次，需要是用量詞和分支結構
使用分支結構時，需要注意順序(惰性)

分析：
對每個地方的數字進行分析：
共4位數字，第一位數字可以為[0-2]。
當第1位為2時，第2位可以為[0-3]，其他情況時，第2位為[0-9]。
第3位數字為[0-5]，第4位為[0-9]

如果也要求匹配7:9，也就是說時分前面的0可以省略:

分析：
年，四位數字即可，可用[0-9]{4}。

月，共12個月，分兩種情況01、02、……、09和10、11、12，可用(0[1-9]|1[0-2])。

日，最大31天，可用(0[1-9]|[12][0-9]|3[01])

分析：
整體模式是: 盤符:文件夾文件夾文件夾
其中匹配F:，需要使用[a-zA-Z]:，其中盤符不區分大小寫，注意字元需要轉義。

文件名或者文件夾名，不能包含一些特殊字元，此時我們需要排除范圍類[ ^{:*<>|"? /]來表示合法字元。另外不能為空名，至少有一個字元，也就是要使用量詞+。因此匹配「文件夾」，可用[} :*<>|"? /]+。

另外「文件夾」，可以出現任意次。也就是([^: <>|"? /]+) 。其中括弧提供子表達式。

路徑的最後一部分可以是「文件夾」，沒有，因此需要添加([^:*<>|"? /]+)?。

最後拼接成了一個看起來比較復雜的正則：

用到了惰性匹配，防止把class也提取出來

優化：

^（脫字元）匹配開頭，在多行匹配中匹配行開頭。

$（美元符號）匹配結尾，在多行匹配中匹配行結尾

比如我們把字元串的開頭和結尾用"#"替換（位置可以替換成字元的！）：

多行匹配模式時，二者是行的概念，這個需要我們的注意

是單詞邊界，具體就是w和W之間的位置，也包括w和^之間的位置，也包括w和$之間的位置

首先，我們知道，w是范圍類[0-9a-zA-Z_]的簡寫形式，即w是字母數字或者下劃線的中任何一個字元。而W是排除范圍類[^0-9a-zA-Z_]的簡寫形式，即W是w以外的任何一個字元

此時我們可以看看"[#JS#] #Lesson_01#.#mp4#"中的每一個"#"，是怎麼來的。

第一個"#"，兩邊是"["與"J"，是W和w之間的位置。

第二個"#"，兩邊是"S"與"]"，也就是w和W之間的位置。

第三個"#"，兩邊是空格與"L"，也就是W和w之間的位置。

第四個"#"，兩邊是"1"與"."，也就是w和W之間的位置。

第五個"#"，兩邊是"."與"m"，也就是W和w之間的位置。

第六個"#"，其對應的位置是結尾，但其前面的字元"4"是w，即w和$之間的位置。

知道了的概念後，那麼B也就相對好理解了。

B就是的反面的意思，非單詞邊界。例如在字元串中所有位置中，扣掉，剩下的都是B的。

具體說來就是w與w、W與W、^與W，W與$之間的位置

exp1(?=exp2) 表達式會匹配exp1表達式，但只有其後面內容是exp2的時候才會匹配

exp1(?=exp2) 表達式會匹配exp1表達式，但只有其後面內容不是exp2的時候才會匹配

(?=p)，其中p是一個子模式，即p前面的位置
比如(?=l)，表示'l'字元前面的位置，例如：

而(?!p)就是(?=p)的反面意思

對於位置的理解，我們可以理解成空字元""

因此，把/ ^{hello$/寫成/} ^hello$$$/，是沒有任何問題的：

也就是說字元之間的位置，可以寫成多個。

把位置理解空字元，是對位置非常有效的理解方式

此正則要求只有一個字元，但該字元後面是開頭。

比如把"12345678"，變成"12,345,678"。

可見是需要把相應的位置替換成","

使用(?=d{3}$)就可以做到：

因為逗號出現的位置，要求後面3個數字一組，也就是d{3}至少出現一次。

此時可以使用量詞+：

此時會出現問題：

上面的正則，僅僅表示把從結尾向前數，一但是3的倍數，就把其前面的位置替換成逗號

怎麼解決呢？我們要求匹配的到這個位置不能是開頭。

我們知道匹配開頭可以使用^，但要求這個位置不是開頭怎麼辦？

easy，(?!^)

如果要把"12345678 123456789"替換成"12,345,678 123,456,789"。

此時我們需要修改正則，把裡面的開頭^和結尾$，替換成

其中(?!)怎麼理解呢？

要求當前是一個位置，但不是前面的位置，其實(?!)說的就是B。

因此最終正則變成了：/B(?=(d{3})+)/g

此題，如果寫成多個正則來判斷，比較容易。但要寫成一個正則就比較困難。

那麼，我們就來挑戰一下。看看我們對位置的理解是否深刻

我們可以把原題變成下列幾種情況之一：

1.同時包含數字和小寫字母

2.同時包含數字和大寫字母

3.同時包含小寫字母和大寫字母

4.同時包含數字、小寫字母和大寫字母

上面的正則看起來比較復雜，只要理解了第二步，其餘就全部理解了。

/(?=.*[0-9])^[0-9A-Za-z]{6,12}$/

對於這個正則，我們只需要弄明白(?=.*[0-9])^即可。

分開來看就是(?=.*[0-9])和^。

表示開頭前面還有個位置（當然也是開頭，即同一個位置，想想之前的空字元類比）。

(?=. [0-9])表示該位置後面的字元匹配. [0-9]，即，有任何多個任意字元，後面再跟個數字。

另一種解法：
「至少包含兩種字元」的意思就是說，不能全部都是數字，也不能全部都是小寫字母，也不能全部都是大寫字母。

那麼要求「不能全部都是數字」，怎麼做呢？(?!p)出馬！

三種'都不能'呢？

1.分組和分支結構

括弧是提供分組功能，使量詞'+'作用於z和這個整體

而在多選分支結構(p1|p2)中，此處括弧的作用也是不言而喻的，提供了子表達式的所有可能

而要使用它帶來的好處，必須配合使用實現環境的API

以日期為例。假設格式是yyyy-mm-dd的

提取數據：

match返回的一個數組，第一個元素是整體匹配結果，然後是各個分組（括弧里）匹配的內容，然後是匹配下標，最後是輸入的文本

可以使用正則對象的exec方法：

也可以使用構造函數的全局屬性$1至$9來獲取：

替換:

想把yyyy-mm-dd格式，替換成mm/dd/yyyy怎麼做？

反向引用:

比如要寫一個正則支持匹配如下三種格式：

注意裡面的1，表示的引用之前的那個分組(-|/|.)。不管它匹配到什麼（比如-），1都匹配那個同樣的具體某個字元

括弧嵌套怎麼辦？

以左括弧（開括弧）為准

10是表示第10個分組，還是1和0呢？答案是前者，雖然一個正則里出現10比較罕見

引用不存在的分組會怎樣？

因為反向引用，是引用前面的分組，但我們在正則里引用了不存在的分組時，此時正則不會報錯，只是匹配反向引用的字元本身。例如2，就匹配"2"。注意"2"表示對2進行了轉意

非捕獲分組:

之前文中出現的分組，都會捕獲它們匹配到的數據，以便後續引用，因此也稱他們是捕獲型分組。

如果只想要括弧最原始的功能，但不會引用它，即，既不在API里引用，也不在正則里反向引用。此時可以使用非捕獲分組(?:p)

第二種，匹配整個字元串，然後用引用來提取出相應的數據

思路是找到每個單詞的首字母，當然這里不使用非捕獲匹配也是可以的

首字母不會轉化為大寫的。其中分組(.)表示首字母，單詞的界定，前面的字元可以是多個連字元、下劃線以及空白符。正則後面的?的目的，是為了應對str尾部的字元可能不是單詞字元，比如str是'-moz-transform '

通過key獲取相應的分組引用，然後作為對象的鍵

匹配一個開標簽，可以使用正則<[^>]+>，

匹配一個閉標簽，可以使用</[^>]+>，

但是要求匹配成對標簽，那就需要使用反向引用

其中開標簽<[ ^{>]+>改成<([} >]+)>，使用括弧的目的是為了後面使用反向引用，而提供分組。閉標簽使用了反向引用，</1>。

另外[dD]的意思是，這個字元是數字或者不是數字，因此，也就是匹配任意字元的意思

而當目標字元串是"abbbc"時，就沒有所謂的「回溯」。其匹配過程是：

其中子表達式b{1,3}表示「b」字元連續出現1到3次。

圖中第5步有紅顏色，表示匹配不成功。此時b{1,3}已經匹配到了2個字元「b」，准備嘗試第三個時，結果發現接下來的字元是「c」。那麼就認為b{1,3}就已經匹配完畢。然後狀態又回到之前的狀態（即第6步，與第4步一樣），最後再用子表達式c，去匹配字元「c」。當然，此時整個表達式匹配成功了。

圖中的第6步，就是「回溯」。

你可能對此沒有感覺，這里我們再舉一個例子。正則是：

目標字元串是"abbbc"，匹配過程是：

其中第7步和第10步是回溯。第7步與第4步一樣，此時b{1,3}匹配了兩個"b"，而第10步與第3步一樣，此時b{1,3}只匹配了一個"b"，這也是b{1,3}的最終匹配結果。

這里再看一個清晰的回溯，正則是：

目標字元串是："acd"ef，匹配過程是：

圖中省略了嘗試匹配雙引號失敗的過程。可以看出「.*」是非常影響效率的。

為了減少一些不必要的回溯，可以把正則修改為/"[^"]*"/。

正則表達式匹配字元串的這種方式，有個學名，叫回溯法。

回溯法也稱試探法，它的基本思想是： 從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有「狀態」，當一條路走到「盡頭」的時候（不能再前進），再後退一步或若干步，從另一種可能「狀態」出發，繼續搜索，直到所有的「路徑」（狀態）都試探過。這種不斷「前進」、不斷「回溯」尋找解的方法，就稱作「回溯法」 。

本質上就是深度優先搜索演算法。其中 退到之前的某一步這一過程，我們稱為「回溯」 。從上面的描述過程中，可以看出，路走不通時，就會發生「回溯」。即， 嘗試匹配失敗時，接下來的一步通常就是回溯

道理，我們是懂了。那麼JS中正則表達式會產生回溯的地方都有哪些呢？

3.1 貪婪量詞

之前的例子都是貪婪量詞相關的。比如b{1,3}，因為其是貪婪的，嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試"bbb"，然後再看整個正則是否能匹配。不能匹配時，吐出一個"b"，即在"bb"的基礎上，再繼續嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了。

雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？

此時我們不禁會問，如果當多個貪婪量詞挨著存在，並相互有沖突時，此時會是怎樣？

答案是，先下手為強！因為深度優先搜索。測試如下：

其中，前面的d{1,3}匹配的是"123"，後面的d{1,3}匹配的是"45"。

3.2 惰性量詞
惰性量詞就是在貪婪量詞後面加個問號。表示盡可能少的匹配，比如：

其中d{1,3}?只匹配到一個字元"1"，而後面的d{1,3}匹配了"234"。

雖然惰性量詞不貪，但也會有回溯的現象。比如正則是：

目標字元串是"12345"，匹配過程是：

知道你不貪、很知足，但是為了整體匹配成，沒辦法，也只能給你多塞點了。因此最後d{1,3}?匹配的字元是"12"，是兩個數字，而不是一個。

3.3 分支結構

我們知道分支也是惰性的，比如/can|candy/，去匹配字元串"candy"，得到的結果是"can"，因為分支會一個一個嘗試，如果前面的滿足了，後面就不會再試驗了。

分支結構，可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續嘗試剩下的分支。這種嘗試也可以看成一種回溯。

比如正則：

目標字元串是"candy"，匹配過程：

上面第5步，雖然沒有回到之前的狀態，但仍然回到了分支結構，嘗試下一種可能。所以，可以認為它是一種回溯的

簡單總結就是，正因為有多種可能，所以要一個一個試。直到，要麼到某一步時，整體匹配成功了；要麼最後都試完後，發現整體匹配不成功。

既然有回溯的過程，那麼匹配效率肯定低一些。相對誰呢？相對那些DFA引擎。

而JS的正則引擎是NFA，NFA是「非確定型有限自動機」的簡寫。

大部分語言中的正則都是NFA，為啥它這么流行呢？

答：你別看我匹配慢，但是我編譯快啊，而且我還有趣哦。

而在正則表達式中，操作符都體現在結構中，即由特殊字元和普通字元所代表的一個個特殊整體。

JS正則表達式中，都有哪些結構呢？

其中涉及到的操作符有：

上面操作符的優先順序從上至下，由高到低。

這里，我們來分析一個正則：

因為是要匹配整個字元串，我們經常會在正則前後中加上錨字元^和$。

比如要匹配目標字元串"abc"或者"bcd"時，如果一不小心，就會寫成/^abc|bcd$/。

而位置字元和字元序列優先順序要比豎杠高，故其匹配的結構是：

應該修改成:

2.2 量詞連綴問題

假設，要匹配這樣的字元串：

此時正則不能想當然地寫成/^[abc]{3}+$/，這樣會報錯，說「+」前面沒什麼可重復的：
此時要修改成：

2.3 元字元轉義問題
所謂元字元，就是正則中有特殊含義的字元。

所有結構里，用到的元字元總結如下：

當匹配上面的字元本身時，可以一律轉義：

在string中，也可以把每個字元轉義，當然，轉義後的結果仍是本身：

現在的問題是，是不是每個字元都需要轉義呢？否，看情況。

2.3.1 范圍類中的元字元

跟范圍類相關的元字元有 []、^、- 。因此在會引起歧義的地方進行轉義。例如開頭的^必須轉義，不然會把整個范圍類，看成反義范圍類。

2.3.2 匹配「[abc]」和「{3,5}」

我們知道[abc]，是個字元組。如果要匹配字元串"[abc]"時，該怎麼辦？

可以寫成/[abc]/，也可以寫成/[abc]/，測試如下:

只需要在第一個方括弧轉義即可，因為後面的方括弧構不成字元組，正則不會引發歧義，自然不需要轉義。

同理，要匹配字元串"{3,5}"，只需要把正則寫成/{3,5}/即可。

另外，我們知道量詞有簡寫形式{m,}，卻沒有{,n}的情況。雖然後者不構成量詞的形式，但此時並不會報錯。當然，匹配的字元串也是"{,n}"，測試如下：

var str = "{,3}";
var reg = /{,3}/g;
console.log( str.match(reg)[0] );
// => "{,3}"

2.3.3 其餘情況

比如= ! : - ,等符號，只要不在特殊結構中，也不需要轉義。

但是，括弧需要前後都轉義的，如/(123)/。

至於剩下的^ $ . * + ? | /等字元，只要不在字元組內，都需要轉義的。

因為豎杠「|」,的優先順序最低，所以正則分成了兩部分d{15}和d{17}[dxX]。

d{15}表示15位連續數字。
d{17}[dxX]表示17位連續數字，最後一位可以是數字可以大小寫字母"x"。
可視化如下：

3.2 IPV4地址

正則表達式是：

這個正則，看起來非常嚇人。但是熟悉優先順序後，會立馬得出如下的結構：

((...).){3}(...)

上面的兩個(...)是一樣的結構。表示匹配的是3位數字。因此整個結構是

3位數.3位數.3位數.3位數
然後再來分析(...)：

(0{0,2}d|0?d{2}|1d{2}|2[0-4]d|25[0-5])

它是一個多選結構，分成5個部分：

0{0,2}d ，匹配一位數，包括0補齊的。比如，9、09、009；
0?d{2} ，匹配兩位數，包括0補齊的，也包括一位數；
1d{2} ，匹配100到199;
2[0-4]d ，匹配200-249；
25[0-5] ，匹配250-255。
最後來看一下其可視化形式：

掌握正則表達式中的優先順序後，再看任何正則應該都有信心分析下去了。

至於例子，不一而足，沒有寫太多。

這里稍微總結一下，豎杠的優先順序最低，即最後運算。

只要知道這一點，就能讀懂大部分正則。

另外關於元字元轉義問題，當自己不確定與否時，盡管去轉義，總之是不會錯的。

本文就解決該問題，內容包括：

2.1 是否能使用正則

正則太強大了，以至於我們隨便遇到一個操作字元串問題時，都會下意識地去想，用正則該怎麼做。但我們始終要提醒自己，正則雖然強大，但不是萬能的，很多看似很簡單的事情，還是做不到的。

比如匹配這樣的字元串：1010010001....

雖然很有規律，但是只靠正則就是無能為力。

2.2 是否有必要使用正則

要認識到正則的局限，不要去研究根本無法完成的任務。同時，也不能走入另一個極端：無所不用正則。能用字元串API解決的簡單問題，就不該正則出馬。

比如，從日期中提取出年月日，雖然可以使用正則：

其實，可以使用字元串的split方法來做，即可：

比如，判斷是否有問號，雖然可以使用：

其實，可以使用字元串的indexOf方法：

比如獲取子串，雖然可以使用正則：

其實，可以直接使用字元串的substring或substr方法來做：

var str = "JavaScript";
console.log( str.substring(4) );
// => Script

2.3 是否有必要構建一個復雜的正則

比如密碼匹配問題，要求密碼長度6-12位，由數字、小寫字元和大寫字母組成，但必須至少包括2種字元。

在匹配位置那篇文章里，我們寫出了正則是：

其實可以使用多個小正則來做：

所謂准確性，就是能匹配預期的目標，並且不匹配非預期的目標。

這里提到了「預期」二字，那麼我們就需要知道目標的組成規則。

不然沒法界定什麼樣的目標字元串是符合預期的，什麼樣的又不是符合預期的。

下面將舉例說明，當目標字元串構成比較復雜時，該如何構建正則，並考慮到哪些平衡。

3.1 匹配固定電話

比如要匹配如下格式的固定電話號碼：

055188888888 0551-88888888 (0551)88888888
第一步，了解各部分的模式規則。

上面的電話，總體上分為區號和號碼兩部分（不考慮分機號和+86的情形）。

區號是0開頭的3到4位數字，對應的正則是：0d{2,3}

號碼是非0開頭的7到8位數字，對應的正則是：[1-9]d{6,7}

因此，匹配055188888888的正則是：/^0d{2,3}[1-9]d{6,7}$/

匹配0551-88888888的正則是：/^0d{2,3}-[1-9]d{6,7}$/

匹配(0551)88888888的正則是：/^(0d{2,3})[1-9]d{6,7}$/

第二步，明確形式關系。

這三者情形是或的關系，可以構建分支：

提取公共部分：

進一步簡寫：

上面的正則構建過程略顯羅嗦，但是這樣做，能保證正則是准確的。

上述三種情形是或的關系，這一點很重要，不然很容易按字元是否出現的情形把正則寫成：

/^(?0d{2,3})?-?[1-9]d{6,7}$/
雖然也能匹配上述目標字元串，但也會匹配(0551-88888888這樣的字元串。當然，這不是我們想要的。

其實這個正則也不是完美的，因為現實中，並不是每個3位數和4位數都是一個真實的區號。

這就

4. 將正則表達式(abc)*轉換為nfa，最多需要多少個狀態

5個：起始，a，b，c，結束。
從起始，a，b，c可以轉移到a，b，c，結束四個當中的任何一個。