首先聲明，這篇文章不是教你如何寫正規表達式，而是教你寫一個能執行正規表達式的執行引擎。 網上教你寫正規表達式的文章、教程很多，但教你寫引擎的并不多。很多人認為我就是用用而已，沒必要了解那麼深，但知道原理是在修煉内功，正規表達式底層原理并不單單是用在這，而是出現在計算機領域的各個角落。了解原理可以讓你以後寫字元串比對時正規表達式能夠信手拈來，了解原理也是觸類旁通的基礎。廢話不多說，直接開始正式内容。
本文是我個人做的動手實踐性項目，是以未完整支援所有文法，而且因為是用NFA實作的是以性能比生産級的執行引擎差好多。目前源碼已開放至
https://github.com/xindoo/regex，後續會繼續更新，歡迎Star、Fork 提PR。
目前支援的正則語義如下:
- 基本文法: . ? * + () |
- 字元集合: []
- 特殊類型符号: d D s S w W
前置知識
聲明：本文不是入門級的文章，是以如果你想看懂後文的内容，需要具備以下的基本知識。
- 基本的程式設計知識，雖然這裡我是用java寫的，但并不要求懂java，懂其他文法也行，基本流程都是類似，就是文法細節不同。
- 了解正規表達式，知道簡單的正規表達式如何寫。
- 基本的資料結構知識，知道有向圖的概念，知道什麼是遞歸和回溯。
有限狀态機
有限狀态機(Finite-state machine)，也被稱為有限狀态自動機(finite-state automation)，是表示有限個狀态以及在這些狀态之間的轉移和動作等行為的數學計算模型(From
維基百科 狀态機) 。 聽起來晦澀難懂，我用大白話描述一遍，狀态機其實就是用圖把狀态和狀态之間的關系描述出來，狀态機中的一個狀态可以在某些給定條件下變成另外一種狀态。舉個很簡單的例子你就懂了。
比如我今年18歲，我現在就是處于18歲的狀态，如果時間過了一年，我就變成19歲的狀态了，再過一年就20了。當然我20歲時時光倒流2年我又可以回到18歲的狀态。這裡我們就可以把我的年齡狀态和時間流逝之間的關系用一個自動機表示出來，如下。
每個圈代表一個節點表示一種狀态，每條有向邊表示一個狀态到另一個狀态的轉移條件。上圖中狀态是我的年齡，邊表示時間正向或者逆向流逝。
有了狀态機之後，我們就可以用狀态機來描述特定的模式，比如上圖就是年齡随時間增長的模式。如果有人說我今年18歲，1年後就20歲了。照着上面的狀态機我們來算下，1年後你才19歲，你這不是瞎說嗎！ 沒錯，狀态機可以來判定某些内容是否符合你狀态機描述的模式了。喲，一不小心就快扯到正規表達式上了。
我們這裡再引入兩種特殊的狀态：起始态和接受态(終止态)，見名知意，不用我過多介紹了吧，起始态和終止态的符号如下。
我們拿狀态機來做個簡單的字元串比對。比如我們有個字元串“zsx”，要判斷其他字元串是否和"zxs"是一緻的，我們可以為"zxs"先建立一個自動機，如下。
對于任意一個其他的字元串，我們從起始态0開始，如果下一個字元能比對到0後邊的邊上就往後走，比對不上就停止，一直重複，如果走到終止态3說明這個字元串和”zxs“一樣。任意字元串都可以轉化成上述的狀态機，其實到這裡你就知道如何實作一個隻支援字元串比對的正規表達式引擎了，如果想支援更多的正則語義，我們要做的更多。
狀态機下的正規表達式
我們再來引入一條特殊的邊，學名叫$\epsilon$閉包(emm！看到這些符号我就回想起上學時被數學支配的恐懼)，其實就是一條不需要任何條件就能轉移狀态的邊。
沒錯，就隻這條紅邊本邊了，它在正規表達式狀态機中起着非常重要的連接配接作用，可以不依賴其他條件直接跳轉狀态，也就是說在上圖中你可以直接從1到2。
有了 $\epsilon$閉包的加持，我們就可以開始學如何畫正規表達式文法對應的狀态機了。
串聯比對
首先來看下純字元比對的自動機，其實上面已經給過一個"zxs"的例子了，這裡再貼一下，其實就是簡單地用字元串在一起而已，如果還有其他字元，就繼續往後串。
兩個表達式如何傳在一起，也很簡單，假如我們已經有兩個表達式A B對應的狀态機，我們隻需要将其用$\epsilon$串一起就行了。
并聯比對 (正規表達式中的 |)
正規表達式中的| 辨別二選一都可以，比如A|B A能比對 B也能比對，那麼A|B就可以表示為下面這樣的狀态圖。
從0狀态走A或B都可以到1狀态，完美的诠釋了A|B語義。
重複比對(正規表達式中的 ? + *)
正規表達式裡有4種表示重複的方式，分别是：
- ？重複0-1次
-
- 重複1次以上
-
- 重複0次以上
-
{n,m} 重複n到m次
我來分别畫下這4種方式如何在狀态機裡表示。
重複0-1次 ？
0狀态可以通過E也可以依賴$\epsilon$直接跳過E到達1狀态，實作E的0次比對。
0到1後可以再通過$\epsilon$跳回來，就可以實作E的1次以上比對了。
仔細看其實就是? +的結合。
比對指定次數
這種建圖方式簡單粗暴，但問題就是如果n和m很大的話，最後生成的狀态圖也會很大。其實可以把指定次數的比對做成一條特殊的邊，可以極大減小圖的大小。
特殊符号(正規表達式中的 . d s……)
正規表達式中還支援很多某類的字元，比如.表示任意非換行符，d辨別數字，[]可以指定字元集…… ，其實這些都和圖的形态無關，隻是某調特殊的邊而已，自己實作的時候可以選擇具體的實作方式，比如後面代碼中我用了政策模式來實作不同的比對政策，簡化了正則引擎的代碼。
子表達式(正規表達式 () )
子表達可以Tompson算法，其實就是用遞歸去生成()中的子圖，然後把子圖拼接到目前圖上面。（什麼Tompson說的那麼高大上，不就是遞歸嗎！）
練習題
來練習畫下 a(a|b)* 的狀态圖，這裡我也給出我畫的，你可以參考下。
代碼實作
建圖
看完上文之後相信你一直知道如果将一個正規表達式轉化為狀态機的方法了，這裡我們要将理論轉化為代碼。首先我們要将圖轉化為代碼辨別，我用State表示一個節點，其中用了Map> next表示其後繼節點，next中有個key-value就是一條邊，MatchStrategy用來描述邊的資訊。
public class State {
private static int idCnt = 0;
private int id;
private int stateType;
public State() {
this.id = idCnt++;
}
Map<MatchStrategy, List<State>> next = new HashMap<>();
public void addNext(MatchStrategy path, State state) {
List<State> list = next.get(path);
if (list == null) {
list = new ArrayList<>();
next.put(path, list);
}
list.add(state);
}
protected void setStateType() {
stateType = 1;
}
protected boolean isEndState() {
return stateType == 1;
}
} NFAGraph表示一個完整的圖，其中封裝了對圖的操作，比如其中就實作了上文中圖串 并聯和重複的操作（注意我沒有實作{}）。
public class NFAGraph {
public State start;
public State end;
public NFAGraph(State start, State end) {
this.start = start;
this.end = end;
}
// |
public void addParallelGraph(NFAGraph NFAGraph) {
State newStart = new State();
State newEnd = new State();
MatchStrategy path = new EpsilonMatchStrategy();
newStart.addNext(path, this.start);
newStart.addNext(path, NFAGraph.start);
this.end.addNext(path, newEnd);
NFAGraph.end.addNext(path, newEnd);
this.start = newStart;
this.end = newEnd;
}
//
public void addSeriesGraph(NFAGraph NFAGraph) {
MatchStrategy path = new EpsilonMatchStrategy();
this.end.addNext(path, NFAGraph.start);
this.end = NFAGraph.end;
}
// * 重複0-n次
public void repeatStar() {
repeatPlus();
addSToE(); // 重複0
}
// ? 重複0次哦
public void addSToE() {
MatchStrategy path = new EpsilonMatchStrategy();
start.addNext(path, end);
}
// + 重複1-n次
public void repeatPlus() {
State newStart = new State();
State newEnd = new State();
MatchStrategy path = new EpsilonMatchStrategy();
newStart.addNext(path, this.start);
end.addNext(path, newEnd);
end.addNext(path, start);
this.start = newStart;
this.end = newEnd;
}
} 整個建圖的過程就是依照輸入的字元建立邊和節點之間的關系，并完成圖的拼接。
private static NFAGraph regex2nfa(String regex) {
Reader reader = new Reader(regex);
NFAGraph nfaGraph = null;
while (reader.hasNext()) {
char ch = reader.next();
String edge = null;
switch (ch) {
// 子表達式特殊處理
case '(' : {
String subRegex = reader.getSubRegex(reader);
NFAGraph newNFAGraph = regex2nfa(subRegex);
checkRepeat(reader, newNFAGraph);
if (nfaGraph == null) {
nfaGraph = newNFAGraph;
} else {
nfaGraph.addSeriesGraph(newNFAGraph);
}
break;
}
// 或表達式特殊處理
case '|' : {
String remainRegex = reader.getRemainRegex(reader);
NFAGraph newNFAGraph = regex2nfa(remainRegex);
if (nfaGraph == null) {
nfaGraph = newNFAGraph;
} else {
nfaGraph.addParallelGraph(newNFAGraph);
}
break;
}
case '[' : {
edge = getCharSetMatch(reader);
break;
}
case '^' : {
break;
}
case '$' : {
break;
}
case '.' : {
edge = ".";
break;
}
// 處理特殊占位符
case '\\' : {
char nextCh = reader.next();
switch (nextCh) {
case 'd': {
edge = "\\d";
break;
}
case 'D': {
edge = "\\D";
break;
}
case 'w': {
edge = "\\w";
break;
}
case 'W': {
edge = "\\W";
break;
}
case 's': {
edge = "\\s";
break;
}
case 'S': {
edge = "\\S";
break;
}
// 轉義後的字元比對
default:{
edge = String.valueOf(nextCh);
break;
}
}
break;
}
default : { // 處理普通字元
edge = String.valueOf(ch);
break;
}
}
if (edge != null) {
NFAState start = new NFAState();
NFAState end = new NFAState();
start.addNext(edge, end);
NFAGraph newNFAGraph = new NFAGraph(start, end);
checkRepeat(reader, newNFAGraph);
if (nfaGraph == null) {
nfaGraph = newNFAGraph;
} else {
nfaGraph.addSeriesGraph(newNFAGraph);
}
}
}
return nfaGraph;
} 這裡我用了設計模式中的政策模式将不同的比對規則封裝到不同的MatchStrategy類裡，目前我實作了. d D s S w w，具體細節請參考代碼。這麼設計的好處就是簡化了比對政策的添加，比如如果我想加一個x 隻比對16進制字元，我隻需要加個政策類就好了，不必改很多代碼。
比對
其實比對的過程就出從起始态開始，用輸入作為邊，一直往後走，如果能走到終止态就說明可以比對，代碼主要依賴于遞歸和回溯，代碼如下。
public boolean isMatch(String text) {
return isMatch(text, 0, nfaGraph.start);
}
private boolean isMatch(String text, int pos, State curState) {
if (pos == text.length()) {
if (curState.isEndState()) {
return true;
}
return false;
}
for (Map.Entry<MatchStrategy, List<State>> entry : curState.next.entrySet()) {
MatchStrategy matchStrategy = entry.getKey();
if (matchStrategy instanceof EpsilonMatchStrategy) {
for (State nextState : entry.getValue()) {
if (isMatch(text, pos, nextState)) {
return true;
}
}
} else {
if (!matchStrategy.isMatch(text.charAt(pos))) {
continue;
}
// 周遊比對政策
for (State nextState : entry.getValue()) {
if (isMatch(text, pos + 1, nextState)) {
return true;
}
}
}
}
return false;
} 下集預告
還有下集？沒錯，雖然到這裡已經是實作了一個基本的正規表達式引擎，但距離可用在生産環境還差很遠，預告如下。
功能完善化
本身上面的引擎對正則語義支援不是很完善，後續我會繼續完善代碼，有興趣可以收藏下源碼
，但應該不會出一篇新部落格了，因為原理性的東西都在這裡，剩下的就是隻是一些編碼工作 。
DFA引擎
上文隻是實作了NFA引擎，NFA的引擎建圖時間複雜度是O(n)，但比對一個長度為m的字元串時因為涉及到大量的遞歸和回溯，最壞時間複雜度是O(mn)。與之對比DFA引擎的建圖時間複雜度O(n^2)，但比對時沒有回溯，是以比對複雜度隻有O(m)，性能差距還是挺大的。
DFA引擎實作的大體流程是先構造NFA(本文内容)，然後用子集構造法将NFA轉化為DFA，預計未來我會出一篇部落格講解細節和具體實作。
正則引擎優化
首先DFA引擎是可以繼續優化的，使用Hopcroft算法可以進一步将DFA圖壓縮，更少的狀态節點更少的轉移邊可以實作更好的性能。其次，目前生産級的正則引擎很多都不是單純用NFA或者DFA實作的，而是二者的結合，不同正規表達式下用不同的引擎可以達到更好的綜合性能，簡單說NFA圖小但要回溯，DFA不需要回溯但有些情況圖會特别大。敬請期待我後續博文。