El problema

¡Tengo un montón de expresiones regulares que necesito usar en algún código, pero estoy usando un lenguaje de programación que no admite expresiones regulares! Afortunadamente, sé que la cadena de prueba tendrá una longitud máxima y estará compuesta solo de ASCII imprimible.

El reto

Debe ingresar una expresión regular y un número n, y generar cada cadena compuesta de ASCII imprimible (códigos ASCII 32 a 126 inclusive, a ~, sin pestañas o nuevas líneas) de longitud menor o igual que nesa coincidencia con esa expresión regular. Es posible que no utilizar construido en expresiones regulares o funciones coincidentes de expresiones regulares en su código. Las expresiones regulares se limitarán a lo siguiente:

• Caracteres literales (y escapes, que obligan a un carácter a ser literal, por lo que \.es un literal ., \nes un literal n(equivalente a just n) y \wes equivalente a w. No es necesario admitir secuencias de escape).
• . - comodín (cualquier personaje)
• Clases de caracteres, [abc]significa "a o b o c" y [d-f]significa cualquier cosa de d a f (entonces, d o e o f). Los únicos caracteres que tienen un significado especial en una clase de caracteres son [y ](que siempre se \escaparán , así que no se preocupe por eso), (el carácter de escape, por supuesto),^ al comienzo de la clase de caracteres (lo cual es una negación ) y -(que es un rango).
• |- el operador OR, alternancia. foo|barsignifica fooo bar, y (ab|cd)ecoincide con abeocde .
• * - coincide con el token anterior repetido cero o más veces, codicioso (intenta repetir tantas veces como sea posible)
• + - repetido una o más veces, codicioso
• ? - cero o una vez
• Agrupación con paréntesis, a fichas de grupo para |, *.+o?

La expresión regular de entrada siempre será válida (es decir, no tiene que manejar entradas como ?abco(foo o cualquier entrada no válida). Puede generar las cadenas en el orden que desee, pero cada cadena debe aparecer solo una vez (no generar duplicados).

Los casos de prueba

Entrada: .*, 1
Salida: (cadena vacía), , !, ", ...,} ,~

Entrada: w\w+, 3
Salida:ww,www

Entrada: [abx-z][^ -}][\\], 3
Salida: a~\, b~\, x~\,y~\ ,z~\

Entrada: ab*a|c[de]*, 3
Salida: c, cd, ce, aa, cde, ced, cdd,cee ,aba

Entrada: (foo)+(bar)?!?, 6
Salida: foo, foo!, foofoo,foobar

Entrada: (a+|b*c)d, 4
Salida: ad, cd, aad, bcd, aaad,bbcd

Entrada: p+cg, 4
Salida: pcg,ppcg

Entrada: a{3}, 4
Salida:a{3}

El ganador

Este es el código de golf , por lo que el código más corto en bytes ganará.

Haskell 757 705 700 692 679 667

import Data.List
data R=L Char|A R R|T R R|E
h=[' '..'~']
k(']':s)a=(a,s)
k('^':s)_=l$k[]s
k('-':c:s)(a:b)=k([a..c]++b)s
k('\\':c:s)a=k s$c:a
k(c:s)a=k s$c:a
l(a,b)=(h\\a,b)
c#E=L c
c#r=A(L c)r
o(a,b)=(foldr(#)E a,b)
t%0=E
t%n=A(t%(n-1))$T t$t%(n-1)
d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s$m r a;r s=w$e s E;w(u,'|':v)=(\(a,b)->(A u a,b))$r v;w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f$b s;e[]t=(t,[]);g t(u,v)=e v$T t u;f(t,'*':s)=(t%n,s);f(t,'+':s)=(T t$t%n,s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o$k s[];b(s:t)=(L s,t)}

salida:

ghci> d ".*" 1
[""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"]
ghci> d "w\\w+" 3
["ww","www"]
ghci> d "[abx-z][^ -}][\\\\]" 3
["x~\\","y~\\","z~\\","b~\\","a~\\"]
ghci> d "ab*a|c[de]*" 3
["aa","aba","c","ce","cd","cee","cde","ced","cdd"]
ghci> d "(foo)+(bar)?!?" 6
["foo!","foobar","foo","foofoo"]
ghci> d "(a+|b*c)d" 4
["ad","aad","aaad","cd","bcd","bbcd"]
ghci> d "p+cg" 4
["pcg","ppcg"]
ghci> d "a{3}" 4
["a{3}"]

Explicación: esta es una implementación de expresiones regulares de libros de texto. R es el tipo de expresiones regulares, con los constructores A (alternativo), L (literal), T (luego) y E (vacío / épsilon). La 'estrella' habitual no aparece porque la alineo como alternativa durante el análisis (ver '%'). 'm' ejecuta la simulación. El analizador (comienza en 'rs = ....') es solo un descenso recursivo; 'k' analiza los rangos. La función '#' expande los rangos en alternancias.

Python v2.7 1069 1036 950 925 897 884 871 833 822

Esta respuesta parece bastante larga para un código de golf, pero hay muchos operadores que deben manejarse y sé qué propósito tiene cada byte en esta respuesta. Como no hay una respuesta existente, presento esto como un objetivo para que otros usuarios lo superen. Vea si puede hacer una respuesta más corta :).

Las dos funciones principales son las fque analizan la expresión regular que comienza en el icarácter th, y la dque genera las cadenas coincidentes, utilizando rlas sub-expresiones regulares en las que podemos recurrir, 'a' la matriz que representa la parte de la expresión regular actual que aún no se procesó, y un sufijo de cadena sque representa la parte de la cadena generada hasta ahora.

También verifique la salida de muestra y un arnés de prueba .

import sys;V=sys.argv;n=int(V[2]);r=V[1];S=len;R=range;C=R(32,127)
Z=[];z=-1;D='d(r,p,';F='for j in '
def f(i,a):
 if i>=S(r):return a,i
 c=r[i];x=0;I="|)]".find(c)
 if c in"([|":x,i=f(i+1,Z)
 if I+1:return([c,a,x],[a],[c,a])[I],i
 if'\\'==c:i+=1;x=c+r[i]
 return f(i+1,a+[x or c])
def d(r,a,s):
 if S(s)>n:return
 while a==Z:
        if r==Z:print s;return
        a=r[z];r=r[:z]
 e=a[z];p=a[0:z]
 if'|'==a[0]:d(r,a[1],s);d(r,a[2],s)
 elif']'==a[0]:
        g=a[1];N=g[0]=='^';g=(g,g[1:])[N];B=[0]*127;O=[ord(c[z])for c in g]
        for i in R(0,S(g)):
         if'-'==g[i]:exec F+'R(O[i-1],O[i+1]):B[j]=1'
         else:B[O[i]]=1
        for c in C:N^B[c]<1or d(r,Z,chr(c)+s)
 elif' '>e:d(r+[p],e,s)
 else:c=p[:z];exec{'.':F+'C:'+D+'chr(j)+s)','?':D+'s);d(r,p[:z],s)','*':F+'R(0,n+1):d(r,c,s);c+=[p[z]]','+':"d(r,p+['*',p[z]],s)"}.get(e,D+'e[z]+s)')
d(Z,f(0,Z)[0],"")

Tenga en cuenta que las pestañas en la solución original se han expandeditado. Para contar el número de caracteres en el uso original unexpand < regex.py | wc.