深入正则表达式(4)：状态机与正则匹配

状态机

有限状态系统

下面直接给出几个有限状态系统的实例，从直观上就能理解有限状态系统：

例1：指针式钟表，一共有12*60*60个状态，每过一秒，钟表就从一种状态转换到另一种状态

例2：围棋共有3**361个状态，每走一步棋，就从一个状态转换到另一个状态

例3：语言的识别

有限状态机

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

有些地方也叫“自动机”，指的都是同一个东西。

FSM的表示，我们常用状态转移图。下图就是一个模式字符串的FSM状态转移图：

给定待匹配的字符串”abababaca”，就能通过模式串的FSM进行匹配，这就是正则表达式的匹配思想。

正则表达式匹配实例

给定正则表达式a(bb)+a，其中+表示匹配前面的子表达式一次或多次，所以字符串abba或abbbba都能被这个模式所匹配。

下图是该正则表达式对应的FSM状态转移图。

该FSM中，圈代表不同的状态。读入字符串时，就从一个状态进入另一个状态。FSM有开始和匹配（匹配）两种特殊状态，分别位于头部和尾部。

下面是匹配的过程示例图：

该状态机结束于最后一个状态，这是一个匹配成功的状态。若状态机结束于非匹配成功状态，那么匹配失败。如果在运行过程中，没有办法到达其他状态，那么状态机提前结束。

我们刚才考虑的是确定状态自动机，因为在每一个状态，可达的下一个状态至多只有一个。我也可以创建一个有多种选择的机器。以之前的自动机为例：

机器的状态是不确定的，因为当它读入ab到达s2，它对于下一个状态有多个选择：它可以回到s1或者到达s3。由于机器无法预料接下来的输入，它不知道该选择哪个状态。可以同时保存多种状态的也就是非确定状态自动机(NFA)。

多路径匹配

正则表达式等效于有限状态机，每一个正则表达式都有一个对应的有限状态机。反之，有限状态机也对应一个正则表达式。具体的对应关系可以参见这篇文章（https://sine-x.com/regexp-1/）。

下面是多路径的算法匹配过程：

匹配时，可能有多条路径，遇到分支时，可以采用试错法，一条走不通，再尝试另一条。但这种做法效率较低。

所以另一种更优的做法，是在分支处同时匹配多条分支，同时保持多个状态，这样避免了很多不必要的尝试。

有限自动机

什么叫有限自动机(Finite Automate)呢？

我们把有限自动机理解为一个机器人，在这个机器人眼里，所有的事物都是由有限节点组成的。机器人按照顺序读取有限节点，并表达成有限状态，最终机器人输出接受或者拒绝作为结束。如果没有见过读卡机(穿孔卡片)，可以回想下初中物理试验的自由落体运动纸带。

关注它的两个特点：

• 有限状态集。
  

• 只根据当前状态和当前输入来决定下一个状态。它有点一板一眼。

怎么理解第二个特点？我们看一个例子：

'aab'.match(/a*?b/);
// ["aab", index: 0, input: "aab", groups: undefined]

我们知道*?是非贪婪匹配，按照我们人类灵活的尿性，直接把匹配结果ab甩他脸上。

但有限自动机不会。第一步它用a匹配a非常完美，然后发现对于a是非贪婪模式，于是试着用b匹配下一个a，结果非常沮丧。于是它只能继续用a匹配，匹配成功后依然没忘非贪婪特性，继续试着用b匹配下一个字符b，成功，收官。

其实写出这段代码的开发者想要的结果应该是ab，但有限自动机从来不仰望星空，只低头做事，一板一眼的根据当前状态和当前输入来决定下一个状态。

参考文章：

https://zhuanlan.zhihu.com/p/40179377

https://blog.csdn.net/u011125324/article/details/73162311

https://kb.cnblogs.com/page/96414/

https://www.php.cn/manual/view/32510.html

https://www.cnblogs.com/dragon/archive/2006/05/08/394078.html

https://www.jianshu.com/p/e260e7087fed

正则表达式之基本原理 https://www.cnblogs.com/longhuihu/p/4128203.html

正则表达式工作原理 https://www.cnblogs.com/aaronjs/archive/2012/06/30/2570800.html

https://www.cnblogs.com/chip/p/4278135.html

正则表达式的先行断言、后行断言 https://blog.csdn.net/icewfz/article/details/79900993

https://wenku.baidu.com/view/f8ec4d7814791711cd791768.html

https://sine-x.com/regexp-1/

https://www.cnblogs.com/jolin123/p/3443543.html

转载本站文章《深入正则表达式(4)：状态机与正则匹配》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/IntroductionAlgorithms/8423.html