不到40行JS代码如何构建正则表达式引擎?

2017-12-07 o0希希0o

近日,笔者偶然发现了一篇文章,Rob Pike在C中实现了一个简单的正则表达式引擎,而Github上的nadrane大神将他的代码转换为Javascript并添加了测试规范,以便程序员可以通过此创建一个简单的正则表达式引擎。规则和解决方案可以在GitHub官网找到(https://github.com/nadrane/build-your-own-regex),以下是该项目的简单介绍:

目的

正则表达式引擎主要将支持以下语法:

目标是提供足够强大的语法来将大部分正则表达式用例与最少的代码进行匹配。

匹配一个字符

第一步是编写一个函数,它接受一个字符模式和一个字符文本字符串,并返回一个布尔值来指示它们是否匹配。.(注意,这里有个点)模式被认为是通配符,可以匹配任何字符。

以下是示例说明:

匹配固定长度的字符串

现在,我们要添加对更大长度的模式和文本字符串的支持。我们只考虑一个长度相同的pattern/text对。我碰巧知道该解决方案用递归非常适合自然,我们在pattern/text组合的连续字符对上反复调用matchOne。

上面的代码在整个pattern/text 对中逐个字符前进,它首先将模式[0]与文本[0]进行比较,然后将模式[1]与文本[1]进行比较,并继续将模式[i]与文本[i]进行比较,直到i === pattern.length - 那么我们知道模式不匹配文本。

举个例子,假设调用match('a.c','abc'),它返回matchOne('a','a')&& match('。c','bc')。

如果继续评估这些函数,可以得到matchOne('a','a')&& matchOne('。','b')&& matchOne('c','c')&& match(“”,“”) ,这只是true && true && true && true,所以我们有一个匹配!

$字符

添加对特殊模式字符$的支持,它允许匹配字符串的末尾。该解决方案只需要添加一个额外的匹配功能。

^字符

添加对特殊模式字符^的支持,它允许匹配一个字符串的开头,接下来将介绍一个称为searh的新功能。

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

匹配从任何地方开始

目前,以下情况返回true:

search("^abc", "abc")

search("^abcd", "abcd")

但是search("bc", "abcd")只会返回undefined,我们希望返回true!

如果用户开始没有指定模式匹配文本,并希望在文本内每个可能的起始点搜索该模式。如果模式不以^开始,我们将默认这种行为。

?字符

这有个例子:

第一步是修改匹配来检测?字符的位置,然后委托给matchQuestion函数,我们将很快定义它。

matchQuestion需要处理两种情况:

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

2、字符?之前的内容是匹配的,文本的其余部分(减去1个匹配的字符)也是匹配的。

如果这两种情况之一是真的,则matchQuestion可以返回true。

我们来考虑第一种情况,我们如何检查文本是否匹配除?以外的所有内容。换句话说,我们如何检查字符?前的内容,我们从模式中删除两个字符(第一个字符是?前面的那个,第二个是?本身),并调用匹配功能。

第二种情况更具挑战性,但是和以前一样,它重用了已经写好的函数:

如果文本[0]与pattern [0]匹配,并且文本的其余部分(减去matchOne匹配的部分)与模式的其余部分匹配,那么请注意,我们可以像这样重写代码:

关于后一种方法我喜欢的一件事是,boolean OR使得它清楚地表明两种情况,其中任何一种可能都是正确的。

*字符

希望能够匹配 0次或多次出现在*之前的字符。

所有这些都应该返回true。

与我们在支持时所做的相似,我们想要在匹配函数中委托matchStar函数:

matchStar和matchQuestion一样,也需要处理两种情况:

1、 *之前的字符不匹配,但文本匹配模式的其余部分(*之后的所有内容)。

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

由于有两种情况导致匹配(0次或多次匹配),我们知道matchStar可以用一个booleanOR来实现。此外,matchStar的情况1与matchQuestion的情况1完全相同,并且可以使用match(pattern.slice(2),text)相同地实现。这意味着只需要制定满足案例2的表达式。

重构

现在可以回过头来简化search:

使用*字符本身允许模式出现在字符串中的任何地方。前面的*表示任何数量的任何字符都可以出现在希望匹配的模式之前。

注意:

这个代码有一个小错误,但作者选择忽略,不考虑文本是空字符串的情况。目前当text ===''时,text.split(“”)将返回,并且不会适当地调用match。

如果你感兴趣,欢迎到Github中查看源代码并使用。


用户评论
开源开发学习小组列表