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

...

- 阅读全文 -

Regular Expression Matching

题目传送门: 我是传送门

实现一个简单的正则匹配, 支持克林*和.任意字符

用 NFA,没有用 epsilon 边。
build_nfa 返回的是包含全部状态的一个 vector,然后 states[0] 是初始态,可以再加一个终止态,不过我实现的时候偷懒了,然后就是模拟 NFA

C++ 实现

...

- 阅读全文 -