专栏首页CSDN技术头条不到40行代码构建正则表达式引擎

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

原文: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 }

相同长度的字符串匹配

现在需要增加参数的长度,并且暂时只考虑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)) 
}

上面的代码首先将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)) 
}

^字符

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

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

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

任意位置的匹配

截止到目前为止,下面的表达式将会返回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))     
        })   
    } 
}

?字符

使用?的话,那么在?前面的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))
   }
}

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

  1. ?之前的字符没有匹配成功,但是?后面所有的文本都和pattern的剩余部分匹配成功了;
  2. ?之前的字符都匹配成功了,并且其余的文本(这里应该减去一个字符)也和pattern的剩余部分匹配成功了;

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

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

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

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

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);   
   }
}

如果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); 
}

我更喜欢后面一个方法的原因是因为它明确地指出了有两种情况,只要满足其中一种,那么返回的结果就是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))
   }
}

matchStarmatchQuestion一样,也要处理两种情况:

  1. *前面的部分没有匹配成功,但是其它文本和pattern中*后面的都匹配成功了;
  2. *前面的部分匹配成功了,并且其它文本和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); 
}

重构

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

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

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

结论

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

本文分享自微信公众号 - CSDN技术头条(CSDN_Tech),作者:Nick Drane

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-12-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于HBase的大数据存储的应用场景分析

    本文结合两个实战场景就基于 HBase 的大数据存储做了简单的分析,并对 HBase 的原理做了简单的阐述。

    CSDN技术头条
  • 资源控制在大数据和云计算平台中的应用

    本文针对大数据平台中资源控制这个层面来详细介绍资源控制在不同操作系统上的具体技术实现,以及大数据平台和资源控制的集成。

    CSDN技术头条
  • OpenStack实战系列:漫谈Neutron 的架构

    一.前言 由于OpenStack Neutron项目本身的高度复杂性和抽象性,加之作为一名初学者,其理解能力有限。因此这里,阐述的仅是凤毛麟角而已,其目的是帮助...

    CSDN技术头条
  • Logback配置

    DH镔
  • 测序深度的计算,你真的掌握了吗

    第一列是染色体名称,第二列是染色体上的坐标,第三列是对应的测序深度。原本以为计算测序深度就是这么轻松的一件事,但是在比较不同方法的输出结果时,却发现部分区域sa...

    生信修炼手册
  • 一文聊透 Dubbo 优雅停机

    一年之前,我曾经写过一篇《研究优雅停机时的一点思考》,主要介绍了 kill -9,kill -15 两个 Linux 指令的含义,并且针对性的聊到了 Sprin...

    kirito-moe
  • eeglab中文教程系列(14)-绘制独立成分ERP贡献

    要完成该操作,必须保证已加载数据和电极位置数据,同时还要对数据进行提取epoch,并对数据进行ICA处理,操作如下:

    脑机接口社区
  • eeglab中文教程系列(14)-绘制独立成分ERP贡献

    本教程为脑机学习者Rose发表于公众号:脑机接口社区(微信号:Brain_Computer),QQ交流群:903290195

    脑机接口社区
  • 如何自定义 Nginx日志?

    为什么要自定义nginx日志? 这里有个例子。示例中希望 nginx 能够记录 php-fpm (上游服务器)执行程序所花费的时间,以便为优化服务器端(程序)响...

    用户1560186
  • 「镁客晚报」卖不动!苹果推新政刺激iPhone 6s印度市场销量

    镁客网

扫码关注云+社区

领取腾讯云代金券