探索Ruby正则表达式算法(译)

来源:Exploring Ruby’s Regular Expression Algorithm(2012)

ps. 业余翻译的,求轻拍。有什么问题可以直接指出。

大家都熟悉正则表达式,它是开发者的“瑞士军刀”。不管你想查找哪种信息,解析哪些字符串,总有一种正则表达式适合你。事实上,你可能用过很久的ruby所使用的正则表达式了——正则表达式已经被集成到几乎所有主要的语言中好多年了:Perl、javascript、PHP、Java等等。ruby支持是在90年代中期,而正则表达式是在60年代中期发明的,早了30年。

但是正则表达式是怎样工作的呢?如果你对正则表达式引擎后面的计算机原理感兴趣的话,可以读一下这三篇Russ Cox写的极棒的文章:

在这里我不打算重复Russ的内容。但是我准备在第二篇文章中快速的解释一下ruby所使用的“无递归的回溯实现”, 这意味着它可能也会像perl正则表达式一下慢吞吞。就是说,这意味着Ruby并没有使用目前最主流的正则表达式实现方法——Thompson NFA,也就是Russ第一篇文章中所描述的。

今天我们细看一下Oniguruma,也就是Ruby所使用的正则表达式引擎。我们使用一些插图来表现一些简单的正则示例,以此来弄清楚在使用正则的时候是Ruby内部是如何工作的——它比你想象的要复杂多了。

Oniguruma

MRI Ruby从1.9开始引入开源的正则表达式c库“Oniguruma”,这个引擎也使用在PHP中。除了支持基本的正则表达式特性以外,Oniguruma对宽字符支持也非常好,比如日文。

Oniguruma解释一个正则表达式会分为以下几个步骤:

第一步,Oniguruma读取正则表达式,抽取符号并转化成为一棵包含语法节点的树结构——也就是抽象语法树(AST)。这和Ruby自己解释Ruby代码很相似。事实上,你可以认为Oniguruma正则引擎是Ruby内部的第二个编程语言绑定。当你在Ruby中使用正则表达式的时候,的确是写了第二种语言,这个语言的语法和Ruby完全不同。解释完表达式以后,Oniguruma把它编译到后面我们将会讲到的虚拟机中。这个虚拟机是通过状态机实现的,Russ Cox在他的文章中有介绍。

执行完正则表达式以后,Oniguruma虚拟机会执行搜索,对目标字符串进行匹配。

这周为了弄清楚Oniguruma的工作原理和它和Russ Cox解释的算法的区别,我在重新添加了几个标识后重新编译了Ruby2.0:ONIG_DEBUG_COMPILE、ONIG_DEBUG_MATCH。设置这几个标志的目的是可以在Oniguruma执行的时候方便查看debug输出,这样可以看到Oniguruma VM编译出来的结果。以下就是我发现的内容:

例1:简单子串匹配

这里有个简单的Ruby代码,在目标串中查找brown:

如果使用我的Ruby修改版,可以看到额外的调试输出(比我在这里贴出来的更多):

关键在于这里“0:[exact5:brown] 6:[end]”——这行打印出了两句Oniguruma VM编译/brown/产生的指令。这个正则看起来是这样的:

来看一下这个/brown/产生的状态机的图示:

  • exact5: brown检查目标串在当前位置是否出现5个字符“brown",然后
  • end  代表搜索结束;它返回匹配到的字符串后结束。

当运行正则查询的时候Oniguruma VM产生指令和分析目标串是同时进行的。让我们看看上面的例子是怎样执行的,首先 exact5:brown 指令针对包含brown的目标串执行:

Oniguruma怎么知道从哪里开始呢?原来它包含了一个优化器,这个优化器决定从(目标串和第一个VM指令的)哪里开始正则搜索。可以从上面的调试中看到“optimize: EXACT_BM… exact: [brown]: length: 5… start offset: 10”。在这个例子中,从Oniguruma知道要开始查找字符串”brown“开始,它就跳到第一次出现”brown“的地方。虽然吧,看起来我好像在忽悠着你,但是事实上吧,这只是一个简单的优化而已,而且这个优化在正则搜索中很常见。

然后,Oniguruma开始执行“exact5:brown”以检查这五个字符是否符合要求。发现符合的时候,Oniguruma就通过了这条指令,开始执行下一条VM指令:

现在,Oniguruma执行end指令——字如其意,也就是劳动结束了(真是辛苦而又充实的一天啊。。)。到了end指令,执行结束,虚拟机宣告匹配成功并返回匹配到的子串。

例2:或匹配

我们来个高端点的例子——我想匹配“black”或者“brown”

跑起来~

现在呢,这里是关键:“0:[push:(11)] 5:[exact5:black] 11:[jump:(6)] 16:[exact5:brown] 22:[end]”.。这个VM执行/black|brown/正则搜索:

 

小复杂啊……首先,你可以看到优化器只查找字符“b”:“optimize: EXACT exact: [b]: length: 1”。因为“black”和“brown”开头相同的子串都是“b”。

好,我们看一下这个小复杂的正则程序:

push指令在第一次发现b的位置先执行。push指令目的是把另外一个指令位置和相应的目标串位置推到一个叫做“Backtrack Stack”(姑且先叫“回溯栈”好了)的地方:

回溯栈就是Oniguruma的工作核心部分。Oniguruma可以用它保持多个匹配路径——因为有时一条指令路径没办法做到直接匹配。好了,继续这个例子。

现在开始对目标串执行“exact5:black”指令,但是其实是brown出现在了目标串里。这意味着这条指令没有成功匹配到,也就是说这条指令失败了。但是失败返回Ruby之前,Oniguruma会检查回溯栈里面是否有其他执行路径。在这个例子中,"exact5.brown"还在里面等着——/black|brown/里面OR的第二种情况.。现在Oniguruma把“exact5.brown”指令位置和目标串位置弹出栈执行:

匹配成功,所以Oniguruma通过这5个字符后转到下一条指令:

Oniguruma又到了end指令,把匹配到的子串返回给Ruby。

例3:任意串(*)

最后一个例子,当然跑起这个小片段的时候看看发生了什么:

这意思是要匹配到“brown”或者后面跟着什么东西都可以的子串,直到这一行结束。调试输出如下:

这是新的状态机:

这次能看到新的Oniguruma VM指令:anychar*。估计你能猜到,这是“.* ”对应的指令。一步步跟踪一下,看看发生了什么:

又一次,我们从目标串的第10个位置开始,也就是“brown”开始出现的地方。匹配成功,Oniguruma通过了“brown”后执行下一条指令:

来到“anychar*”。它的工作包含以下几点:

  • 第一,他匹配任何字符,所以它总是向前执行的。
  • 但是呢,这是个循环,下一个指令又是它,Oniguruma就又回来继续执行“anychar*”,当然目标串的位置是下一个字符
  • 它会把当前字符和下个指令推入栈,end 指令:

现在Oniguruma简单的在剩下的子串中迭代,重复以上步骤直到一下字符都匹配完:“brown fox jumps over the lazy dog.”,他重复的保存end指令到栈里面:

又一次:

最终,多次迭代后Oniguruma来到句子的末尾:

”anychar*“在这里自然是失败了,因为没啥字符好给他匹配的了。然后呢?然后就如上面例子中那样,从这个点开始从栈中弹出下一条指令,开始下一个查询。这个例子呢,他会弹出“end”指令和匹配到的目标字符的位置(因为每次入栈的都是end和目标字符位置),也就是说Oniguruma会返回从匹配成功开始到结束所有的字符串给Ruby:“brown fox jumps over the lazy dog.”。

但是为什么“anychar*”要把每次匹配到的单个字符的位置入栈呢?那是因为如果在“.*”后面还有其他的匹配,或者“.*”只是一个子匹配,就没法确定最终用那个位置就作为匹配的返回的。Oniguruma需要尝试所有的结果。这个例子中匹配到了字符串末尾,所以也就不需要弹出栈后执行更多的指令了。

有意思的是,如果你在“.*”后面有其他指令——比如你查找/.*brown/,Oniguruma就不会使用“anychar*”。取而代之的是“anychar*-peek-next:b”。这个指令跑起来和“anychar*”差不多,不同的是它不是把所有的字符位置都推到栈里,而是只把匹配到的字符位置推进去——这个例子中就是“b”。这是因为Oniguruma知道下个位置的字符肯定是“b.”。

一个问题

我之前说过当我们给出一个有问题的匹配的时候,Ruby表现出和Perl同样的问题,或者说是很复杂的正则匹配。你可以在自己的电脑上试一下这个简单的例子:

这个应该还挺快的:

然而,你试着把3个换做29个的时候,就发现开始有点诡异的味道了,就好像Russ在他第一篇文章中的图示中展示的那样:

29个重复:

来个30个重复的结果:

31次重复跑了我67秒,也就是所谓的几何级的增长哟。这是因为Oniguruma的回溯算法只能通过对一个列表不停的迭代,这个列表里面存放的表达式的长度成几何级的增长。如果Oniguruma使用了Russ提到的 Thompson NFA算法就不会发生这事了。

结语

如我篇头所讲,在这里我解释了Oniguruma和Ruby在正则上的实现。当然大家也知道,有好多好多种正则操作和扩展供大家使用,每种都会和Oniguruma VM有关。在此之上,我的例子在常见的Ruby代码中的确是相对简单了,平常我们可能使用到十分复杂的正则表达式,我们的一个程序可能会执行成百上千的Oniguruma VM指令。

但是,底下的思路是没什么区别的。每个Oniguruma正则表达式都是编译成一系列和状态机等级的虚拟机指令。当Oniguruma到达终态的时候,比如 end——它就从回溯栈里弹出可能路径上的另外一条指令和相对应目标串的位置,这些东西之前是被一个push或者类似的指令推进栈里去的。

发表评论

电子邮件地址不会被公开。 必填项已用*标注