Aoba

简单来说是一个用Haskell写的可以对正则表达式求交集，子集和相等性的库，稍作扩展也可以用来做正则匹配
https://github.com/mayokaze/Aoba

编译： ghc -O2 aoba.hs RE.hs
使用方法大致如下：

• ./aoba -i "a" "a*" -- 交集
• ./aoba -c "a+" "a*" -- 子集
• ./aoba -e "aa*" "a+" -- 相等

比起传统的 thompson 构建算法，求导算法不构建自动机，而且能够支持本应属于正则语言的 and 和 not 运算.
关于集合运算的效率，和传统的 epsilon closure 同样是 n^2,不过传统 nfa 还多了 nfa to regex 一步所以求导算法应该是占优的

Google 有写过类似的项目： https://github.com/google/redgrep 但是他们只用到了 derive 而且他们的目的是构建自动机做匹配最终编译成 llvm bc.
如果纯求导算法做 match 的话工程上用不会太实用主要是因为 unicode 字符集爆炸的问题.

具体的原理见这篇论文： Valentin M. Antimirov: Partial Derivatives of Regular Expressions and Finite Automaton Constructions. Theor. Comput. Sci. 155(2): 291-319 (1996)

其他一些更高级的讨论例如正则求（偏）导和实函数求（偏）导的内在关联，自动机代数能否套用群论（环）的定义， n 次幂化简算法等等都跟朋友有过一些讨论，的确是非常有意思的一个课题，有想法的朋友请不吝赐教