Le problème

J'ai un tas d'expressions régulières que je dois utiliser dans du code, mais j'utilise un langage de programmation qui ne prend pas en charge l'expression régulière! Heureusement, je sais que la chaîne de test aura une longueur maximale et sera composée uniquement d'ASCII imprimable.

Le défi

Vous devez saisir une expression régulière et un nombre n, et sortir chaque chaîne composée d'ASCII imprimables (codes ASCII 32 à 126 inclus, à ~, sans tabulations ni sauts de ligne) d'une longueur inférieure ou égale à ncelle correspondant à cette expression régulière. Vous ne pouvez pas utiliser du tout d'expressions régulières intégrées ou de fonctions de correspondance d'expressions rationnelles dans votre code. Les expressions régulières seront limitées aux suivantes:

• Caractères littéraux (et les échappements, qui forcent un caractère à être littéral, \.est donc un littéral ., \nest un littéral n(équivalent à juste n) et \west équivalent à w. Vous n'avez pas besoin de prendre en charge les séquences d'échappement.)
• . - caractère générique (n'importe quel caractère)
• Classes de caractères, [abc]signifie "a ou b ou c" et [d-f]signifie n'importe quoi de d à f (donc, d ou e ou f). Les seuls caractères qui ont une signification particulière dans une classe de caractères sont [et ](qui seront toujours échappés, alors ne vous inquiétez pas), \(le caractère d'échappement, bien sûr), ^au début de la classe de caractères (qui est une négation ), et- (qui est une plage).
• |- l'opérateur OR, alternance. foo|barsignifie soit fooou bar, et (ab|cd)ecorrespond soitabe ou cde.
• * - faire correspondre le jeton précédent répété zéro ou plusieurs fois, gourmand (il essaie de répéter autant de fois que possible)
• + - répété une ou plusieurs fois, gourmand
• ? - zéro ou une fois
• Regroupement avec des parenthèses, aux jetons de groupe pour |, *. +, ou?

La regex d'entrée sera toujours valide (c'est-à-dire que vous n'avez pas à gérer une entrée comme ?abcou (fooou toute entrée non valide). Vous pouvez sortir les chaînes dans l'ordre que vous souhaitez, mais chaque chaîne ne doit apparaître qu'une seule fois (ne pas sortir de doublons).

Les cas de test

Entrée: .*, 1
sortie: (chaîne vide), , !, ", ..., },~

Entrée: w\w+, 3
sortie: ww,www

Entrée: [abx-z][^ -}][\\], 3
sortie: a~\, b~\, x~\, y~\,z~\

Entrée: ab*a|c[de]*, 3
sortie: c, cd, ce, aa, cde, ced, cdd, cee,aba

Entrée: (foo)+(bar)?!?, 6
sortie: foo, foo!, foofoo,foobar

Entrée: (a+|b*c)d, 4
sortie: ad, cd, aad, bcd, aaad,bbcd

Entrée: p+cg, 4
sortie: pcg,ppcg

Entrée: a{3}, 4
sortie:a{3}

Le gagnant

C'est du code-golf , donc le code le plus court en octets gagnera!

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

production:

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}"]

Explication: celle-ci est une implémentation d'expressions régulières. R est le type regex, avec les constructeurs A (alternatif), L (littéral), T (puis) ​​et E (vide / epsilon). Le 'Star' habituel n'apparaît pas parce que je l'inline en alternance pendant l'analyse (voir '%'). 'm' exécute la simulation. L'analyseur (commencer à 'rs = ....') n'est qu'une descente récursive; «k» analyse les plages. La fonction '#' étend les plages en alternances.

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

Cette réponse semble assez longue pour un golf de code, mais il y a beaucoup d'opérateurs qui doivent être traités et je sais à quoi sert chaque octet de cette réponse. Puisqu'il n'y a pas de réponse existante, je soumets cela comme un objectif à battre pour les autres utilisateurs. Voyez si vous pouvez faire une réponse plus courte :).

Les deux fonctions principales sont celles fqui analysent l'expression rationnelle en commençant par le ie caractère et dqui génèrent les chaînes correspondantes, en utilisant rles sous-expressions rationnelles dans lesquelles nous pouvons récurser, `` a '' le tableau représentant la partie de la sous-expression rationnelle actuelle non encore traitée, et un suffixe de chaîne squi représente la partie de la chaîne générée jusqu'à présent.

Consultez également l' échantillon de sortie et un faisceau de test .

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],"")

Notez que les onglets de la solution d'origine ont été expandédités. Pour compter le nombre de caractères dans l'utilisation d'origine unexpand < regex.py | wc.

Prolog (SWI) , 590 octets

La capacité de retour en arrière intégrée de Prolog en fait un choix génial pour ce défi. En tirant parti du retour arrière, la génération de chaînes pour une expression régulière devient exactement la même tâche que de tester si une chaîne est mise en correspondance par une expression régulière. Malheureusement, une grande partie de mon effort de golf a été consacrée à l'écriture d'analyseurs regex plus courts. La tâche réelle de décomposer une expression régulière, nous avons facilement joué au golf.

R-L-S:-R*A,-(B,A,[]),setof(Z,(0/L/M,length(C,M),C+B+[],Z*C),S).
-R-->e+S,S-R.
R-T-->{R=T};"|",e+S,u+R+S-T.
Z+Y-->(".",{setof(C,32/126/C,R)};"[^",!,\E,"]",{setof(C,(32/126/C,\+C^E),R)};"[",\R,"]";"(",-R,")";{R=[C]},([C],{\+C^`\\.[|+?*(`};[92,C])),("*",{S=k(R)};"+",{S=c+R+k(R)};"?",{S=u+e+R};{S=R}),({Y=c+Z+S};c+Z+S+Y).
\C-->{C=[H|T]},+H,\T;{C=[]};+A,"-",+B,\T,{setof(C,A/B/C,H),append(H,T,C)}.
+C-->[92,C];[C],{\+C^`\\]-`}.
S+e+S.
[C|S]+D+S:-C^D.
S+(B+L+R)+T:-B=c,!,S+L+U,U+R+T;S+L+T;S+R+T.
S+k(K)+U:-S=U;S+K+T,S\=T,T+k(K)+U.
A/B/C:-between(A,B,C).
A^B:-member(A,B).
A*B:-string_codes(A,B).

Le prédicat -\3peut être invoqué avec les deux premiers arguments instanciés pour générer les chaînes correspondant à une expression régulière.

?- "[abx-z][^ -}][\\\\]"-3-S.
S = ["a~\\"] ;
S = ["b~\\"] ;
S = ["x~\\"] ;
S = ["y~\\"] ;
S = ["z~\\"] ;
false.

Essayez-le en ligne!

Code non golfé

generate_string(R, L, S) :-
    % parse regex
    string_codes(R, RC),
    regex_union(RE, RC, []),

    % bound string length
    between(0, L, M),
    length(SC, M),

    % find string
    match(SC, RE, []),

    string_codes(S, SC).

% Parsers
%%%%%%%%%  

regex_union(R) -->regex_concat(S), regex_union1(S, R).

regex_union1(R,T) --> [124], regex_concat(S), regex_union1(regex_union(R,S), T).
regex_union1(R, R) --> [].

regex_concat(R) --> regex_op(S), regex_concat1(S, R).

regex_concat1(R, T) --> regex_op(S), regex_concat1(regex_concat(R,S), T).
regex_concat1(R, R) --> [].

regex_op(regex_kleene(R)) --> regex_lit(R), [42].
regex_op(regex_concat(R,regex_kleene(R))) --> regex_lit(R), [43].
regex_op(regex_union(regex_empty,R)) --> regex_lit(R), [63].
regex_op(R) --> regex_lit(R).

regex_lit(regex_char([C])) --> [C], {\+ regex_ctrl(C)}.
regex_lit(regex_char([C])) --> [92], [C].

regex_lit(regex_char(CS)) --> [46], {findall(C, between(32,126, C), CS)}.

regex_lit(regex_char(DS)) --> 
    [91], [94], !, class_body(CS), [93],
    {findall(C, (between(32, 126, C), \+ member(C, CS)), DS)}.
regex_lit(regex_char(CS)) --> [91], class_body(CS), [93].

regex_lit(R) --> [40], regex_union(R), [41].

class_body([C|T]) --> class_lit(C),class_body(T).
class_body(CS) -->
    class_lit(C0), [45], class_lit(C1), class_body(T),
    {findall(C, between(C0, C1, C), H), append(H,T,CS)}.
class_body([]) --> [].

class_lit(C) --> [C], {\+ class_ctrl(C)}.
class_lit(C) --> [92], [C].

class_ctrl(C) :- string_codes("\\[]-", CS), member(C, CS).
regex_ctrl(C) :- string_codes("\\.[]|+?*()", CS), member(C, CS).

% Regex Engine
%%%%%%%%%%%%%% 

% The regex empty matches any string without consuming any characters.
match(S, regex_empty, S).

% A regex consisting of a single character matches any string starting with
% that character. The chanter is consumed.
match([C|S], regex_char(CS), S) :- member(C, CS).

% A union of two regex only needs to satisify one of the branches.
match(S, regex_union(L,R), T) :- match(S, L, T); match(S, R, T).     

% A concat of two regex must satisfy the left and then the right.
match(S, regex_concat(L, R), U) :- match(S, L, T), match(T, R, U).

% The kleene closure of a regex can match the regex 0 times or it can the regex
% once before matching the kleene closure again.
match(S, regex_kleene(_), S).
match(S, regex_kleene(K), U) :- match(S, K, T), S \= T, match(T, regex_kleene(K), U).