Dans cette tâche, vous devez écrire un programme qui lit une expression régulière et génère un autre programme qui affiche si une chaîne d'entrée est acceptée par cette expression régulière. La sortie doit être un programme écrit dans la même langue que votre soumission.

Contribution

L'entrée est une expression régulière r correspondant à l'ABNF suivant (la règle de production initiale est REGEX):

REGEX       = *( STAR / GROUP / LITERAL / ALTERNATIVE )
STAR        = REGEX '*'
GROUP       = '(' REGEX ')'
LITERAL     = ALPHA / DIGIT
ALTERNATIVE = REGEX '|' REGEX

Si l'entrée ne correspond pas à cette grammaire, le comportement de votre programme n'est pas défini.

Interprétation

Interpréter l'entrée comme une expression régulière, où se *trouve l'étoile de Kleene (signifiant répéter l'argument gauche zéro ou plusieurs fois ), |est une alternative (et )regrouper et aucun opérateur du tout concaténé. Le regroupement a la priorité sur l'étoile, l'étoile a la priorité sur la concaténation, la concaténation a la priorité sur l'alternative.

Une chaîne est réputée acceptée si l'expression régulière correspond à la chaîne entière.

Production

La sortie du programme est un autre programme écrit dans le même langage que votre soumission qui lit une chaîne s d'une manière définie par l'implémentation au moment de l'exécution, affiche si r accepte s puis se termine. La sortie peut être effectuée d'une manière définie par l'utilisateur bien qu'il ne doive y avoir que deux sorties distinctes pour les programmes acceptés et rejetés.

Vous pouvez supposer que l'entrée de votre programme de sortie ne dépasse jamais 2 ¹⁶ -1 octets.

Restrictions

Ni votre soumission ni aucun programme généré par votre soumission ne peut utiliser des fonctionnalités intégrées ou des bibliothèques qui

• match regexes
• transformer des expressions régulières
• compiler des expressions régulières
• générer des analyseurs à partir d'une grammaire
• simplifier le problème de manière à ce que votre soumission devienne triviale

Notation

Le score de votre soumission est le nombre de caractères qu'il contient. La soumission avec le score le plus bas gagne.

Cas de test

Toutes les testcases contiennent une expression régulière, un ensemble de chaînes acceptées, un ensemble de chaînes rejetées et un exemple de programme en C99 qui est une sortie valide d'une soumission (hyptothétique) C99.

(expression régulière vide)

Chaînes acceptées

1. (entrée vide)

Chaînes rejetées

1. foo
2. bar
3. baz
4. quux

Exemple de programme

#include <stdio.h>

int main() {
    char input[65536];
    gets(input);

    return input[0] != 0;
}

(b|)(ab)*(a|)( aet en balternance)

chaînes acceptées

1. a
2. ba
3. abababababa
4. abab

chaînes rejetées

1. afba
2. foo
3. babba

exemple de programme

#include <stdio.h>

int main() {
  char input[65536];
  int state = 0;

  for (;;) switch (state) {
    case 0: switch (getchar()) {
      case 'a': state = 1; break;
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 1: switch (getchar()) {
      case 'b': state = 2; break;
      case EOF: return 0;
      default:  return 1;
    } break;
    case 2: switch (getchar()) {
      case 'a': state = 1; break;
      case EOF: return 0;
      default:  return 1;
    } break;
}

(0|1(0|1)*)(|A(0|1)*1) (nombres à virgule flottante binaires)

chaînes acceptées

1. 10110100
2. 0
3. 1A00001

chaînes rejetées

1. 011
2. 10A
3. 1A00
4. 100A010

Ruby, 641 651 543 caractères

H=Hash.new{|h,k|[k]}
d=[[i=0,0,[]]]
o=[?(]
L="t,u,v=d.pop;q,r,s=d.pop;o.pop<?|&&(H[r]<<=t)||(H[q]<<=t;H[r]<<=u);d<<[q,u,s+v]"
gets.chop.chars.map{|c|c==?*&&(q,r,s=d.pop;H[r]|=[q,i+=1];d<<=[r,i,s];next)
eval(L)while/[|)]/=~c ?o[-1]>?(:o[-1]==?.
/[|(]/=~c&&d<<[i+=1,i,o<<c&&[]]||c!=?)&&d<<[i+=1,i+1,["s==#{o<<?.;i}&&c=='#{c}'&&#{i+=1}"]]||o[-1]=?.}
eval(L)while o.size>1
H.map{H.map{|k,v|v.map{|v|H[k]|=H[v]}}}
t,u,v=d[0]
$><<"s=#{H[t]};gets.chop.chars.map{|c|s=s.map{|s|#{v*'||'}}-[!0];#{H.map{|k,v|"s&[#{k}]!=[]&&s|=#{v}"}*?;}};p s&[#{u}]!=[]"

Cette version rubis est devenue assez longue à cause de plusieurs cas d'angle dans l'analyseur d'expressions rationnelles (je devrais peut-être essayer une approche différente). Il attend l'expression régulière sur STDIN et sort le code rubis correspondant pour le matcher vers STDOUT.

Le programme génère directement du code pour un NFA-ε qui est ensuite exécuté dans le matcher.

Cas de test 1: (la sortie comprend des sauts de ligne et une indentation supplémentaires)

>>>

s=[0];
gets.chop.chars.map{|c|
  s=s.map{|s|}-[!0];
};
p s&[0]!=[]

Cas de test 2:

>>> (b|)(ab)*(a|)

s=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
gets.chop.chars.map{|c|
  s=s.map{|s|s==2&&c=='b'&&3||s==6&&c=='a'&&7||s==8&&c=='b'&&9||s==12&&c=='a'&&13}-[!0];
  s&[1]!=[]&&s|=[1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[3]!=[]&&s|=[3, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[0]!=[]&&s|=[0, 1, 2, 4, 9, 5, 10, 6, 11, 12, 14];
  s&[5]!=[]&&s|=[5, 6];
  s&[7]!=[]&&s|=[7, 8];
  s&[9]!=[]&&s|=[9, 5, 10, 6, 11, 12, 14];
  s&[4]!=[]&&s|=[4, 9, 5, 10, 6, 11, 12, 14];
  s&[11]!=[]&&s|=[11, 12, 14];
  s&[13]!=[]&&s|=[13, 14];
  s&[10]!=[]&&s|=[10, 11, 12, 14]
};
p s&[14]!=[]

Un autre exemple:

>>> a|bc

s=[0, 1, 3, 4];
gets.chop.chars.map{|c|
  s=s.map{|s|s==1&&c=='a'&&2||s==4&&c=='b'&&5||s==6&&c=='c'&&7}-[!0];
  s&[0]!=[]&&s|=[0, 1, 3, 4];
  s&[3]!=[]&&s|=[3, 4];
  s&[5]!=[]&&s|=[5, 6];
  s&[2]!=[]&&s|=[2, 7]
};
p s&[7]!=[]

Éditer: Ajout d'une transition pour corriger le bug PleaseStand noté dans les commentaires. Modification également de l'initialisation de l'état.

C, 627 caractères

Ce programme traite son premier argument de ligne de commande comme entrée et génère du code C comme sortie.

#define A(v) F[v]+strlen(F[v])
#define S sprintf
char*B="&&f%d(s)||f%d(s)",*J="&&f%d(s+%d)",*r,F[256][65536];h=2;e(f,n,o,R,C,O,t,g){for(C=O=f;*r;++r)switch(*r){case 40:r++;e(g=h++,C=h++,0,0);r[1]^42?t=g:(t=C,S(A(t),B,g,C=h++),r++);o=!S(A(O),J,t,o);O=C;break;case 41:goto L;case'|':S(A(C),J,n,o);o=!S(A(O=f),"||1");break;default:r[1]^42?S(A(C),"&&s[%d]==%d",o++,*r,O^f||R++):(o=!S(A(O),J,t=h++,o),O=C=h++,g=h++,S(A(g),"&&*s==%d&&f%d(s+1)",*r++,t),S(A(t),B,g,C));}L:S(A(C),J,n,o);}main(int c,char**v){r=v[1];for(e(1,!S(*F,"&&!*s"),0,0);h--;)printf("f%d(char*s){return 1%s;}",h,F[h]);puts("main(int c,char**v){exit(f1(v[1]));}");}

Voici sa sortie pour (0|1(0|1)*)(|A(0|1)*1)(avec ajout de nouvelles lignes):

f11(char*s){return 1&&s[0]==49&&f7(s+1);}
f10(char*s){return 1&&s[0]==48&&f9(s+1)||1&&s[0]==49&&f9(s+1);}
f9(char*s){return 1&&f10(s)||f11(s);}
f8(char*s){return 1&&f7(s+0)||1&&s[0]==65&&f9(s+1);}
f7(char*s){return 1&&f0(s+0);}
f6(char*s){return 1&&f2(s+0);}
f5(char*s){return 1&&s[0]==48&&f4(s+1)||1&&s[0]==49&&f4(s+1);}
f4(char*s){return 1&&f5(s)||f6(s);}
f3(char*s){return 1&&s[0]==48&&f2(s+1)||1&&s[0]==49&&f4(s+1);}
f2(char*s){return 1&&f8(s+0);}
f1(char*s){return 1&&f3(s+0);}
f0(char*s){return 1&&!*s;}
main(int c,char**v){exit(f1(v[1]));}

Si vous fournissez une entrée valide comme premier argument de ligne de commande, elle renvoie l'état de sortie 1. Sinon, elle renvoie l'état de sortie 0.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: Dans la fonction 'main':
floatprog.c: 1: 519: avertissement: déclaration implicite incompatible de la fonction intégrée 'exit' [activée par défaut]
$ ./floatprog '1A00001' && echo invalide || écho valide
valide
$ ./floatprog '100A010' && écho invalide || écho valide
invalide

L'un ou l'autre programme, si vous ne fournissez pas l'argument de ligne de commande, déréférence un pointeur nul, provoquant une erreur de segmentation. Un regex suffisamment long débordera les tampons de cette soumission, et la taille de l'entrée d'un programme généré est limitée par la taille de la pile. Cependant, tous les cas de test fonctionnent.

Notez que e(g=h++,C=h++,0,0);introduit un comportement indéfini. Si, par exemple, les programmes générés ne se compilent pas, vous pouvez essayer de remplacer l'instruction par h+=2;e(g=h-1,C=h-2,0,0);, qui comporte cinq caractères de plus.