筆者偶然發(fā)現(xiàn)了一篇文章，Rob Pike在C中實(shí)現(xiàn)了一個簡單的正則表達(dá)式引擎，而Github上的nadrane大神將他的代碼轉(zhuǎn)換為Java并添加了測試規(guī)范，以便程序員可以通過此創(chuàng)建一個簡單的正則表達(dá)式引擎。規(guī)則和解決方案可以在GitHub官網(wǎng)找到(https://github.com/nadrane/build-your-own-regex)，以下是該項(xiàng)目的簡單介紹：
目的
正則表達(dá)式引擎主要將支持以下語法：
目標(biāo)是提供足夠強(qiáng)大的語法來將大部分正則表達(dá)式用例與最少的代碼進(jìn)行匹配。
匹配一個字符
第一步是編寫一個函數(shù)，它接受一個字符模式和一個字符文本字符串，并返回一個布爾值來指示它們是否匹配。.(注意，這里有個點(diǎn))模式被認(rèn)為是通配符，可以匹配任何字符。
以下是示例說明：
匹配固定長度的字符串
現(xiàn)在，我們要添加對更大長度的模式和文本字符串的支持。我們只考慮一個長度相同的pattern/text對。我碰巧知道該解決方案用遞歸非常適合自然，我們在pattern/text組合的連續(xù)字符對上反復(fù)調(diào)用matchOne。
上面的代碼在整個pattern/text 對中逐個字符前進(jìn)，它首先將模式[0]與文本[0]進(jìn)行比較，然后將模式[1]與文本[1]進(jìn)行比較，并繼續(xù)將模式[i]與文本[i]進(jìn)行比較，直到i === pattern.length - 那么我們知道模式不匹配文本。
舉個例子，假設(shè)調(diào)用match('a.c'，'abc')，它返回matchOne('a'，'a')&& match('。c'，'bc')。
如果繼續(xù)評估這些函數(shù)，可以得到matchOne('a'，'a')&& matchOne('。'，'b')&& matchOne('c'，'c')&& match(“”，“”) ，這只是true && true && true && true，所以我們有一個匹配!
$字符
添加對特殊模式字符$的支持，它允許匹配字符串的末尾。該解決方案只需要添加一個額外的匹配功能。
^字符
添加對特殊模式字符^的支持，它允許匹配一個字符串的開頭，接下來將介紹一個稱為searh的新功能。
這個函數(shù)將成為代碼的新入口。到目前為止，只是在文本開始時才匹配模式，通過強(qiáng)迫用戶以^來開始這個模式。但是，如何支持文本中出現(xiàn)的其他模式呢?
匹配從任何地方開始
目前，以下情況返回true：
search("^abc", "abc")
search("^abcd", "abcd")
但是search("bc", "abcd")只會返回undefined，我們希望返回true!
如果用戶開始沒有指定模式匹配文本，并希望在文本內(nèi)每個可能的起始點(diǎn)搜索該模式。如果模式不以^開始，我們將默認(rèn)這種行為。
?字符
這有個例子：
第一步是修改匹配來檢測?字符的位置，然后委托給matchQuestion函數(shù)，我們將很快定義它。
matchQuestion需要處理兩種情況：
1、字符?之前的內(nèi)容不匹配，但文本匹配模式的其余部分(在?之后的所有內(nèi)容)。
2、字符?之前的內(nèi)容是匹配的，文本的其余部分(減去1個匹配的字符)也是匹配的。
如果這兩種情況之一是真的，則matchQuestion可以返回true。
我們來考慮第一種情況，我們?nèi)绾螜z查文本是否匹配除?以外的所有內(nèi)容。換句話說，我們?nèi)绾螜z查字符?前的內(nèi)容，我們從模式中刪除兩個字符(第一個字符是?前面的那個，第二個是?本身)，并調(diào)用匹配功能。
第二種情況更具挑戰(zhàn)性，但是和以前一樣，它重用了已經(jīng)寫好的函數(shù)：
如果文本[0]與pattern [0]匹配，并且文本的其余部分(減去matchOne匹配的部分)與模式的其余部分匹配，那么請注意，我們可以像這樣重寫代碼：
關(guān)于后一種方法我喜歡的一件事是，boolean OR使得它清楚地表明兩種情況，其中任何一種可能都是正確的。
*字符
希望能夠匹配 0次或多次出現(xiàn)在*之前的字符。
所有這些都應(yīng)該返回true。
與我們在支持時所做的相似，我們想要在匹配函數(shù)中委托matchStar函數(shù)：
matchStar和matchQuestion一樣，也需要處理兩種情況：
1、 *之前的字符不匹配，但文本匹配模式的其余部分(*之后的所有內(nèi)容)。
2、*之前的字符匹配一次或多次，其余文本匹配模式的其余部分。
由于有兩種情況導(dǎo)致匹配(0次或多次匹配)，我們知道m(xù)atchStar可以用一個booleanOR來實(shí)現(xiàn)。此外，matchStar的情況1與matchQuestion的情況1完全相同，并且可以使用match(pattern.slice(2)，text)相同地實(shí)現(xiàn)。這意味著只需要制定滿足案例2的表達(dá)式。
重構(gòu)
現(xiàn)在可以回過頭來簡化search：
使用*字符本身允許模式出現(xiàn)在字符串中的任何地方。前面的*表示任何數(shù)量的任何字符都可以出現(xiàn)在希望匹配的模式之前。
注意：
這個代碼有一個小錯誤，但作者選擇忽略，不考慮文本是空字符串的情況。目前當(dāng)text ===''時，text.split(“”)將返回[]，并且不會適當(dāng)?shù)卣{(diào)用match。
如果你感興趣，歡迎到Github中查看源代碼并使用。
