生成与给定正则表达式匹配的随机序列
问题描述:
具有任意正则表达式如何生成匹配(或不匹配)给定正则表达式的随机文本序列?我对理论和实际使用感兴趣(需要在.NET上下文中改进我的测试),因此我们将欣赏链接到文章或现有库。看它生成与给定正则表达式匹配的随机序列
答
从纯理论的角度来看,正则表达式是等效于理性语言,这是在以下基础上构建:
-
{}
(无字的语言)是合理的。 -
{a}
(使用单一一个字的字母语言)是合理的。 - 如果
L
和M
是两种理性语言,那么它们的联合(L
或M
中的词)是合理的。 - 如果
L
和M
两种理性语言,那么它们的级联LM
(通过从前面加上M
从L
一个单词到字构造的话)也是合理的。 - 如果
L
是一种合理的语言,那么L*
(通过连接来自语言L
的任何数量的词构造的词)也是合理的。
此建设性的方法补充了正则表达式识别/匹配方法,并且有助于构建递归与表达式匹配的话:
make({}) = ""
make({a}) = "a"
make(A|B) = flip-coin ? make(A) : make(B)
make(AB) = make(A) + make(B)
make(A*) = flip-coin ? "" : make(A) + make(A*)
答
的一种方式是,每一个正则表达式(我相信)被表示为一个有限状态机中的状态之间的每个过渡由消耗一个或多个字符(或者零字符也是有效的?龙自从我研究这个以来的时间)。
所以,去了解这一个办法是想或正则表达式转换成有限状态机和状态移动到状态,随机选择的转变,直到你打一个有效的最终状态。
当然,我不知道这个方法实际上是如何可行的是代码,或任何这样的库是否存在。
http://lara.epfl.ch/dokuwiki/equivalence_of_finite_state_machine_and_regular_expression_languages
答
在.NET中,你可能也想看看项目Fare。它完全符合你的描述。
这里是如何使用它:
var xeger = new Xeger(pattern);
var match = xeger.Generate();
Regex.IsMatch(match, pattern);
// Prints -> true
既然你提到的单元测试,你也可以考虑使用AutoFixture曾经你装饰一个属性(或字段)的[RegularExpression]属性将分配与正则表达式匹配的值。
我不知道一个合适的.NET库,但尝试在*中搜索“xeger”;这可能会给你一些指示。 xeger是一个Java库,用于从给定的正则表达式中生成字符串。 – 2010-12-06 07:52:11