正则表达式和NFA

时间  2019-11-06 标签 正则 表达式 nfa

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

咱们写下这样的正则表达式 (a+|b)c，而后用它来匹配字符串 aacde、abcde，这是怎样的一个过程呢？html

前段时间，我试着去查找、学习相关的资料，而后知道了如下的内容：前端

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

那么 NFA 又是啥，跟 DFA 有什么不一样？NFA 又是怎么实现正则表达式匹配的呢？java

接下来，我试着用我本身的方式来介绍，但愿也能帮助对此感兴趣的你。git

NFA

NFA 是指 Nondeterministic Finite Automaton，非肯定有限状态自动机。github

有点深奥，我刚看到的时候也很懵，我们慢慢来。正则表达式

先说有限状态机（Automation），来个示例图看下：算法

有限状态机

状态机中有这样一些要素，对照上图分别说下：express

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

因此有限状态机的工做过程，就是从开始状态，根据不一样的输入，自动进行状态转换的过程。编程

上图中的状态机的功能，是检测二进制数是否含有偶数个 0。从图上能够看出，输入只有 1 和 0 两种。从 S1 状态开始，只有输入 0 才会转换到 S2 状态，一样 S2 状态下只有输入 0 才会转换到 S1。因此，二进制数输入完毕，若是知足最终状态，也就是最后停在 S1 状态，那么输入的二进制数就含有偶数个 0。

仍是有点晕，这个和正则表达式有什么关系呢？

正则表达式，能够认为是对一组字符串集合的描述。例如 (a+|b)c 对应的字符串集合是：

ac
bc
aac
aaac
aaaac
...
复制代码

有限状态机也能够用来描述字符串集合，一样是正则表达式所描述的集合，用有限状态机来表示，能够是这样的：

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|nfa not
复制代码

用上面的正则表达式来测试字符串 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

- 建立输出队列 output 和运算符栈 ops
- 依次读取输入字符串中每个字符 ch
  - 若是 ch 是普通字符，追加到 output
  - 若是 ch 是运算符，只要 ops 栈顶的运算符优先级不低于 ch，依次出栈并追加到 output，最后将 ch 入栈 ops
  - 若是 ch 是“(”，入栈 ops
  - 若是 ch 是“)”，只要 ops 栈顶不是“(”，依次出栈并追加到 output
- 将 ops 中运算符依次出栈追加到 output
- 返回 output
复制代码

具体处理过程当中，因为原始正则表达式中并无组合运算符，因此须要自行判断合理的插入位置。

运算符优先级以下（由高到低）：

  • * ? +
  • .
  • |
  • (

后缀表达式 -> NFA

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

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

// State
{
  id: String,
  type: String, // 'n' - normal, 'e' - epsilon, 'end'
  symbol: String, // 普通状态对应的输入字符
  out: State, // 容许的下一个状态
  out1: State // 容许的下一个状态
}
复制代码

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

在构造最终 NFA 过程当中，每次会建立 NFA 的片断 Fragment：

// Fragment
{
  start: State,
  out: State
}
复制代码

无论 NFA 片断内部是怎样复杂，它都只有一个入口（开始状态），一个出口（最终状态）。

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

处理的过程大体为：

- 建立用于记录 NFA 片断的栈 stack
- 依次读取输入的后缀表达式的每一个字符 ch
  - 若是 ch 是运算符，从 stack 出栈所需数目的 NFA 片断，构建新的 NFA 片断后入栈 stack
  - 若是 ch 是普通字符，建立新的状态，并构建只包含此状态的 NFA 片断入栈 stack
- 返回 stack 栈顶的 NFA 片断，即最终结果
复制代码

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

const e2 = stack.pop()
const e1 = stack.pop()
e1.out.out = e2.start
stack.push(new Fragment(e1.start, e2.out))
复制代码

从 stack 出栈两个 NFA 片断，而后将其首尾相连后构建新的 NFA 片断再入栈。

其余处理过程就不详细介绍了，感兴趣能够看下代码。

NFA 的执行

NFA 的执行过程就是用当前状态来比对字符串的当前字符，若是匹配就继续比对下一个状态和下一个字符，不然匹配失败。

不过因为 NFA 的不肯定性，因此可能会同时有多个匹配的状态。

我这里就简单粗暴了，直接让当前全部的状态都进行比对，仍然知足条件的下一个状态再继续参与下一轮比对。一次只跟踪一条路径，匹配失败后再回溯确定也是能够的，不过就要复杂不少了。

代码在：simulator.js - luobotang/nfa

总结

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

但愿经过个人介绍，可以让你对正则表达式有了更多的了解。固然，水平有限，讲得不当的地方在所不免，欢迎指正。

最后，感谢阅读！

参考资料

联系我们 沪ICP备2021010478号-7