我做了一个简单的正则表达式引擎,它支持连接,交替,闭包和char a .. z.
我代表nfa和dfa的方式是使用记录：
type state = int with sexp,compare
type alphabet = char with sexp,compare
type transaction = state * alphabet option * state with sexp,compare
type d_transaction = state * alphabet * state with sexp,compare
type state_set = State_set.t
type states_set = States_set.t
type nfa = {
states : State_set.t ;
alphabets : Alphabet_set.t ;
transactions : Transaction_set.t;
start_state : state;
final_states : State_set.t;
}
type dfa = {
d_states : State_set.t ;
d_alphabets : Alphabet_set.t;
d_transactions : D_Transaction_set.t ;
d_start_state : state ;
d_final_states : State_set.t;
}
例如,字符串“a *”将被解析为Closure(Char’a’),然后进行转换
到nfa：
国家：0 1 2 3
字母：a
交易：0-> e-> 1,1-> a> 2,2-> e-> 3,2-> e-> 1,0-> e-> 3
start_state：0
final_states：3
那么dfa：
州：0 1
字母：a
交易：0-> a-> 1,1-> a-> 1
start_state：0
final_states：0 1
但是,我在代码中使用了很多递归.我的程序为nfa和dfa中的每个节点生成状态编号的方式实际上是不可预测的.我不知道如何在不使用笔和纸张自己进行测试的情况下验证生成的dfa是否正确
我试图找出一种更好的方法来测试我的代码,以便将来可以在我的程序中添加更多功能.
有人可以给我一些建议吗？
解决方法
一个相当精细的计划是将您的DFA转换回正则表达式,然后测试结果是否等同于您的原始正则表达式.这是一个SO页面,提供了一些测试RE等价的方法：
Regex: Determine if two regular expressions could match for the same input?
希望两个逆转换有助于相互调试:-)
