近日，筆者偶然發(fā)現(xiàn)了一篇文章，Rob Pike在C中實(shí)現(xiàn)了一個(gè)簡單的正則表達(dá)式引擎，而Github上的nadrane大神將他的代碼轉(zhuǎn)換為Javascript并添加了測試規(guī)范，以便程序員可以通過此創(chuàng)建一個(gè)簡單的正則表達(dá)式引擎。規(guī)則和解決方案可以在GitHub官網(wǎng)找到(https://github.com/nadrane/build-your-own-regex)，以下是該項(xiàng)目的簡單介紹：

目的

正則表達(dá)式引擎主要將支持以下語法：

目標(biāo)是提供足夠強(qiáng)大的語法來將大部分正則表達(dá)式用例與最少的代碼進(jìn)行匹配。

匹配一個(gè)字符

第一步是編寫一個(gè)函數(shù)，它接受一個(gè)字符模式和一個(gè)字符文本字符串，并返回一個(gè)布爾值來指示它們是否匹配。.(注意，這里有個(gè)點(diǎn))模式被認(rèn)為是通配符，可以匹配任何字符。

以下是示例說明：

匹配固定長度的字符串

現(xiàn)在，我們要添加對更大長度的模式和文本字符串的支持。我們只考慮一個(gè)長度相同的pattern/text對。我碰巧知道該解決方案用遞歸非常適合自然，我們在pattern/text組合的連續(xù)字符對上反復(fù)調(diào)用matchOne。

上面的代碼在整個(gè)pattern/text 對中逐個(gè)字符前進(jìn)，它首先將模式[0]與文本[0]進(jìn)行比較，然后將模式[1]與文本[1]進(jìn)行比較，并繼續(xù)將模式[i]與文本[i]進(jìn)行比較，直到i === pattern.length - 那么我們知道模式不匹配文本。

舉個(gè)例子，假設(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，所以我們有一個(gè)匹配!

$字符

添加對特殊模式字符$的支持，它允許匹配字符串的末尾。該解決方案只需要添加一個(gè)額外的匹配功能。

^字符

添加對特殊模式字符^的支持，它允許匹配一個(gè)字符串的開頭，接下來將介紹一個(gè)稱為searh的新功能。

這個(gè)函數(shù)將成為代碼的新入口。到目前為止，只是在文本開始時(shí)才匹配模式，通過強(qiáng)迫用戶以^來開始這個(gè)模式。但是，如何支持文本中出現(xiàn)的其他模式呢?

匹配從任何地方開始

目前，以下情況返回true：

search("^abc", "abc")

search("^abcd", "abcd")

但是search("bc", "abcd")只會返回undefined，我們希望返回true!

如果用戶開始沒有指定模式匹配文本，并希望在文本內(nèi)每個(gè)可能的起始點(diǎn)搜索該模式。如果模式不以^開始，我們將默認(rèn)這種行為。

?字符

這有個(gè)例子：

第一步是修改匹配來檢測?字符的位置，然后委托給matchQuestion函數(shù)，我們將很快定義它。

matchQuestion需要處理兩種情況：

1、字符?之前的內(nèi)容不匹配，但文本匹配模式的其余部分(在?之后的所有內(nèi)容)。

2、字符?之前的內(nèi)容是匹配的，文本的其余部分(減去1個(gè)匹配的字符)也是匹配的。

如果這兩種情況之一是真的，則matchQuestion可以返回true。

我們來考慮第一種情況，我們?nèi)绾螜z查文本是否匹配除?以外的所有內(nèi)容。換句話說，我們?nèi)绾螜z查字符?前的內(nèi)容，我們從模式中刪除兩個(gè)字符(第一個(gè)字符是?前面的那個(gè)，第二個(gè)是?本身)，并調(diào)用匹配功能。

第二種情況更具挑戰(zhàn)性，但是和以前一樣，它重用了已經(jīng)寫好的函數(shù)：

如果文本[0]與pattern [0]匹配，并且文本的其余部分(減去matchOne匹配的部分)與模式的其余部分匹配，那么請注意，我們可以像這樣重寫代碼：

關(guān)于后一種方法我喜歡的一件事是，boolean OR使得它清楚地表明兩種情況，其中任何一種可能都是正確的。

*字符

希望能夠匹配 0次或多次出現(xiàn)在*之前的字符。

所有這些都應(yīng)該返回true。

與我們在支持時(shí)所做的相似，我們想要在匹配函數(shù)中委托matchStar函數(shù)：

matchStar和matchQuestion一樣，也需要處理兩種情況：

1、 *之前的字符不匹配，但文本匹配模式的其余部分(*之后的所有內(nèi)容)。

2、*之前的字符匹配一次或多次，其余文本匹配模式的其余部分。

由于有兩種情況導(dǎo)致匹配(0次或多次匹配)，我們知道m(xù)atchStar可以用一個(gè)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)在希望匹配的模式之前。

注意：

這個(gè)代碼有一個(gè)小錯(cuò)誤，但作者選擇忽略，不考慮文本是空字符串的情況。目前當(dāng)text ===''時(shí)，text.split(“”)將返回，并且不會適當(dāng)?shù)卣{(diào)用match。

如果你感興趣，歡迎到Github中查看源代碼并使用。