• Contents

有穷状态自动机

正则之所以能够处理复杂文本，就是因为采用了有穷状态自动机（finite automaton）。

有穷状态是指一个系统具有有穷个状态，不同的状态代表不同的意义。自动机是指系统可以根据相应的条件，在不同的状态下进行转移。从一个初始状态，根据对应的操作（比如录入的字符集）执行状态转移，最终达到终止状态（可能有一到多个终止状态）。

有穷自动机的具体实现称为正则引擎，主要有 DFA 和 NFA 两种，其中 NFA 又分为传统的 NFA 和 POSIX NFA。

DFA：确定性有穷自动机（Deterministic finite automaton）
NFA：非确定性有穷自动机（Non-deterministic finite automaton）

正则的匹配过程

使用到编程语言时，我们经常会「编译」一下正则表达式，来提升效率，比如在 Python3 中：

>>> import re
>>> reg = re.compile(r'a(?:bb)+a')
>>> reg.findall('abbbba')
['abbbba']

这个编译的过程，其实就是生成自动机的过程，正则引擎会拿着这个自动机去和字符串进行匹配。生成的自动机可能是这样的：

在状态 s3 时，不需要输入任何字符，状态也有可能转换成 s1。你可以理解成 a(bb)+a 在匹配了字符 abb 之后，到底在 s3 状态，还是在 s1 状态，这是不确定的。这种状态机就是非确定性有穷状态自动机（Non-deterministic finite automaton 简称 NFA）。

NFA 和 DFA 是可以相互转化的，当我们把上面的状态表示成下面这样，就是一台 DFA 状态机了，因为在 s0-s4 这几个状态，每个状态都需要特定的输入，才能发生状态变化。

DFA & NFA 工作机制

字符串：we study on jikeshijian app
正则：jike(zhushou|shijian|shixi)

NFA 引擎的工作方式是：先看正则，再看文本，而且以正则为主导。正则中的第一个字符是 j，NFA 引擎在字符串中查找 j，接着匹配其后是否为 i，如果是 i 则继续，这样一直找到 jike。

regex: jike(zhushou|shijian|shixi)
          ^
text: we study on jikeshijian app
                     ^

再根据正则看文本后面是不是 z，发现不是，此时 zhushou 分支淘汰。

regex: jike(zhushou|shijian|shixi)
            ^
         淘汰此分支(zhushou)
text: we study on jikeshijian app
                      ^