re2dot

根据正则表达式生成其对应 DFA 的状态转移图, 简单来说就是输入一个正则表达式, 然后会构造其对应的 NFA, 然后再构造对应的 DFA, 然后再最小化 DFA, 最后使用 dot 语法绘制出最小 DFA.

re2dot 使用姿势如下:

$ ./re2dot.py --help
usage: re2dot.py [-h] [-N] [-D] [-d] regexp

根据正则表达式生成其对应 DFA 的状态转移图

positional arguments:
  regexp         正则表达式

optional arguments:
  -h, --help     show this help message and exit
  -N, --nfa      若指定, 则输出原始 NFA 对应的状态转移图.
  -D, --dfa      若指定, 则输出原始 NFA 转换为 DFA 对应的状态转移图.
  -d, --minidfa  若指定, 则输出原始 NFA 转换为 DFA 并最小化后对应的状态转移图.

emmm.. 精力所限, 这里只支持闭包, 连接, 选择三种正则运算符. 据说剩余的正则运算符均可只用这三种运算符重写.

$ ./re2dot.py  'a|bc|def|ghij'
// Generated by hidva.com
digraph {
rankdir=LR
	0 [label="" peripheries=0]
	1 [peripheries=1]
	0 -> 1
	2 [peripheries=1]
	1 -> 2 [label=d]
	3 [peripheries=2]
	1 -> 3 [label=a]
	4 [peripheries=1]
	1 -> 4 [label=g]
	5 [peripheries=1]
	1 -> 5 [label=b]
	6 [peripheries=1]
	2 -> 6 [label=e]
	7 [peripheries=1]
	4 -> 7 [label=h]
	8 [peripheries=2]
	5 -> 8 [label=c]
	9 [peripheries=2]
	6 -> 9 [label=f]
	10 [peripheries=1]
	7 -> 10 [label=i]
	11 [peripheries=2]
	10 -> 11 [label=j]
}

$ ./re2dot.py -N 'a|bc|def|ghij' | dot -Tpng > imgs/nfa.png
$ open imgs/nfa.png

$ ./re2dot.py -D 'a|bc|def|ghij' | dot -Tpng > imgs/dfa.png
$ open imgs/dfa.png