OCaml：如何测试我自己的正则表达式库

Question

我做了一个简单的正则表达式引擎，支持连接、交替、闭包和char a .. z。

我表示nfa和dfa的方式是用record:

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： states: 0 1 2 3 alphabets: a transactions: 0->e->1, 1->a>2, 2->e->3, 2->e->1, 0->e->3 start_state: 0 final_states: 3

然后 dfa:

states: 0 1 alphabets: a transactions: 0->a->1, 1->a->1 start_state: 0 final_states: 0 1

但是，我在我的代码中使用了很多递归。我的程序为 nfa 和 dfa 中的每个节点生成状态编号的方式确实是不可预测的。我不知道如何在不使用笔和纸自己测试的情况下验证生成的dfa是否正确

我正在尝试找到一种更好的方法来测试我的代码，以便将来可以在我的程序中添加更多功能。

谁能给我一些建议吗？

Answer 1

缺少形式验证，您可以：

使用单元测试库，例如 OUnit or alcotest to test your engine against a large number of examples. Here is a nice blog post 比较其他一些测试库。
将其与 Bisect_ppx, which serves two purposes: it directly helps make sure that your examples test the various branches in your generator, and also indirectly causes you to look at the generator much more closely and think about how to write examples to test the various code paths. Here is another blog post 等覆盖工具相结合，对覆盖工具进行简要比较。

编辑：我想如果你想直接测试你的 DFA，你可能想为你的特定类型写一些专门的 "coverage tool"，告诉你状态的分数 and/or state/transition 您在测试每个 DFA 期间达到的对，以及哪些对。这将是您当前用于沿着输入字符串遍历 DFA 的函数的某种修改形式。

免责声明：我目前正在为改进 Bisect_ppx（这是 Bisect 的 "modern" 分支）做出贡献。不过，我不隶属于或参与此处提到的任何其他内容。

Answer 2

一个相当复杂的计划是将您的 DFA 转换回正则表达式，然后测试结果是否等同于您的原始正则表达式。这是一个 SO 页面，提供了一些测试 RE 等价性的方法：Regex: Determine if two regular expressions could match for the same input?

希望这两个逆转换有助于相互调试:-)

Answer 3

您的正则表达式库的一个 property-based test 是编写

生成随机正则表达式的正则表达式生成器
一个字符串生成器，给定一个正则表达式，在这种语言中生成随机字符串。
A 属性，给定一个正则表达式，您的正则表达式匹配器匹配字符串生成器的输出。

对于 OCaml 中的 property-based 测试，您可以使用 QCheck.

OCaml：如何测试我自己的正则表达式库

OCaml: How to test my own regular expression library

regex

testing

ocaml

unit-testing