2019獨角獸企業(yè)重金招聘Python工程師標準>>>

大概和我不以程序員為職業(yè)有關(guān)吧，我本人是比較喜歡算法的那種，當然是比不了科班出身的。

比如我就寫過很多版本的算術(shù)表達式解析器，優(yōu)先級堆棧的；二叉樹的；分治策略的；修正計算順序的……

正則表達式兩個我也寫過兩個，一個采用的回溯算法，另一個則是二叉樹版本的，雖然這倆倒是都能用吧，但是對分組的處理（分組是采用遞歸調(diào)用的方法實現(xiàn)的，相當于另一個正則表達式）實在是不太好，這個缺點導致很多時候搜索的結(jié)果會遺漏很多，而二叉樹版本的還有個缺點是選擇操作“|”只能獲得第一個匹配…………

就效果看，這倆都是殘次品。

后來，我在vczh的博客里看到了他的一個科普貼子，在那里面，我才了解到還有有限自動機這種方法。

之后我花了不少時間去思考，因為總覺得這個方法太麻煩了，斷斷續(xù)續(xù)有2-3個月吧，想來想去也沒想出什么更好的法子，最后還是覺得只有用有限自動機才合適。

不過多少我還是做了些修改的，倒不是為了效率，是為了減少打字量……

主要修改如下：

（1）不每個字符轉(zhuǎn)移一次狀態(tài)，而是盡可能的把連續(xù)的字符作為一個整體進行比對。

（2）不弄什么字母分組表，數(shù)據(jù)結(jié)構(gòu)就使用指針鏈表，節(jié)省工作量

（3）“{a,b}”這種有次數(shù)限定的重復，vczh是采用復制節(jié)點實現(xiàn)的，我采用增加狀態(tài)邊來解決（效率會下降）

（4）分組命名，向前向后預查這些花哨而實用的功能，俺就丟了

那么，整體上看，正則表達式引擎的設(shè)計我就劃分為如下幾個步驟：

1）對規(guī)則字符串做預處理，主要是換行這類要使用轉(zhuǎn)義符的字符，這個預處理可以把這些字符還原

2）將規(guī)則字符串進行劃分，修正成操作符、操作數(shù)的列表形式

3）對這個列表進行處理，獲得NFA狀態(tài)轉(zhuǎn)移圖

4）將NFA狀態(tài)轉(zhuǎn)移圖里的ε邊消去，減少狀態(tài)轉(zhuǎn)移數(shù)

5）利用得到的狀態(tài)轉(zhuǎn)移圖，對字符串進行匹配

第一步很容易解決，無非就是找到'\'，然后將后跟't'、'n'、'r'等字符的修正為相應(yīng)的制表、換行……

第二步也相對簡單，無非是識別幾個操作符:

'*'、'+'、'?'、'*?'、'+?'、'??'、'('、'(:'、')'、'|'、'['、']'、'{'、'}'

比較特殊的是：

因為把連續(xù)的字符看做一個整體，所以在后跟重復或者可選運算符時，要檢查一下是否需要斷開字符串；

'['后面要一直讀取到前面不是'\'的']'，期間不作分析，結(jié)果作為一個整體

'{'后面有'{a}'、'{a,}'、'{,a}'、'{a,b}'這幾種形式，同樣是讀取為一個整體

還有一個隱藏的操作符，它的作用是將兩個操作數(shù)連接起來，類似算術(shù)里的“*”，關(guān)于它另有介紹[*]

如此一來，列表里的成員記錄的內(nèi)容就會有好幾種，python里這不算啥，C++里就麻煩一些，我采用的是struct和union來回嵌套+標志字節(jié)的辦法來處理這個問題。

（如果使用正則表達式這一步非常輕松，可是如果用了就真成了笑話了）

第三步見下一帖

[*]被隱藏了的“連接”運算符，比如“ab[cd]”這個字符串，分析后的兩個元素“ab”和“[cd]”正是通過這個操作符連接的。這個隱藏運算符我是用后面的Operator類的一個補足函數(shù)來填充修復的，不然就得另外寫一個函數(shù)了。

轉(zhuǎn)載于:https://my.oschina.net/liudiwu/blog/111327

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的从头开始，搭建一个正则表达式引擎（一）整体构架、预处理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。