W tym zadaniu musisz napisać program, który odczytuje wyrażenie regularne i generuje inny program, który wyświetla, czy wyrażenie wejściowe jest akceptowane przez to wyrażenie regularne. Wyjściem musi być program napisany w tym samym języku, co przesłanie.

Wejście

Dane wejściowe to wyrażenie regularne r pasujące do następującego ABNF (początkowa reguła produkcyjna to REGEX):

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

Jeśli dane wejściowe nie pasują do tej gramatyki, zachowanie Twojego programu jest niezdefiniowane.

Interpretacja

Interpretuj dane wejściowe jako wyrażenie regularne, gdzie *jest gwiazdą Kleene'a (co oznacza powtórzenie lewego argumentu zero lub więcej razy ), |jest alternatywą, (a )grupa i żaden operator w ogóle nie są połączone. Grupowanie ma pierwszeństwo przed gwiazdą, gwiazda ma pierwszeństwo przed konkatenacją, konkatenacja ma pierwszeństwo przed alternatywą.

Mówi się, że ciąg jest akceptowany, jeśli wyrażenie regularne pasuje do całego łańcucha.

Wynik

Dane wyjściowe programu to inny program napisany w tym samym języku co przesłanie, który w czasie wykonywania odczytuje ciąg s w sposób zdefiniowany w implementacji, wyświetla informację, czy r akceptuje s, a następnie kończy działanie. Wyjście może być wykonane w sposób zdefiniowany przez użytkownika, chociaż muszą istnieć tylko dwa różne wyjścia dla programów zaakceptowanych i odrzuconych.

Możesz założyć, że dane wejściowe programu wyjściowego nigdy nie przekraczają 2 ¹⁶ -1 bajtów.

Ograniczenia

Ani twoje zgłoszenie, ani żaden program wygenerowany przez twoje zgłoszenie nie może korzystać z wbudowanych funkcji ani bibliotek, które

• dopasuj wyrażenia regularne
• przekształcać wyrażenia regularne
• kompiluj wyrażenia regularne
• generować parsery z gramatyki
• uprościć problem w taki sposób, aby zgłoszenie stało się banalne

Punktacja

Wynik twojego zgłoszenia to liczba znaków. Zgłoszenie o najniższym wyniku wygrywa.

Przypadki testowe

Wszystkie przypadki testowe zawierają wyrażenie regularne, zestaw zaakceptowanych ciągów, zestaw odrzuconych ciągów i przykładowy program w C99, który jest prawidłowym wyjściem (hipotetycznego) złożenia C99.

(puste wyrażenie regularne)

Akceptowane ciągi

1. (puste wejście)

Odrzucone ciągi

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

Przykładowy program

#include <stdio.h>

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

    return input[0] != 0;
}

(b|)(ab)*(a|)( ai bnaprzemiennie)

akceptowane ciągi znaków

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

odrzucone ciągi

1. afba
2. foo
3. babba

przykładowy program

#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) (binarne liczby zmiennoprzecinkowe)

akceptowane ciągi znaków

1. 10110100
2. 0
3. 1A00001

odrzucone ciągi

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

Rubinowy, 641 651 543 znaków

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

Ta wersja ruby ​​stała się dość długa z powodu kilku przypadków narożnych w parserze wyrażeń regularnych (może powinienem spróbować zastosować inne podejście). Oczekuje wyrażenia regularnego na STDIN i wysyła odpowiedni kod ruby ​​dla dopasowującego do STDOUT.

Program bezpośrednio generuje kod dla NFA-ε który jest następnie wykonywany w module dopasowującym.

Przypadek testowy 1: (dane wyjściowe obejmują dodatkowe znaki nowej linii i wcięcia)

>>>

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

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

Inny przykład:

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

Edycja: Dodano przejście, aby naprawić błąd, który proszę zanotować w komentarzach. Zmieniono także inicjalizację stanu.

C, 627 znaków

Ten program traktuje swój pierwszy argument wiersza poleceń jako dane wejściowe i generuje kod C jako dane wyjściowe.

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

Oto jego wyniki dla (0|1(0|1)*)(|A(0|1)*1)(z dodanymi znakami nowej linii):

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

Jeśli podasz poprawne dane wejściowe jako pierwszy argument wiersza polecenia, zwraca status wyjścia 1. W przeciwnym razie zwraca status wyjścia 0.

$ ./regexcompiler '(0 | 1 (0 | 1) *) (| A (0 | 1) * 1)'> floatprog.c
$ gcc -o floatprog floatprog.c
floatprog.c: W funkcji 'main':
floatprog.c: 1: 519: ostrzeżenie: niekompatybilna niejawna deklaracja wbudowanej funkcji „exit” [domyślnie włączona]
$ ./floatprog '1A00001' && echo niepoprawne || echo ważne
poprawne
$ ./floatprog '100A010' && echo nieprawidłowe ||
nieprawidłowe echo

Każdy program, jeśli nie podasz argumentu wiersza polecenia, odrzuci wskaźnik zerowy, powodując błąd segmentacji. Wystarczająco długi regex przepełni bufory tego przesyłania, a rozmiar danych wejściowych do generowanego programu jest ograniczony przez rozmiar stosu. Jednak wszystkie przypadki testowe działają.

Zauważ, że e(g=h++,C=h++,0,0);wprowadza niezdefiniowane zachowanie. Jeśli na przykład wygenerowane programy nie kompilują się, możesz spróbować zamienić instrukcję na h+=2;e(g=h-1,C=h-2,0,0);, która jest dłuższa o pięć znaków.