Utwórz zestaw wszystkich możliwych dopasowań dla danego regex

Question

Zastanawiam się, jak znaleźć zestaw wszystkich dopasowań do danego wyrażenia regularnego ze skończoną liczbą dopasowań.

Na przykład:

Wszystkie te przykład można założyć, że zaczynają się i kończą ^$

`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 

Byłbym również zainteresowany, czy nie było sposobem na zdobycie count unikalne rozwiązanie do wyrażenia regularnego lub jeśli istnieje sposób na określenie, czy regex ma skończone rozwiązania.

Byłoby miło, gdyby algorytm mógł przeanalizować dowolny regex, ale wystarczająco silny podzbiór regex byłby w porządku.

Jestem zainteresowany rozwiązaniem PHP dla tego problemu, ale inne języki również byłyby w porządku.

EDIT:

nauczyłem się w moim formalnej teorii klasie o DFA które mogą być wykorzystane do wdrożenia regex (i innych języków regularnych). Jeśli mógłbym przekształcić wyrażenie regularne w DFA, rozwiązanie wydaje mi się dość proste, ale ta transformacja wydaje mi się trudna.

EDIT 2:

Dzięki za wszystkie sugestie, see my post about the public github project pracuję na "odpowiedź" na to pytanie.

Answer 1

zacząłem pracuje nad solution on Github. Może już pominąć większość przykładów i podać rozwiązanie dla skończonego wyrażenia regularnego.

Aktualnie przechodzi następujące testy jednostkowe.

<?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); 
    } 

} 

?> 

Chciałbym zbudować klasę MatchIterator który mógłby obsłużyć nieskończonej listy, a także taki, który będzie losowo generować mecze z regex. Chciałbym również zagłębić się w budowanie wyrażeń regularnych z zestawu dopasowań, by zoptymalizować wyszukiwanie lub kompresowanie danych.

Answer 2

Przekształcenie z wyrażenia regularnego na DFA jest całkiem proste. Jednak problem z tym związany polega na tym, że wygenerowany DFA może zawierać pętle (np. Dla * lub +), co uniemożliwi pełne rozwinięcie. Ponadto, {n,n} nie może być reprezentowany w czystym DFA, ponieważ DFA nie ma "pamięci" ile razy jest zapętlona.

Rozwiązaniem tego problemu jest zbudowanie funkcji, która tokenizuje i parsuje wyrażenie regularne, a następnie zwraca tablicę wszystkich możliwych dopasowań. Korzystanie z rekurencji pomoże ci uzyskać część.

Punktem wyjścia w Pseudokod, może wyglądać następująco:

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

Zastanawiam się, jak znaleźć zbiór wszystkich meczów na danym regex ze skończonej liczby meczów.

Bo bierzesz pod uwagę tylko wyrażeń regularnych oznaczających skończone języki, jesteś faktycznie rozważa podzbiór wyrażeń regularnych nad alfabetem. W szczególności nie mamy do czynienia z wyrażeń regularnych skonstruowanych przy użyciu operatora gwiazdy Kleene. Sugeruje to prosty algorytm rekurencyjny do skonstruowania zbioru ciągów oznaczonych przez wyrażenia regularne bez gwiazdy Kleene nad alfabetem Σ.

LANG(a)  = {a} for all a ∈ Σ 
LANG(x ∪ y) = LANG(x) ∪ LANG(y) 
LANG(xy) = {vw : v ∈ LANG(x) ∧ w ∈ LANG(y)} 

Należy wziąć pod uwagę wyrażenie regularne, takie jak a(b ∪ c)d. Taka jest właśnie struktura twoich kotów i psów.Wykonywanie algorytmu będzie poprawnie określić język oznaczony przez wyrażenie regularne:

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} 

również zapytać, czy istnieje algorytm, który określa, czy język regularny jest skończona. Algorytm polega na skonstruowaniu deterministycznego skończonego automatu akceptującego język, a następnie ustaleniu, czy wykres przejścia zawiera spacer od stanu początkowego do stanu końcowego zawierającego cykl. Zauważ, że podzbiór wyrażeń regularnych skonstruowanych bez gwiazdy Kleene oznacza skończone języki. Ponieważ zjednoczenie i konkatenacja zbiorów skończonych jest skończona, wynika to z łatwej indukcji.

Answer 4

To prawdopodobnie nie odpowiada na wszystkie pytania/potrzeby, ale może to dobry punkt wyjścia. Szukałem rozwiązania do automatycznego generowania danych, które pasuje do regexp jakiś czas temu, i znalazłem ten moduł perla Parse :: RandGen, Parse :: RandGen :: RegExp, który pracował całkiem imponująco dobrze dla moich potrzeb:

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

Answer 5

Możecie zajrzeć do tej biblioteki regex, który analizuje składnię regex (choć trochę różni się od standardowego perl) i można skonstruować DFA od niego: http://www.brics.dk/automaton/