不到40行代码构建正则表达式引擎

末蓝、 2022-06-03 03:50 182阅读 0赞

原文：Build a Regex Engine in Less than 40 Lines of Code
    作者：Nick Drane
    翻译：Diwei

译者注：如何用不到40行的代码构建一个正则表达式引擎？作者在本文就将他本人的解决思路记录了下来，如果你也想挑战，不妨借鉴一下作者的思路，说不定你写的代码可能不到30行。以下为译文。

无意之间我发现了一篇文章，Rob Pike用C语言实现了一个正则表达式引擎的模型。于是我也尝试用Javascript写一个，并且增加了测试规范。测试规范和解决方案都放在了GitHub仓库上面。本文将重点介绍解决方案。  
问题描述

正则表达式引擎将支持以下语法：

最终目标是用最少的代码提供最强大的功能，从而满足上述正则表达式用例。  
单字符匹配

第一步是编写一个函数，该函数有两个入参，返回值是一个布尔类型，表示匹配结果。.表示通配模式，可以匹配任意字符。

简单举一些用例：

matchOne(‘a’, ‘a’) -> true

matchOne(‘.’, ‘z’) -> true

matchOne(”, ‘h’) -> true

matchOne(‘a’, ‘b’) -> false

matchOne(‘p’, ”) -> false

function matchOne(pattern, text) \{  
if (!pattern) return true // Any text matches an empty pattern  
if (!text) return false // If the pattern is defined but the text is empty, there cannot be a match  
if (pattern === “.”) return true // Any inputted text matches the wildcard  
return pattern === text  
\}

1
    2
    3
    4
    5
    6
    7

相同长度的字符串匹配

现在需要增加参数的长度，并且暂时只考虑pattern和string长度相同的情况。根据以前的经验，我很自然的认为这种情况非常适合用递归来解决。 我们只需要反复调用matchOne函数就可以了。

function match(pattern, text) \{  
if (pattern === “”) return true // Our base case - if the pattern is empty, any inputted text is a match  
else return matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(1), text.slice(1))  
\}

1
    2
    3
    4
    5

上面的代码首先将pattern\[0\]与text\[0\]进行比较，然后将pattern\[1\]与text\[1\]进行比较，并继续将pattern\[i\]与text\[i\]进行比较，直到i === pattern.length - 1。如果在某个地方没有匹配成功，那么最终返回的结果就是匹配失败。

我们来举个例子。假设调用match（’a.c’，’abc’），实际上返回的就是matchOne（’a’，’a’）&& match（’.c’，’bc’）。

如果继续分析下去，其实最终的结果就是matchOne（’a’，’a’）&& matchOne（’.’，’b’）&& matchOne（’c’，’c’）&& match（”“，”“） ，这就相当于true && true && true && true，所以返回结果就是true！  
$字符

接下来增加特殊字符$的支持，它可以匹配字符串后面的所有字符。要想实现该功能，只需要在上一步的match函数中增加一个额外基本情况的判断就可以了。

function match(pattern, text) \{  
if (pattern === “”) return true  
if (pattern === “$” && text === “”) return true  
else return matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(1), text.slice(1))  
\}

1
    2
    3
    4
    5
    6

^字符

让我们添加对特殊模式字符^的支持，它允许匹配字符串的开头。这里我将介绍一个新的函数–search。

function search(pattern, text) \{  
if (pattern\[0\] === “^”) \{  
return match(pattern.slice(1), text)  
\}  
\}

1
    2
    3
    4
    5
    6

这个函数将成为代码的新入口。到目前为止只是在文本开始时才开始匹配。现在只是通过强迫用户以^来开始。但是如何支持文本中出现的任何模式呢？  
任意位置的匹配

截止到目前为止，下面的表达式将会返回true。

search(“^abc”, “abc”)

search(“^abcd”, “abcd”)

但是search(“bc”, “abcd”)返回的却是undefined。我们期望让它返回true。

如果用户没有指明要从第一个字符开始就要匹配，那么我们希望在文本内的每个可能的起始点进行搜索。这是默认的处理规则，除非pattern是以^开始。

function search(pattern, text) \{  
if (pattern\[0\] === “^”) \{  
return match(pattern.slice(1), text)  
\} else \{  
// This code will run match(pattern, text.slice(index)) on every index of the text.  
// This means that we test the pattern against every starting point of the text.  
return text.split(“”).some((\_, index) => \{  
return match(pattern, text.slice(index))  
\})  
\}  
\}

1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

?字符

使用?的话，那么在?前面的0个或者1个字符可以进行匹配。

这里有一些范例：

search(“ab?c”, “ac”) -> true

search(“ab?c”, “abc”) -> true

search(“a?b?c?”, “abc”) -> true

search(“a?b?c?”, “”) -> true

第一步是修改match函数，当检测到?字符出现以后就开始调用matchQuestion函数，matchQuestion函数的定义将会在下面的内容看到。

function match(pattern, text) \{  
if (pattern === “”) \{  
return true  
\} else if (pattern === “$” && text === “”) \{  
return true  
// Notice that we are looking at pattern\[1\] instead of pattern\[0\].  
// pattern\[0\] is the character to match 0 or 1 of.  
\} else if (pattern\[1\] === “?”) \{  
return matchQuestion(pattern, text)  
\} else \{  
return matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(1), text.slice(1))  
\}  
\}

1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

matchQuestion函数需要处理两种情况：

?之前的字符没有匹配成功，但是?后面所有的文本都和pattern的剩余部分匹配成功了；
    ?之前的字符都匹配成功了，并且其余的文本（这里应该减去一个字符）也和pattern的剩余部分匹配成功了；

上面两种情况中只要满足一种，那么matchQuestion函数就会返回true。

让我们先考虑第一种情况。如果pattern中的文本除了\_?不一样以外，其它都能匹配成功，这种情况我们怎么去检查呢？换句话说，如果?前面的字符只出现了0次，这种情况我们怎么去检查呢？我们从pattern剔除掉2个字符（第一个字符就是?前面的哪个，第二个字符就是?本身），然后再调用match函数。

function matchQuestion(pattern, text) \{  
return match(pattern.slice(2), text);  
\}

1
    2
    3
    4

第二种情况更具挑战性，但是和上面介绍的一样，它还是重用了之前已经写好的函数。

function matchQuestion(pattern, text) \{  
if (matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(2), text.slice(1))) \{  
return true;  
\} else \{  
return match(pattern.slice(2), text);  
\}  
\}

1
    2
    3
    4
    5
    6
    7
    8

如果text\[0\]跟pattern\[0\]匹配上了，而且其它的文本和pattern中剩余的也能匹配上，那么我们就成功了。注意，代码我们也可以这么写：

function matchQuestion(pattern, text) \{  
return (matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(2), text.slice(1))) || match(pattern.slice(2), text);  
\}

1
    2
    3
    4

我更喜欢后面一个方法的原因是因为它明确地指出了有两种情况，只要满足其中一种，那么返回的结果就是true。  
\*字符

我们希望能够匹配\*前面0个或多个字符。

下面这些表达式的返回结果都应该是true。

search(“a\*”, “”)

search(“a\*”, “aaaaaaa”)

search(“a\*b”, “aaaaaaab”)

这个跟?的情况很相似，我们在match函数里面再增加一个matchStar方法。

function match(pattern, text) \{  
if (pattern === “”) \{  
return true  
\} else if (pattern === “$” && text === “”) \{  
return true  
\} else if (pattern\[1\] === “?”) \{  
return matchQuestion(pattern, text)  
\} else if (pattern\[1\] === “\*”) \{  
return matchStar(pattern, text)  
\} else \{  
return matchOne(pattern\[0\], text\[0\]) && match(pattern.slice(1), text.slice(1))  
\}  
\}

1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

matchStar和matchQuestion一样，也要处理两种情况：

*前面的部分没有匹配成功，但是其它文本和pattern中*后面的都匹配成功了；
    *前面的部分匹配成功了，并且其它文本和pattern中*后面的也都匹配成功了；

由于这两种情况都能决定匹配的结果，因此我们知道matchStar可以用布尔类型OR来实现。此外，matchStar的情况1与matchQuestion的情况1完全相同，因此同样也可以使用match（pattern.slice（2），text）进行实现。这意味着我们只需要制定满足情况2的表达式。

function matchStar(pattern, text) \{  
return (matchOne(pattern\[0\], text\[0\]) && match(pattern, text.slice(1))) || match(pattern.slice(2), text);  
\}

1
    2
    3
    4

重构

现在我们可以回过头来，对search函数进行简化，而且正好可以将我从Peter Norvig写的类里面学到的一个技巧应用上。

function search(pattern, text) \{  
if (pattern\[0\] === “^”) \{  
return match(pattern.slice(1), text)  
\} else \{  
return match(“.\*” + pattern, text)  
\}  
\}

1
    2
    3
    4
    5
    6
    7
    8

我们使用*字符本身来允许pattern中字符串可以出现在任何地方。前面的.*表示在pattern前面出现了任何数量的任何字符，我们也希望能匹配成功。  
结论

功能如此强大，但是代码却如此简洁明了，这真是一件很了不起的事情。完整的源代码可以再GitHub仓库中找到。

PS：推荐一个容器技术线上直播，讲师来自腾讯、华为、思科、58同城、蘑菇街、当当等6位一线专家，议题涵盖容器云、微服务、servicemesh等最新实践，欢迎报名参加。