Crear un conjunto de todas las coincidencias posibles para una expresión regular dada

Question

Me pregunto cómo encontrar un conjunto de todas las coincidencias para una expresión regular dada con un número finito de coincidencias.

Por ejemplo:

Todos estos ejemplo, usted puede asumir que comienzan con ^ y terminan con $

`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 

Yo también estaría interesado si había una manera de recuperar el recuento soluciones únicas para la expresión regular o si hay una forma de determinar si la expresión regular tiene soluciones finitas.

Sería bueno si el algoritmo pudiera analizar cualquier expresión regular, pero un subconjunto lo suficientemente potente de la expresión regular estaría bien.

Estoy interesado en una solución PHP para este problema, pero otros lenguajes también estarían bien.

EDIT:

que he aprendido en mi clase de teoría formal sobre DFA que puede ser utilizado para implementar expresiones regulares (y otros lenguajes regulares). Si pudiera transformar la expresión regular en un DFA, la solución parece bastante directa para mí, pero esa transformación me parece bastante difícil.

EDIT 2:

Gracias por todas las sugerencias, see my post about the public github project que estoy trabajando a "respuesta" a esta pregunta.

Answer 1

he comenzado a trabajar en una solution on Github. Ya puede leer la mayoría de los ejemplos y dar la solución establecida para finita Regex.

Actualmente pasa las siguientes pruebas unitarias.

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

} 

?> 

me gustaría construir una clase MatchIterator que pudiera manejar listas infinitas, así como uno que generarían al azar partidos de la expresión regular. También me gustaría analizar la generación de expresiones regulares a partir de un conjunto de coincidencias para optimizar las búsquedas o comprimir datos.

Answer 2

La transformación de un regex a un DFA es bastante sencilla. Sin embargo, el problema con el que se encontrará allí es que el DFA generado puede contener bucles (por ejemplo, * o +), lo que impedirá que se expanda por completo. Además, {n,n} no se puede representar limpiamente en un DFA, ya que un DFA no tiene "memoria" de cuántas veces se ha colocado un bucle.

Una solución a este problema se reducirá a la construcción de una función que tokenizes y analiza una expresión regular, y luego devuelve una matriz de todas las posibles coincidencias. El uso de la recursión aquí le ayudará con un lote.

Un punto de partida, en pseudocódigo, podría ser:

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

Me pregunto cómo encontrar un conjunto de todos los partidos de una expresión regular dada con un número finito de partidos.

Debido a que sólo está pensando en expresiones regulares que denotan finitos idiomas, eres realmente considerando un subconjunto de las expresiones regulares sobre un alfabeto. En particular, no se trata de expresiones regulares construidas utilizando el operador de estrellas Kleene. Esto sugiere un algoritmo recursivo simple para construir el conjunto de cadenas denotadas por las expresiones regulares sin Kleene star sobre un alfabeto Σ.

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

Considérese una expresión regular como a(b ∪ c)d. Esta es precisamente la estructura de tu ejemplo de gatos y perros.Ejecutar el algoritmo determinará correctamente el lenguaje denotado por la expresión regular:

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} 

También pregunta si hay un algoritmo que determina si un lenguaje regular es finito. El algoritmo consiste en construir el autómata finito determinista que acepta el idioma, y ​​luego determinar si el gráfico de transición contiene un andar desde el estado de inicio hasta un estado final que contiene un ciclo. Tenga en cuenta que el subconjunto de expresiones regulares construidas sin Kleene star denota lenguajes finitos. Debido a que la unión y la concatenación de conjuntos finitos es finita, esto se deduce por inducción fácil.

Answer 4

Esto probablemente no responda todas sus preguntas/necesidades, pero tal vez sea un buen punto de partida. Estaba buscando una solución para la generación automática de datos que coincida con una expresión regular hace un tiempo, y encontré este módulo Perl Parse :: RandGen, Parse :: RandGen :: RegExp, que funcionó bastante bien para mis necesidades:

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

Answer 5

es posible que desee ver en esta biblioteca expresión regular, que analiza una sintaxis de expresiones regulares (aunque un poco diferente de la norma perl) y puede construir un DFA de ella: http://www.brics.dk/automaton/