sin(x)

Tag: 正则表达式

正则表达式匹配:运行

测试

为了测试引擎的正确性以及评估效率,测试程序(TestRunner)是必须的。

手工创建一个测试数据集是不现实的,项目的测试程序需要一个正则表达式的集合,对于每一个正则表达式,程序使用Generex根据正则表达式生成指定数量的随机字符串,同时,程序对得到的字符串进行随机替换字符、增加字符、删除字符来获得“错误字符串”的测试数据。程序使用String类的match方法来验证匹配结果的正确性,使用System的nanoTime方法来计时。

运行

NFA

编译得到了NFA,那么可以直接运行NFA(Pattern)。

Continue reading

正则表达式实现:编译

Thompson在他1968年的论文当中介绍了多重状态的模拟。在他的设想当中,NFA由短小精悍的机器码表示,状态的变化只是指令的调用。实际上,Thompson把正则表达式编译成了机器码。四十年之后,计算机速度变快了,机器码运行不再必要。原文使用C语言实现,并且只能编译显式连接的后缀正则表达式,而本文实现了标准的简单正则表达式的编译。

表示

本项目(SimpleRegex)采用Java语言编写,Java的两个重要特性大大方便了正则表达式引擎的实现:

  • Unicode:原生支持Unicode支持,不必额外考虑Unicode字符匹配

  • 垃圾回收:可以免去复杂的NFA链接结构的内存管理

首先需要使用特定的数据结构来表示NFA,我们把NFA表示为关于状态的链接集合。

状态

NFA由状态(AbstractState)链接而成,其中可以分为三类状态:

Continue reading

正则表达式实现:原理

这学期的创新实践尝试自己写一个正则表达式引擎,采用Thompson NFA实现,在网上找到了一篇很棒的文章,于是把它编译(Adapted Translation)过来用作原理解析。

正则表达式

正则表达式是一种描述字符串集合的标准。当一个字符串在一个正则表达式描述的字符串集合当中时,我们认为该字符串匹配了该正则表达式。

最简单的正则表达式就是字符。除了特殊的元字符*+?()|之外,所有的字符匹配自身。为了匹配元字符,需要借助\来转义,例如\+匹配加号。

两个正则表达式可以被串联或者并联,组成新的正则表达式:如果e1匹配s并且e2匹配t,那么e1|e2匹配s或者t,e1e2匹配st。

元字符*,+,和?表示重复操作:e1*匹配任意个匹配e1的字符串;e1+匹配一个以上,而e1?匹配至多一个。

对于各种操作,有着优先级之分,优先级最高的是并联,然后是串联,最后是重复。括号可以用来改变优先级。例如ab|cd相当于(ab)|(cd)ab*相当于a(b*)

Continue reading