专栏首页应用案例不到40行代码构建正则表达式引擎

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

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

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

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

问题描述

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

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

单字符匹配

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

简单举一些用例:

相同长度的字符串匹配

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

上面的代码首先将与进行比较,然后将与进行比较,并继续将与进行比较,直到。如果在某个地方没有匹配成功,那么最终返回的结果就是匹配失败。

我们来举个例子。假设调用,实际上返回的就是。

如果继续分析下去,其实最终的结果就是,这就相当于,所以返回结果就是true!

$字符

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

^字符

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

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

任意位置的匹配

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

但是返回的却是。我们期望让它返回。

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

?字符

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

这里有一些范例:

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

函数需要处理两种情况:

之前的字符没有匹配成功,但是后面所有的文本都和pattern的剩余部分匹配成功了;

之前的字符都匹配成功了,并且其余的文本(这里应该减去一个字符)也和pattern的剩余部分匹配成功了;

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

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

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

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

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

*字符

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

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

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

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

前面的部分没有匹配成功,但是其它文本和pattern中后面的都匹配成功了;

前面的部分匹配成功了,并且其它文本和pattern中后面的也都匹配成功了;

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

重构

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

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

结论

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

本文来自企鹅号 - CSDN大数据媒体

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从零开始学正则

    问题:我怎么才能收到你们公众号平台的推送文章呢? 正则规范 正则表达式的英文是regular expression简称regex。正则表达式就是用事先定义好的一...

    企鹅号小编
  • 死磕支付宝!腾讯信用分来了:送逆天福利

    福利:手机刷机你还在网上大海捞针的寻找方法吗 告诉你个黑科技 关注本公众号后回复刷机+手机型号 系统就会自动为你寻找最适合的刷机教程 省时又省力 12月18日...

    企鹅号小编
  • 你知道自己腾讯信用多少吗?可免押金租房了!

    ? 12月18日,腾讯公司与深圳市住房和建设局举行发布会,宣布深圳市住房租赁交易服务平台正式启动。 据官方介绍,腾讯将通过征信、支付、云计算、人工智能、大数据...

    企鹅号小编
  • Hadoop 多文件输出MultipleOutputFormat

    FileOutputFormat 及其子类产生的文件放在输出目录下。每个 reducer 一个文件并且文件由分区号命名:part-r-00000,part-r-...

    smartsi
  • C语言关于进制转换,补码, 整数的位操作

    tandaxia
  • 全网最易懂的正则表达式教程(4)- 范围

    要想匹配数字,字母,空白是很简单的,因为已经有了对应这些字符集合的元字符,但是如果你想匹配没有预定义元字符的字符集合(比如:元音字母 a,e,i,o,u )

    小菠萝测试笔记
  • 信安 | 红包踩雷,为什么输的总是你?

    有网友在腾讯举报中心公众号留言——“我在微信群里玩抢红包游戏,莫名其妙被举报为赌博,究竟是为啥?” 小助手:Excuse me ?这位网友,你确定你真的只是单纯...

    腾讯技术工程官方号
  • Jenkins 配置GitLab插件和Git插件

    浏览器登录Jenkins Web UI,点击系统管理,再点击管理插件,切换到可选插件,分别搜索GitLab Plugin和Git Plugin,然后点击直接安装...

    羽客
  • Excel简化办公系列之二 | 录制宏快速制作工资条

    本文为CDA作者青菜原创文章,转载请注明来源 编者按:CDA作者青菜将在近期发布「Excel简化办公」系列文章,本文是第二篇;更多精彩请持续关注~ 今天午饭后和...

    CDA数据分析师
  • 手把手教你上手Gephi制作基于共现矩阵的论文作者关系图谱

    共现矩阵的构建算法和该图片的.gexf文件可在我的Github上看到,如果你觉得对你有帮助,欢迎star和fork我:)。

    SL_World

扫码关注云+社区

领取腾讯云代金券