주어진 정규식에 대한 모든 가능한 일치 집합을 만듭니다

Question

일치하는 한정된 수의 주어진 정규식에 모든 일치 집합을 찾는 방법을 알고 싶습니다.

이

이 예를 들어 모든 당신이 수를 검색하는 방법이 있다면 나 또한 관심이있을 것 그들이 ^ 시작 가정 $

`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 

으로 종료 할 수 있습니다 예를 들어

regex에 고유 한 솔루션이 있는지 또는 정규식에 유한 솔루션이 있는지를 판단 할 수있는 방법이 있는지를 확인하십시오.

알고리즘이 모든 정규식을 구문 분석 할 수 있으면 좋겠지 만 정규식의 강력한 하위 집합은 좋을 것입니다.

이 문제에 대한 PHP 솔루션에 관심이 있습니다. 그러나 다른 언어들도 문제가되지 않습니다.

편집 :

내가 정규식 (및 기타 일반 언어)를 구현하는 데 사용할 수 있습니다 DFA에 대한 내 공식 이론 수업 시간에 배운

. 내가 정규 표현식을 DFA로 변환 할 수 있다면 솔직하게 나에게 솔직하게 보인다. 그러나 그 변환은 나에게 다소 까다로운 것처럼 보인다.

편집 2 : 모든 제안

감사합니다, 나는 "대답"이 질문에 일하고 있어요 see my post about the public github project.

Answer 1

나는 작업을 시작했다 solution on 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 클래스를 구축하고 싶습니다. 조회를 최적화하거나 데이터를 압축하는 방법으로 정규식을 구축하는 방법을 살펴보고 싶습니다.

Answer 2

정규 표현식에서 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: 
      ... 

Answer 3

:

출발점은 의사에서처럼 보일 수 있습니다.

만 유한 언어를 나타내는 정규 표현식을 고려하고 있기 때문에, 당신은 알파벳을 통해 정규 표현식의 부분 집합을 고려 실제로입니다. 특히 Kleene 스타 연산자를 사용하여 생성 된 정규 표현식을 다루지 않습니다. 이것은 알파벳 Σ에 대한 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 star가없는 정규 표현식의 서브 세트는 유한 언어를 나타냅니다. 유한 집합의 결합과 결합이 유한하기 때문에, 이것은 쉬운 유도에 따른다.

Answer 4

아마도이 질문은 모든 질문/답변에 대한 대답은 아니지만 좋은 출발점 일 수 있습니다. 나는 이전에 정규 표현식과 일치하는 데이터를 자동으로 생성하는 솔루션을 찾고 있었는데이 Perl 모듈을 찾았습니다. Parse :: RandGen, Parse :: RandGen :: RegExp, 제 요구에 상당히 좋은 결과를 얻었습니다.

http://metacpan.org/pod/Parse::RandGen

Answer 5

당신은 (펄 표준과 다른 조금이라도) 정규식 구문을 구문 분석이 정규식 라이브러리,보고 할 수 있습니다과에서 DFA를 구성 할 수

: http://www.brics.dk/automaton/