Regex en sens inverse - décomposer les expressions régulières

17

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 , donc le code le plus court en octets gagnera!

Poignée de porte
la source
Sommes-nous autorisés à prendre en charge les séquences d'échappement? Alors c'est trivial.
John Dvorak
3
Votre explication de |n'a que très peu de sens. Il ne semble pas gérer les groupes imbriqués ou a|b|c. Quel est le problème avec l'utilisation des explications standard en termes de force de concaténation et d'alternance? (Et vous n'avez aucune excuse pour ne pas utiliser le bac à sable)
Peter Taylor
1
@PeterTaylor En fait, il a une excuse: meta.codegolf.stackexchange.com/q/1305/9498
Justin
2
A en juger par votre exemple, le motif doit correspondre à la chaîne entière? (Par opposition à une sous-chaîne)
Martin Ender
3
@KyleKanos C'est dommage que les problèmes du monde réel ne vous font pas penser que vous devez apprendre les expressions régulières. : P Mais ils ne sont pas aussi inaccessibles que cela puisse paraître: regular-expressions.info/tutorial.html
Martin Ender

Réponses:

8

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.

bazzargh
la source
9

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.

gmatht
la source
9
Je n'ai jamais vu un python aussi horrible.
user80551
Ne pouvez-vous pas changer def E(a,b):c=a[:];c.extend(b);return cpour E=lambda a,b:a[:].extend(b), idem pourA
user80551
Apparemment non, car .extend (b) ne renvoie rien.
gmatht
1
Pour le elif isinstance(e,str):, je pense que vous pouvez changer le code à l'intérieur en: exec{'.':'for c in C:d(r,p,s+chr(c))','?':'d(r,p,s);d(r,p[:z],s)','*':'''c=p[:z]#newline for i in R(0,n+1):d(r,c,s);c+=[p[z]]''','+':"d(r,p+['*',p[z]],s)",'\\':'d(r,p,e[1]+s)'}.get(e,'d(r,p,e+s)')(notez que #newlinec'est une nouvelle ligne) (source: stackoverflow.com/a/103081/1896169 )
Justin
1
Si vous pouviez trouver plus d'endroits pour utiliser l'astuce exec, nous pourrions facilement changer votre code en code illisible :-)
Justin
0

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).
ankh-morpork
la source