@[toc]
今天是五一假期第一天枪蘑，這里先給大家拜個晚 咳咳！岖免！祝大家五一快樂岳颇，我這里給大家奉上一篇硬核教程。首先聲明颅湘，這篇文章不是教你如何寫正則表達式话侧，而是教你寫一個能執(zhí)行正則表達式的執(zhí)行引擎。 網(wǎng)上教你寫正則表達式的文章闯参、教程很多瞻鹏，但教你寫引擎的并不多。很多人認為我就是用用而已鹿寨，沒必要理解那么深新博，但知道原理是在修煉內功，正則表達式底層原理并不單單是用在這脚草，而是出現(xiàn)在計算機領域的各個角落赫悄。理解原理可以讓你以后寫字符串匹配時正則表達式能夠信手拈來，理解原理也是觸類旁通的基礎馏慨。廢話不多說埂淮，直接開始正式內容。
本文是我個人做的動手實踐性項目写隶，所以未完整支持所有語法倔撞，而且因為是用NFA實現(xiàn)的所以性能比生產(chǎn)級的執(zhí)行引擎差好多。目前源碼已開放至https://github.com/xindoo/regex樟澜，后續(xù)會繼續(xù)更新误窖，歡迎Star、Fork 提PR秩贰。
目前支持的正則語義如下:
- 基本語法: . ? * + () |
- 字符集合: []
- 特殊類型符號: \d \D \s \S \w \W
前置知識
聲明：本文不是入門級的文章霹俺，所以如果你想看懂后文的內容，需要具備以下的基本知識毒费。
- 基本的編程知識丙唧，雖然這里我是用java寫的，但并不要求懂java觅玻，懂其他語法也行想际，基本流程都是類似，就是語法細節(jié)不同溪厘。
- 了解正則表達式胡本，知道簡單的正則表達式如何寫。
- 基本的數(shù)據(jù)結構知識畸悬，知道有向圖的概念侧甫，知道什么是遞歸和回溯。
有限狀態(tài)機
有限狀態(tài)機(Finite-state machine)蹋宦，也被稱為有限狀態(tài)自動機(finite-state automation)披粟，是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉移和動作等行為的數(shù)學計算模型(From 維基百科 狀態(tài)機) 。 聽起來晦澀難懂冷冗，我用大白話描述一遍守屉，狀態(tài)機其實就是用圖把狀態(tài)和狀態(tài)之間的關系描述出來，狀態(tài)機中的一個狀態(tài)可以在某些給定條件下變成另外一種狀態(tài)蒿辙。舉個很簡單的例子你就懂了拇泛。
比如我今年18歲，我現(xiàn)在就是處于18歲的狀態(tài)须板，如果時間過了一年碰镜，我就變成19歲的狀態(tài)了，再過一年就20了习瑰。當然我20歲時時光倒流2年我又可以回到18歲的狀態(tài)绪颖。這里我們就可以把我的年齡狀態(tài)和時間流逝之間的關系用一個自動機表示出來，如下甜奄。
每個圈代表一個節(jié)點表示一種狀態(tài)柠横，每條有向邊表示一個狀態(tài)到另一個狀態(tài)的轉移條件。上圖中狀態(tài)是我的年齡课兄，邊表示時間正向或者逆向流逝牍氛。
有了狀態(tài)機之后，我們就可以用狀態(tài)機來描述特定的模式烟阐，比如上圖就是年齡隨時間增長的模式搬俊。如果有人說我今年18歲紊扬，1年后就20歲了。照著上面的狀態(tài)機我們來算下唉擂，1年后你才19歲餐屎，你這不是瞎說嗎！ 沒錯玩祟，狀態(tài)機可以來判定某些內容是否符合你狀態(tài)機描述的模式了腹缩。喲，一不小心就快扯到正則表達式上了空扎。
我們這里再引入兩種特殊的狀態(tài)：起始態(tài)和接受態(tài)(終止態(tài))藏鹊，見名知意，不用我過多介紹了吧转锈，起始態(tài)和終止態(tài)的符號如下盘寡。
我們拿狀態(tài)機來做個簡單的字符串匹配。比如我們有個字符串“zsx”撮慨，要判斷其他字符串是否和"zxs"是一致的宴抚，我們可以為"zxs"先建立一個自動機，如下甫煞。
對于任意一個其他的字符串菇曲，我們從起始態(tài)0開始，如果下一個字符能匹配到0后邊的邊上就往后走抚吠，匹配不上就停止常潮，一直重復，如果走到終止態(tài)3說明這個字符串和”zxs“一樣楷力。任意字符串都可以轉化成上述的狀態(tài)機喊式，其實到這里你就知道如何實現(xiàn)一個只支持字符串匹配的正則表達式引擎了，如果想支持更多的正則語義萧朝，我們要做的更多岔留。
狀態(tài)機下的正則表達式
我們再來引入一條特殊的邊，學名叫閉包(emm检柬！看到這些符號我就回想起上學時被數(shù)學支配的恐懼)献联，其實就是一條不需要任何條件就能轉移狀態(tài)的邊。
沒錯何址，就只這條紅邊本邊了里逆，它在正則表達式狀態(tài)機中起著非常重要的連接作用，可以不依賴其他條件直接跳轉狀態(tài)用爪，也就是說在上圖中你可以直接從1到2原押。
有了 閉包的加持，我們就可以開始學如何畫正則表達式文法對應的狀態(tài)機了偎血。
串聯(lián)匹配
首先來看下純字符匹配的自動機诸衔，其實上面已經(jīng)給過一個"zxs"的例子了盯漂，這里再貼一下，其實就是簡單地用字符串在一起而已笨农，如果還有其他字符宠能，就繼續(xù)往后串。
兩個表達式如何傳在一起磁餐，也很簡單，加入我們已經(jīng)有兩個表達式A B對應的狀態(tài)機阿弃，我們只需要將其用串一起就行了诊霹。
并連匹配 (正則表達式中的 |)
正則表達式中的| 標識二選一都可以，比如A|B A能匹配 B也能匹配渣淳，那么A|B就可以表示為下面這樣的狀態(tài)圖脾还。
從0狀態(tài)走A或B都可以到1狀態(tài)，完美的詮釋了A|B語義入愧。
重復匹配(正則表達式中的 ? + *)
正則表達式里有4中表示重復的方式鄙漏，分別是：
- ？重復0-1次
- 重復1次以上
- 重復0次以上
- {n,m} 重復n到m次
我來分別畫下這4種方式如何在狀態(tài)機里表示棺蛛。
重復0-1次 怔蚌？
0狀態(tài)可以通過E也可以依賴直接跳過E到達1狀態(tài)，實現(xiàn)E的0次匹配旁赊。
重復1次以上
0到1后可以再通過跳回來桦踊，就可以實現(xiàn)E的1次以上匹配了。
重復0次以上
仔細看其實就是? +的結合终畅。
匹配指定次數(shù)
這種建圖方式簡單粗暴籍胯，但問題就是如果n和m很大的話，最后生成的狀態(tài)圖也會很大离福。其實可以把指定次數(shù)的匹配做成一條特殊的邊杖狼，可以極大減小圖的大小。
特殊符號(正則表達式中的 . \d \s……)
正則表達式中還支持很多某類的字符妖爷，比如.表示任意非換行符蝶涩，\d標識數(shù)字，[]可以指定字符集…… 絮识，其實這些都和圖的形態(tài)無關子寓，只是某調特殊的邊而已，自己實現(xiàn)的時候可以選擇具體的實現(xiàn)方式笋除，比如后面代碼中我用了策略模式來實現(xiàn)不同的匹配策略斜友，簡化了正則引擎的代碼。
子表達式(正則表達式 () )
子表達可以Tompson算法垃它，其實就是用遞歸去生成()中的子圖鲜屏，然后把子圖拼接到當前圖上面烹看。（什么Tompson說的那么高大上，不就是遞歸嗎Ｂ迨贰）
練習題
來聯(lián)系畫下 a(a|b)* 的狀態(tài)圖惯殊，這里我也給出我畫的，你可以參考下也殖。
代碼實現(xiàn)
建圖
看完上文之后相信你一直知道如果將一個正則表達式轉化為狀態(tài)機的方法了土思，這里我們要將理論轉化為代碼。首先我們要將圖轉化為代碼標識忆嗜，我用State表示一個節(jié)點己儒，其中用了Map<MatchStrategy, List<State>> next表示其后繼節(jié)點，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表示一個完整的圖，其中封裝了對圖的操作绩卤，比如其中就實現(xiàn)了上文中圖串 并連和重復的操作（注意我沒有實現(xiàn){}）途样。
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;
}
}
整個建圖的過程就是依照輸入的字符建立邊和節(jié)點之間的關系，并完成圖的拼接濒憋。
private static NFAGraph regex2nfa(String regex) {
Reader reader = new Reader(regex);
NFAGraph NFAGraph = null;
while (reader.hasNext()) {
char ch = reader.next();
MatchStrategy matchStrategy = 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 '[' : {
matchStrategy = getCharSetMatch(reader);
break;
}
case '^' : {
break;
}
case '$' : {
break;
}
case '.' : {
matchStrategy = new DotMatchStrategy();
break;
}
// 處理特殊占位符
case '\\' : {
char nextCh = reader.next();
switch (nextCh) {
case 'd': {
matchStrategy = new DigitalMatchStrategy(false);
break;
}
case 'D': {
matchStrategy = new DigitalMatchStrategy(true);
break;
}
case 'w': {
matchStrategy = new WMatchStrategy(false);
break;
}
case 'W': {
matchStrategy = new WMatchStrategy(true);
break;
}
case 's': {
matchStrategy = new SpaceMatchStrategy(false);
break;
}
case 'S': {
matchStrategy = new SpaceMatchStrategy(true);
break;
}
// 轉義后的字符匹配
default:{
matchStrategy = new CharMatchStrategy(nextCh);
break;
}
}
break;
}
default : { // 處理普通字符
matchStrategy = new CharMatchStrategy(ch);
break;
}
}
// 表明有某類單字符的匹配
if (matchStrategy != null) {
State start = new State();
State end = new State();
start.addNext(matchStrategy, end);
NFAGraph newNFAGraph = new NFAGraph(start, end);
checkRepeat(reader, newNFAGraph);
if (NFAGraph == null) {
NFAGraph = newNFAGraph;
} else {
NFAGraph.addSeriesGraph(newNFAGraph);
}
}
}
return NFAGraph;
}
private static void checkRepeat(Reader reader, NFAGraph newNFAGraph) {
char nextCh = reader.peak();
switch (nextCh) {
case '*': {
newNFAGraph.repeatStar();
reader.next();
break;
} case '+': {
newNFAGraph.repeatPlus();
reader.next();
break;
} case '?' : {
newNFAGraph.addSToE();
reader.next();
break;
} case '{' : {
//
break;
} default : {
return;
}
}
}
這里我用了設計模式中的策略模式將不同的匹配規(guī)則封裝到不同的MatchStrategy類里何暇，目前我實現(xiàn)了. \d \D \s \S \w \w，具體細節(jié)請參考代碼凛驮。這么設計的好處就是簡化了匹配策略的添加赖晶，比如如果我想加一個\x 只匹配16進制字符，我只需要加個策略類就好了辐烂，不必改很多代碼遏插。
匹配
其實匹配的過程就出從起始態(tài)開始，用輸入作為邊纠修，一直往后走胳嘲，如果能走到終止態(tài)就說明可以匹配，代碼主要依賴于遞歸和回溯扣草，代碼如下了牛。
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;
}
下集預告
還有下集？沒錯辰妙，雖然到這里已經(jīng)是實現(xiàn)了一個基本的正則表達式引擎鹰祸，但距離可用在生產(chǎn)環(huán)境還差很遠，預告如下密浑。
功能完善化
本身上面的引擎對正則語義支持不是很完善蛙婴，后續(xù)我會繼續(xù)完善代碼，有興趣可以收藏下源碼https://github.com/xindoo/regex尔破，但應該不會出一篇新博客了街图，因為原理性的東西都在這里浇衬，剩下的就是只是一些編碼工作 。
DFA引擎
上文只是實現(xiàn)了NFA引擎餐济，NFA的引擎建圖時間復雜度是O(n)耘擂，但匹配一個長度為m的字符串時因為涉及到大量的遞歸和回溯，最壞時間復雜度是O(mn)絮姆。與之對比DFA引擎的建圖時間復雜度O(n^2)醉冤，但匹配時沒有回溯，所以匹配復雜度只有O(m)篙悯，性能差距還是挺大的蚁阳。
DFA引擎實現(xiàn)的大體流程是先構造NFA(本文內容)，然后用子集構造法將NFA轉化為DFA辕近，預計未來我會出一篇博客講解細節(jié)和具體實現(xiàn)。
正則引擎優(yōu)化
首先DFA引擎是可以繼續(xù)優(yōu)化的匿垄，使用Hopcroft算法可以近一步將DFA圖壓縮移宅，更少的狀態(tài)節(jié)點更少的轉移邊可以實現(xiàn)更好的性能。其次椿疗，目前生產(chǎn)級的正則引擎很多都不是單純用NFA或者DFA實現(xiàn)的漏峰，而是二者的結合，不同正則表達式下用不同的引擎可以達到更好的綜合性能届榄，簡單說NFA圖小但要回溯浅乔，DFA不需要回溯但有些情況圖會特別大。敬請期待我后續(xù)博文铝条。
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布靖苇！
