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 16 -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
- (puste wejście)
Odrzucone ciągi
- bla
- bar
- baz
- quux
Przykładowy program
#include <stdio.h>
int main() {
char input[65536];
gets(input);
return input[0] != 0;
}
(b|)(ab)*(a|)
( a
i b
naprzemiennie)
akceptowane ciągi znaków
a
ba
abababababa
abab
odrzucone ciągi
afba
foo
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
- 10110100
- 0
- 1A00001
odrzucone ciągi
- 011
- 10 A
- 1A00
- 100A010
return (regex.match(stdin) is not null)
jest niedozwolone.Odpowiedzi:
Rubinowy,
641651543 znakówTa 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)
Przypadek testowy 2:
Inny przykład:
Edycja: Dodano przejście, aby naprawić błąd, który proszę zanotować w komentarzach. Zmieniono także inicjalizację stanu.
źródło
011
dla wyrażeń regularnych(0|1(0|1)*)(|A(0|1)*1)
powodujetrue
- powinno byćfalse
.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.
Oto jego wyniki dla
(0|1(0|1)*)(|A(0|1)*1)
(z dodanymi znakami nowej linii):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.
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ę nah+=2;e(g=h-1,C=h-2,0,0);
, która jest dłuższa o pięć znaków.źródło