正则表达式和 NFA

作为前端大佬的你,想必对于 JavaScript 的正则表达式非常熟悉了,甚至随手就能利用正则表达式写出一些惊世骇俗的代码。只是不知道你是否有和我一样的疑惑:正则表达式是怎么执行的呢?

我们写下这样的正则表达式 (a+|b)c,然后用它来匹配字符串 aacdeabcde,这是怎样的一个过程呢?

前段时间,我试着去查找、学习相关的资料,然后知道了以下的内容:

  • 目前正则表达式引擎主要有两种:NFADFA
  • JavaScript 采用的是 NFA 引擎

那么 NFA 又是啥,跟 DFA 有什么不同?NFA 又是怎么实现正则表达式匹配的呢?

接下来,我试着用我自己的方式来介绍,希望也能帮助对此感兴趣的你。

NFA

NFA 是指 Nondeterministic Finite Automaton,非确定有限状态自动机。

有点深奥,我刚看到的时候也很懵,咱们慢慢来。

先说有限状态机(Automation),来个示例图看下:

有限状态机

状态机中有这样一些要素,对照上图分别说下:

  • 开始状态:圆圈表示状态,被一个“没有起点的箭头”指向的状态,是开始状态,上例中是 S1
  • 最终状态:也叫接受状态,图中用双圆圈表示,这个例子中也是 S1
  • 输入:在一个状态下,向状态机输入的符号/信号,不同输入导致状态机产生不同的状态改变
  • 转换:在一个状态下,根据特定输入,改变到特定状态的过程,就是转换

所以有限状态机的工作过程,就是从开始状态,根据不同的输入,自动进行状态转换的过程。

上图中的状态机的功能,是检测二进制数是否含有偶数个 0。从图上可以看出,输入只有 1 和 0 两种。从 S1 状态开始,只有输入 0 才会转换到 S2 状态,同样 S2 状态下只有输入 0 才会转换到 S1。所以,二进制数输入完毕,如果满足最终状态,也就是最后停在 S1 状态,那么输入的二进制数就含有偶数个 0。

还是有点晕,这个和正则表达式有什么关系呢?

正则表达式,可以认为是对一组字符串集合的描述。例如 (a+|b)c 对应的字符串集合是:

有限状态机也可以用来描述字符串集合,同样是正则表达式所描述的集合,用有限状态机来表示,可以是这样的:

NFA – (a+|b)c

这里的 NFA 状态图是我用自己写的页面绘制出来的,比较简陋,不过我相信你可以看懂。
你可以在这里(luobotang/nfa)自己试试看,只支持简单的正则表达式。

并且,有限状态机是可以“执行”的,给出如上的状态机之后,就可以用来对输入的字符串进行检测。如果最终匹配,也就意味着输入的字符串和正则表达式 (a+|b)c 匹配。

所以,编程语言中的正则表达式,一般是通过有限状态机来实现。正则表达式匹配字符串的过程,可以分解为:

  • 正则表达式转换为等价的有限状态机
  • 有限状态机输入字符串执行

到这里,我想你大概知道有限状态机在正则表达式中的作用了,当然,只是具体实现还不清楚。

这里再讲一下 NFA 和 DFA 的区别。DFA 是 Deterministic Finite Automaton,确定有限状态机。DFA 可以认为是一种特殊的 NFA,它最大的特点,就是确定性。它的确定性在于,在一个状态下,输入一个符号,一定是转换到确定的状态,没有其他的可能性。

举个例子,对于正则表达式 ab|ac,对应 NFA 可以是这样的:

NFA – ab|ac

可以看到,在状态 1 这里,如果输入 a,其实有两种可能,如果后面的符号是 b,那么可以匹配成功,后面符号是 c 也能匹配成功。所以状态机在执行过程中,可能要尝试所有的可能性。在尝试一种可能路径匹配失败后,还要回到之前的状态再尝试其他的路径,这就是“回溯”。

但是 DFA 消除了这种不确定性,所以可以想见,其执行性能应该要比 NFA 更好,因为不需要回溯。

NFA 是可以转换为等价的 DFA 的,也就是说,理论上讲,正则表达式可以用 DFA 来实现,从而获得优于 NFA 的执行性能。但是 NFA 转换 DFA 的过程,会消耗更多资源,甚至最终得到的 DFA 要占用大量存储空间(据有的资料的说法,可能会产生指数级增长)。而且,DFA 相比 NFA,在实现一些正则表达式的特性时会更复杂,成本更高。所以当前的许多编程语言,其正则表达式引擎为 NFA 模式。

可以用如下的正则表达式测试当前编程语言采用的引擎是否 NFA:

用上面的正则表达式来测试字符串 nfa not,NFA 引擎在检测满足 nfa 就返回匹配成功的结果了,而 DFA 则会尝试继续查找,也就是说会得到“最长的匹配结果”。

从正则表达式到 NFA

了解了 NFA 在正则表达式中的应用,接下来要介绍的是如何将正则表达式转换得到对应的 NFA。这一部分会稍微有些枯燥,不过对于深入理解正则表达式和 NFA 还是挺有帮助的。

Thompson 算法

Thompson 算法用于转换正则表达式为NFA,它并非最高效的算法,但是实用,易于理解。

Thompson 算法中使用最基本的两种转换:

Thompson 算法基本元素

普通转换就是在一个状态下,输入字符a后转换至另一个状态;epsilon转换则不需要有输入,就从一个状态转换至另一个状态。

正则表达式中的各种运算,可以通过组合上述两种转换实现:

  • 组合运算 RS
RS
  • 替换运算 R|S
    R|S
  • 重复运算 R*
    R*

上面图中的 R、S 是有开始状态和结束状态的 NFA。

以正则表达式 ab|c 为例,包括两个运算:

  • ab 组合
  • ab 的结果,与 c 替换

这样我们把正则表达式视为一系列输入和运算,进行分解、组合,就可以得到最终的 NFA。

首先,我们要把正则表达式转换为方便记录输入、运算的方式。

正则表达式 -> 后缀表达式

后缀表达式是一种方便记录输入、运算的表达式,本身已包含了运算符的优先级,也称为 逆波兰表示法(Reverse Polish Notation,简写为 RPN)。

为方便记录运算,我们为正则表达式中的组合运算也创建一个运算符“.”(本文只涉及最简单的正则表达式形式,这里的“.”不是用于匹配任意字符的特殊符号)。

正则表达式ab|c对应的后缀表达式为 ab.c|

这样,通过逐个扫描后缀表达式,并识别其中的运算符来执行,就可以对后缀表达式进行求解。对于正则表达式来说,则是在将其变为后缀表达式后,通过“求值”的过程来进一步构建并得到最终的 NFA。

用于创建后缀表达式的是 调度场算法

对于这里的正则表达式处理的场景,算法的大致描述如下:

代码在:regex2post() | nfa.js#L14 – luobotang/nfa

具体处理过程中,由于原始正则表达式中并没有组合运算符,所以需要自行判断合理的插入位置。

运算符优先级如下(由高到低):

  • * ? +
  • .
  • |
  • (

后缀表达式 -> NFA

基于后缀表达式创建 NFA,是一个由简单的 NFA 进行不断组合得到复杂 NFA 的过程。

用于表示状态 State 的数据结构为:

每个状态可以对应最多两个 out 状态,像 a|b|c 的表达式,会被分解为 (a|b)|c,每次运算符“|”都只处理两个(子)表达式。

在构造最终 NFA 过程中,每次会创建 NFA 的片段 Fragment:

不管 NFA 片段内部是怎样复杂,它都只有一个入口(开始状态),一个出口(最终状态)。

这一部分代码在:post2nfa() | nfa.js#L90 – luobotang/nfa

处理的过程大致为:

以对组合运算的处理为例:

从 stack 出栈两个 NFA 片段,然后将其首尾相连后构建新的 NFA 片段再入栈。

其他处理过程就不详细介绍了,感兴趣可以看下代码。

NFA 的执行

NFA 的执行过程就是用当前状态来比对字符串的当前字符,如果匹配就继续比对下一个状态和下一个字符,否则匹配失败。

不过由于 NFA 的不确定性,所以可能会同时有多个匹配的状态。

我这里就简单粗暴了,直接让当前所有的状态都进行比对,仍然满足条件的下一个状态再继续参与下一轮比对。一次只跟踪一条路径,匹配失败后再回溯肯定也是可以的,不过就要复杂很多了。

代码在:simulator.js – luobotang/nfa

总结

综上,正则表达式的执行,可以通过构建等价的 NFA,然后执行 NFA 来匹配输入的字符串。真实的 JavaScript 中的正则表达式拥有更多的特性,其正则表达式引擎也更加复杂。

希望通过我的介绍,能够让你对正则表达式有了更多的了解。当然,水平有限,讲得不当的地方在所难免,欢迎指正。

最后,感谢阅读!

参考资料

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 收藏 评论

关于作者:luobotang

前端工程师@网易 个人主页 · 我的文章 · 4 ·  

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部