构建Regex编写器

实际上,这看起来越来越像一个编译器应用程序。事实上,如果我没记错的话,Aho-Dragon编译器一书使用了一个regex示例来构建DFA编译器。这就是开始的地方。这可能是一个非常酷的编译器项目。

如果这太多了,你可以把它当作一个优化过程来处理,以进一步细化它,但它首先都是预定义的算法:

第一关:想配猫,接住罐头 结果:/Cat |捕获|罐/

第二遍:寻找相似的起动条件: 结果:/Ca(t | tches | ans)/

第二遍:寻找相似的结束条件: 结果:/Ca(t | tch | an)s*/

第三遍:寻找更多的改进,比如重复和否定条件

正则表达式等价于DFA(确定性有限自动机)。

如果生成一个确定性自动机就足够了,那么看看Alergia(理论)和MDI算法(实际使用)。

http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf

如果要生成更小的模型,可以使用其他算法。描述它的文章在这里: http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz

http://www.grappa.univ-lille3.fr/~lemay

如果您想使用否定的例子,我建议您使用一个简单的规则(着色)来防止DFA的两个状态被合并。

如果你问这些人,我相信他们会分享他们的源代码。

在我攻读概率自动机的博士学位期间,我也做过同样的算法。也就是说,你可以把概率与每个字符串相关联,我已经做了一个C++程序,学习“加权自动机”。

这些算法主要是这样工作的:

从正面例子:{abb,aba,abb}

创建最简单的DFA,完全接受以下所有示例:

-> x -- a --> (y) -- b --> (z)
          \
            b --> t -- b --> (v)

状态是x,y,z,t和v。(z)表示它是一个有限状态。

然后是DFA的“merge”状态:(这里举例来说,合并状态y和t后的结果。

               _
              /  \
             v    | a,b     ( <- this is a loop :-) )
x -- a -> (y,t) _/

选择合并哪些状态是算法之间的主要区别。

这符合例子

我不认为这是个有用的问题。你必须从语义上知道你需要表达什么来推断某件事。当你写一个正则表达式时,你有一个目的:接受URL,接受电子邮件,从代码中提取标记等等。我会重新定义这个问题:给定正则表达式的知识库和语义,计算最小的正则表达式。这更进一步,因为你有自然语言试图解释一个普遍的表达式,我们都知道它是如何变得模棱两可的!你必须有一些语义上的解释。如果不这样做,对于示例,您可以做的最好的事情就是计算覆盖ok列表中所有字符串的regex。

覆盖算法:

填充确定列表
填写不合格列表
检查是否重复
检查是否有矛盾(同一字符串不能同时出现在两个列表中)
从Ok列表创建确定性有限自动机(DFA),其中列表中的字符串是最终状态
通过消除重复状态简化DFA。([1]4.4)

测试正常列表和不正常列表

[1] Introduction to Automata Theory, Language, and Computation. J. Hopcroft, R. Motwani, J.D. Ullman, 2nd Edition, Pearson Education.

遗传规划(GP)是一种进化机器学习技术,它将给定问题的候选解表示为抽象语法树。

已经发表了一些关于如何使用GP来找到与给定的一组示例相匹配的正则表达式的研究。 你可以找到文章和细节 here

这样做的webapp托管在 regex.inginf.units.it . 应用程序背后的源代码已于公开发布 github

http://github.com/mvaled/inferdtd

应该会对AutomataInferrer.py这很简单。

RegexBuilder