我想知道如何找到一组与有限数量的匹配给定正则表达式的所有匹配。
例如:所有这些例子你可以假设它们以^开始，以$结束
`hello?` -> (hell, hello)
`[1-9][0-9]{0,3}` -> (1,2,3 ..., 9998, 9999)
`My (cat|dog) is awesome!` -> (My cat is awesome!, My dog is awesome!)
`1{1,10}` -> (1,11, ..., 111111111, 1111111111)
`1*` -> //error
`1+` -> //error
`(1|11){2}` -> (1,11,111,1111) //notice how it doesn't repeat any of the possibilities
我也很感兴趣，如果有一种方法来检索计数一个唯一的解决方案的正则表达式，或者如果有一种方法来确定正则表达式是否有一个有限的解决方案。
如果算法可以解析任何正则表达式就好了，但是一个足够强大的正则表达式子集就可以了。
我对PHP解决这个问题很感兴趣，但其他语言也可以。
编辑:我在我的形式理论课上学到了DFA，它可以用来实现正则表达式(和其他常规语言)。如果我可以将正则表达式转换为DFA，那么解决方案对我来说似乎相当简单，但这种转换对我来说似乎相当棘手。
编辑2:感谢所有的建议，看看我关于公共github项目的帖子，我正在"回答"这个问题。
从正则表达式到DFA的转换非常简单。但是，您将遇到的问题是，生成的DFA可能包含循环(例如，对于*或+)，这将使其无法完全展开。此外，{n,n}不能在DFA中清晰地表示，因为DFA没有循环多少次的"内存"。
这个问题的解决方案将归结为构建一个函数，该函数对正则表达式进行标记和解析，然后返回一个包含所有可能匹配的数组。在这里使用递归将帮助您减少。在伪代码中，起始点可能看起来像:
to GenerateSolutionsFor(regex):
solutions = [""]
for token in TokenizeRegex(regex):
if token.isConstantString:
for sol in solutions: sol.append(token.string)
else if token.isLeftParen:
subregex = get content until matching right paren
subsols = GenerateSolutionsFor(subregex)
for sol in solutions:
for subsol in subsols:
sol.append(subsol)
else if token.isVerticalBar:
solutions.add(GenerateSolutionsFor(rest of the regex))
else if token.isLeftBrace:
...
我想知道如何找到一组与有限数量的匹配给定正则表达式的所有匹配。
因为您只考虑表示有限语言的正则表达式，所以您实际上是考虑字母表上正则表达式的子集。特别是，您不是在处理使用Kleene星号运算符构造的正则表达式。这提出了一种简单的递归算法，用于构造由正则表达式表示的字符串集合，而不包含字母Σ。
LANG(a) = {a} for all a ∈ Σ
LANG(x ∪ y) = LANG(x) ∪ LANG(y)
LANG(xy) = {vw : v ∈ LANG(x) ∧ w ∈ LANG(y)}
考虑一个正则表达式，如a(b ∪ c)d。这正是你的猫和狗例子的结构。执行该算法将正确地确定正则表达式
LANG(a((b ∪ c)d)) = {xy : x ∈ LANG(a) ∧ y ∈ LANG((b ∪ c)d)}
= {xy : x ∈ {a} ∧ y ∈ {vw : v ∈ LANG(b ∪ c) ∧ w ∈ LANG{d}}}
= {ay : y ∈ {vw : v ∈ (LANG(b) ∪ LANG(c)) ∧ w ∈ {d}}}
= {ay : y ∈ {vd : v ∈ {b} ∪ {c}}
= {ay : y ∈ {vd : v ∈ {b,c}}}
= {ay : y ∈ {bd, cd}}
= {abd, acd}
你还问是否存在一种算法来确定正则语言是否是有限的。该算法包括构造接受语言的确定性有限自动机，然后确定过渡图是否包含从起始状态到包含循环的最终状态的行走。注意，没有Kleene星号的正则表达式子集表示有限语言。因为有限集合的并集和连接是有限的，所以这是一个简单的归纳法。
您可能想看看这个Regex库，它解析Regex语法(尽管与perl标准有点不同)并可以从中构建DFA: http://www.brics.dk/automaton/
我已经开始在Github上研究解决方案。它已经可以lex大多数例子，并给出有限正则表达式的解集。
当前通过以下单元测试。
<?php
class RegexCompiler_Tests_MatchTest extends PHPUnit_Framework_TestCase
{
function dataProviderForTestSimpleRead()
{
return array(
array( "^ab$", array( "ab" ) ),
array( "^(ab)$", array( "ab" ) ),
array( "^(ab|ba)$", array( "ab", "ba" ) ),
array( "^(ab|(b|c)a)$", array( "ab", "ba", "ca" ) ),
array( "^(ab|ba){0,2}$", array( "", "ab", "ba", "abab", "abba", "baab", "baba" ) ),
array( "^(ab|ba){1,2}$", array( "ab", "ba", "abab", "abba", "baab", "baba" ) ),
array( "^(ab|ba){2}$", array( "abab", "abba", "baab", "baba" ) ),
array( "^hello?$", array( "hell", "hello" ) ),
array( "^(0|1){3}$", array( "000", "001", "010", "011", "100", "101", "110", "111" ) ),
array( "^[1-9][0-9]{0,1}$", array_map( function( $input ) { return (string)$input; }, range( 1, 99 ) ) ),
array( '^'n$', array( "'n" ) ),
array( '^'r$', array( "'r" ) ),
array( '^'t$', array( "'t" ) ),
array( '^['''''']a''-]$', array( "''", "]", "a", "-" ) ), //the regex is actually '^[''']a'-]$' after PHP string parsing
array( '^[''n-''r]$', array( chr( 10 ), chr( 11 ), chr( 12 ), chr( 13 ) ) ),
);
}
/**
* @dataProvider dataProviderForTestSimpleRead
*/
function testSimpleRead( $regex_string, $expected_matches_array )
{
$lexer = new RegexCompiler_Lexer();
$actualy_matches_array = $lexer->lex( $regex_string )->getMatches();
sort( $actualy_matches_array );
sort( $expected_matches_array );
$this->assertSame( $expected_matches_array, $actualy_matches_array );
}
}
?>
我想建立一个MatchIterator类，可以处理无限列表，以及一个将随机生成匹配从正则表达式。我还想看看从匹配集构建regex作为优化查找或压缩数据的一种方式。
这可能不能回答你所有的问题/需求，但也许这是一个很好的起点。我正在寻找一个解决方案自动生成数据匹配一个regexp前一段时间，我发现这个perl模块Parse::RandGen, Parse::RandGen:: regexp，这工作相当令人印象深刻的好我的需要:
http://metacpan.org/pod/Parse: RandGen