In dieser Aufgabe müssen Sie ein Programm schreiben, das einen regulären Ausdruck liest und ein anderes Programm generiert, das ausgibt, ob eine Eingabezeichenfolge von diesem regulären Ausdruck akzeptiert wird. Die Ausgabe muss ein Programm sein, das in derselben Sprache wie Ihre Einreichung geschrieben ist.

Eingang

Der Eingang ist ein regulärer Ausdruck r die folgende ABNF Matching (die anfängliche Produktionsregel ist REGEX):

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

Wenn die Eingabe nicht mit dieser Grammatik übereinstimmt, ist das Verhalten Ihres Programms undefiniert.

Deutung

Die Eingabe als regulären Ausdruck interpretieren, wobei *der Kleene-Stern (dh das Argument links null oder mehrmals wiederholen ) |eine Alternative darstellt (und eine )Gruppe und überhaupt kein Operator verkettet ist. Gruppierung hat Vorrang vor Stern, Stern hat Vorrang vor Verkettung, Verkettung hat Vorrang vor Alternative.

Eine Zeichenfolge gilt als akzeptiert, wenn der reguläre Ausdruck mit der gesamten Zeichenfolge übereinstimmt.

Ausgabe

Die Ausgabe des Programms ist ein anderes Programm, das in derselben Sprache wie Ihre Einreichung geschrieben ist und das zur Laufzeit einen String s in einer durch die Implementierung definierten Weise liest , ausgibt, ob r s akzeptiert und dann beendet. Die Ausgabe kann auf benutzerdefinierte Weise erfolgen, obwohl es für akzeptierte und abgelehnte Programme nur zwei unterschiedliche Ausgaben geben muss.

Sie können davon ausgehen, dass die Eingabe Ihres Ausgabeprogramms niemals länger als 2 ¹⁶ -1 Bytes ist.

Beschränkungen

Weder Ihr Beitrag noch ein von Ihrem Beitrag erstelltes Programm dürfen eingebaute Funktionen oder Bibliotheken verwenden, die

• Spiel Regexes
• reguläre Ausdrücke transformieren
• kompiliere reguläre Ausdrücke
• Parser aus einer Grammatik generieren
• Vereinfachen Sie das Problem auf eine Weise, dass Ihre Eingabe trivial wird

Wertung

Die Punktzahl Ihrer Einreichung ist die Anzahl der Zeichen. Die Einsendung mit der niedrigsten Punktzahl gewinnt.

Testfälle

Alle Testfälle enthalten einen regulären Ausdruck, eine Reihe akzeptierter Zeichenfolgen, eine Reihe abgelehnter Zeichenfolgen und ein Beispielprogramm in C99, das eine gültige Ausgabe einer (hyptothetischen) C99-Übermittlung darstellt.

(leerer regulärer Ausdruck)

Akzeptierte Zeichenfolgen

1. (leere Eingabe)

Abgelehnte Zeichenfolgen

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

Beispielprogramm

#include <stdio.h>

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

    return input[0] != 0;
}

(b|)(ab)*(a|)( aund babwechselnd)

akzeptierte Zeichenfolgen

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

abgelehnte Zeichenfolgen

1. afba
2. foo
3. babba

Beispielprogramm

#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) (binäre Gleitkommazahlen)

akzeptierte Zeichenfolgen

1. 10110100
2. 0
3. 1A00001

abgelehnte Zeichenfolgen

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

Ruby, 641 651 543 Zeichen

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}]!=[]"

Diese rubinrote Version wurde aufgrund mehrerer Eckfälle im Regex-Parser ziemlich lang (vielleicht sollte ich einen anderen Ansatz ausprobieren). Es erwartet den regulären Ausdruck für STDIN und gibt den entsprechenden Ruby-Code für den Matcher an STDOUT aus.

Das Programm generiert direkt Code für ein NFA-ε, das dann im Matcher ausgeführt wird.

Testfall 1: (Ausgabe enthält zusätzliche Zeilenumbrüche und Einrückungen)

>>>

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

Testfall 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]!=[]

Ein anderes Beispiel:

>>> 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]!=[]

Bearbeiten: Es wurde ein Übergang hinzugefügt, um den in den Kommentaren angegebenen Fehler PleaseStand zu beheben . Auch Statusinitialisierung geändert.

C 627 Zeichen

Dieses Programm behandelt sein erstes Befehlszeilenargument als Eingabe und generiert C-Code als Ausgabe.

#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]));}");}

Hier ist die Ausgabe für (0|1(0|1)*)(|A(0|1)*1)(mit hinzugefügten Zeilenumbrüchen):

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

Wenn Sie als erstes Befehlszeilenargument eine gültige Eingabe angeben, wird der Beendigungsstatus 1 zurückgegeben. Andernfalls wird der Beendigungsstatus 0 zurückgegeben.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: In Funktion 'main':
floatprog.c: 1: 519: Warnung: Inkompatible implizite Deklaration der integrierten Funktion 'exit' [standardmäßig aktiviert]
$ ./floatprog '1A00001' && echo invalid || echo valid
valid
$ ./floatprog '100A010' && echo invalid || Echo gültig
ungültig

Wenn Sie das Befehlszeilenargument nicht angeben, wird in beiden Programmen ein Nullzeiger dereferenziert, wodurch ein Segmentierungsfehler verursacht wird. Ein ausreichend langer regulärer Ausdruck überläuft die Puffer dieser Übermittlung, und die Größe der Eingabe in ein generiertes Programm ist durch die Größe des Stapels begrenzt. Alle Testfälle funktionieren jedoch.

Beachten Sie, dass e(g=h++,C=h++,0,0);undefiniertes Verhalten eingeführt wird. Wenn beispielsweise generierte Programme nicht kompiliert werden können, können Sie versuchen, die Anweisung durch h+=2;e(g=h-1,C=h-2,0,0);eine fünf Zeichen längere Anweisung zu ersetzen .