分类 算法 下的文章

NFA to DFA

关于实现

将 NFA 构造成有向图,nfa_state 为顶点,state 到下一个 state 之间,通过接受的 nfa_edge 转移。nfa_edge 接受字符或空串(epsilion)。
NFA 转 DFA 过程中,要把 e_closure(T) 算作一个 DFA 状态,所以在 nfa_to_dfa 之前要先 nfa_alloc_id,为每个 nfa_state 标记 id,以便后续 e_closure(T) 的结果方便比较。在我的实现里,我在把 e_closure(T) 返回的 set 构造成一个按 id 升序排序的状态数组,算 hash 加速查找(我用加法是偷懒)。主要算法可以看龙书不再多说。

实现

fa.go

...

- 阅读全文 -