Ken Thompson’s NFA Simulation Algorithm
0. Retrospect
书接前两回：
有一个问题我们很早就应该讨论的，那就是：为啥我们选择用 $\varepsilon$-NFA 去做 regex matching，而不是用 DFA 去做？这里涉及一个 trade-off:
- DFA simulation 的效率高 (因为 deterministic)，但是 DFA 构造的难度大
- NFA simulation 的效率低，但是 NFA 构造的难度低
《编译原理 (第 2 版）》3.7.5 节说：
如果字符串处理器被频繁使用，比如词法分析器，那么转换到 DFA 时付出的任何代价都是值得的。然而在另一些字符串处理应用中，例如 grep，用户指定一个正则表达式，并在一个或多个文件中搜索这个表达式所描述的模式，那么跳过构造的 DFA 步骤直接模拟 NFA 可能更加高效。
1. 原 C 代码的逻辑其实不复杂，就是 Set + $\varepsilon$-closure + BFS
1.1 struct List $\Rightarrow$ Set + $\varepsilon$-closure
原 C 代码看起来非常的繁琐，但其实它很大一部分 struct List 的代码，其实就是要实现 set + $\varepsilon$-closure 的逻辑。
我们还是先来解密一下 variable names:
listid$\Rightarrow$traversal_stepstruct List并没有这么listid这么个 field- 这个外部的
listid是我们在计算 $\varepsilon$-closure 时的一个 versioning 计数，即：- 假设我们用 DFS 计算 $\varepsilon$-closure，从 root 出发，我们每处理完一棵 subtree，我们就给
lastid += 1 List l1, l2在计算 $\varepsilon$-closure 的过程中，它们只是 content 变了，它们不知道lastid的变化
- 假设我们用 DFS 计算 $\varepsilon$-closure，从 root 出发，我们每处理完一棵 subtree，我们就给
state.lastlist$\Rightarrow$state.last_traversal_stepstruct State用lastlist来记录 state 是在哪一步被计入 list (也就是 closure 的)- 也能实现 loop detection 和 dedup
- 如果存在一个 $\varepsilon$-loop，那么 loop 上的所有 states 都是在同一步被加入 list 的，所以它们的
lastlist应该相同 - 如果 DFS 跑完了一整个 $\varepsilon$-loop，那么循环到 loop 开头时，state 的
lastlist一定是已经有值了，而且等于当前的listid- 此时我们就能判定 loop 已经跑完，可以 stop 了
- 而且 list 内也不会有 duplicate states
- 如果存在一个 $\varepsilon$-loop，那么 loop 上的所有 states 都是在同一步被加入 list 的，所以它们的
绕了这么大一圈，其实也没啥鸟用，我们不如直接用 set 来实现 $\varepsilon$-closure.
BFS + stack:
def epsilon_closure(states: Iterable[State]) -> set[State]:
if not states:
return None
closure = set()
stack = list(states)
while stack:
s = stack.pop()
if s not in closure:
closure.add(s)
else:
continue
# BFS style
if isinstance(s, SplitState):
stack.append(s.next_state_1)
stack.append(s.next_state_2)
return closure
DFS:
def epsilon_closure_recursive(states: Iterable[State]) -> set[State]:
if not states:
return None
closure = set()
def _calculate_closure(_s: State):
nonlocal closure
if _s not in closure:
closure.add(_s)
if isinstance(_s, SplitState):
_calculate_closure(_s.next_state_1)
_calculate_closure(_s.next_state_2)
return
# DFS style
for s in states:
_calculate_closure(s)
return closure
1.2 match $\Rightarrow$ 受 transition 引导的 BFS
然后，你仔细一琢磨：这个 NFA simulation，不就是 BFS 吗？ 只是这里是一种 “受引导的” BFS：
- 假设我们要 match 一个 string $\overline{c_1 c_2 \dots c_n}$
- 以 $q_0$ 为起点，准备 match $c_1$
- 假设所有从 $q_0$ 开始、经过 $c_1$-transition 到达的 state 集合为 $Q_1$
- i.e. $Q_1 = \lbrace q \mid \delta(q_0, c_1) = q \rbrace$
- 以 $Q_1$ 为起点，准备 match $c_2$
- 假设所有从 $\forall q_i \in Q_1$ 开始、经过 $c_2$-transition 到达的 state 集合为 $Q_2$
- i.e. $Q_2 = \bigcup_{\forall q_i \in Q_1}\lbrace q \mid \delta(q_i, c_2) = q \rbrace$
- 依此类推，一直 match 到 $c_n$，假设我们最终到达的 state 集合为 $Q_n$
- 如果 $q_f \in Q_n \Rightarrow$ match 成功
- otherwise, match 失败
下图就是一个 match $\overline{c_1 c_2 c_3}$ 成功的例子：
flowchart LR
A([$$q_0$$])
A e1@--> |$$c_1$$| B
A e2@--> |$$c_1$$| C
A --> D([$$q_3$$])
A --> E([$$q_4$$])
B e3@--> |$$c_2$$| F
B e4@--> |$$c_2$$| G
C e5@--> |$$c_2$$| H
C --> I([$$q_8$$])
F --> K
G e6@--> |$$c_3$$|K
H e7@--> |$$c_3$$|L
D --> I
E --> I
I --> L
L --> K
subgraph $$Q_1$$
direction LR
B([$$q_1$$])
C([$$q_2$$])
end
subgraph $$Q_2$$
direction LR
F([$$q_5$$])
G([$$q_6$$])
H([$$q_7$$])
end
subgraph $$Q_3$$
direction LR
K[["$$q_{f}$$"]]
L(["$$q_{10}$$"])
end
style A fill:#FAD689
style K fill:#FFFFFB
e1@{ animate: slow }
e2@{ animate: slow }
e3@{ animate: slow }
e4@{ animate: slow }
e5@{ animate: slow }
e6@{ animate: slow }
e7@{ animate: slow }
我说这种 BFS 是 “受引导的”，意思就是每次 breadth 的范围要受当前企图 match 的 $c_i$ 的限制。
Russ Cox 提到的 “某些 regex engine 的实现，在 re 为 $(a?)^{29} a^{29}$ 时，match string $a^{29}$ 的效率极低” 的情况，其实就是因为这些 regex engine 用的是 DFS + backtrace.
我们简化一下：re 为 $(a?)^{2} a^{2}$，企图 match string $a^{2}$：
flowchart LR
A([$$q_0$$])
A --> |a| B([$$q_1$$])
A e1@--> |$$\varepsilon$$| C([$$q_2$$])
B --> |a|D([$$q_3$$])
B --> |$$\varepsilon$$|E([$$q_4$$])
C --> |a|E
C e2@--> |$$\varepsilon$$|F([$$q_5$$])
D --> |a|G([$$q_6$$])
E --> |a|G
F e3@--> |a|G
G e4@--> |a|H[["$$q_{f}$$"]]
style A fill:#FAD689
style H fill:#FFFFFB
e1@{ animate: slow }
e2@{ animate: slow }
e3@{ animate: slow }
e4@{ animate: slow }
你用 DFS + backtrace 就是一直 path testing 试错，你的 search 过程可能是：
- $q_0 \rightarrow q_1 \rightarrow q_3 \Rightarrow$ failure
- $q_0 \rightarrow q_1 \rightarrow q_4 \rightarrow q_6 \Rightarrow$ failure
- $q_0 \rightarrow q_2 \rightarrow q_4 \rightarrow q_6 \Rightarrow$ failure
- $q_0 \rightarrow q_2 \rightarrow q_5 \rightarrow q_6 \rightarrow q_f$
至少是 15 次 transitions.
而 BFS 的 search 过程是：
- when calculating $Q_1$:
- $q_0 \rightarrow q_1 \rightarrow q_4$ (found $q_1$ and $q_4$)
- $q_0 \rightarrow q_2 \rightarrow q_4$ (found $q_4$ again)
- $q_2 \rightarrow q_5$ (found $q_5$)
- when calculating $Q_2$:
- $q_1 \rightarrow q_3$ (found $q_3$)
- $q_4 \rightarrow q_6$ (found $q_6$)
- $q_6 \rightarrow q_f$ (found $q_f$)
只需要 8 次 transitions.
Russ Cox 给出的 time complexity 为：
- DFS + backtrace: $O(2^n)$:
- 你相当于是有一个长度为 $n$ 的
array[n]，你选择array[i] = 1就表示用第 $i$ 个 $a?$ 去匹配一个 $a$ - 每个
array[i]都有1和0两种选择 - 所以一定有 $2^n$ 种可能
- 你相当于是有一个长度为 $n$ 的
- BFS: $O(n^2)$
- 这个规律还蛮明显的：
- 当 $n=1$ 时，$q_0$ 到 $q_1, q_2$ 有 $2$ 条 edges
- 当 $n=2$ 时，$q_0$ 到 $q_3, q_4, q_5$ 有 $2 + 4$ 条 edges
- 当 $n=k$ 时，$q_0$ 到 $q_{\frac{k^2 + k}{2}}, \dots, q_{\frac{k^2 + 3k}{2}}$ 有 $2 + 4 + \dots + 2k$ 条 edges
- 就是一种杨辉三角形
- 所以最多只需要尝试 $\frac{(2+2n) \times n}{2} = O(n^2)$ 条 edges
- 这个规律还蛮明显的：
我们给出一个 python 实现：
def match(start_state: State, _input: str) -> bool:
if start_state is None:
raise ValueError("Invalid NFA!")
if not _input:
raise ValueError("Invalid input!")
current_closure = epsilon_closure(start_state)
for c in _input:
valid_states = [s for s in current_closure if isinstance(s, LiteralState) and s.literal == c]
current_closure = epsilon_closure(valid_states)
if current_closure is None:
return False
for s in current_closure:
if isinstance(s, AcceptState):
return True
return False
Comments