Poniższe wyzwanie wymaga znajomości formalnej teorii parsera. Jeśli nie wiesz, o co pyta pytanie, ponieważ nie wiesz, co oznaczają te terminy, gramatyki bezkontekstowe i zestawy pierwsze / następne są objęte wieloma kursami uniwersyteckimi.
Mogę polecić ten kurs Stanford , w szczególności materiały informacyjne 08 i 09 (od strony 7). Wyodrębniłem też ściągawki z tych materiałów - polecam każdemu, kto spróbuje tego wyzwania przeczytać .
Napisz program lub funkcję, która podając gramatykę bezkontekstową znajdzie następujący zestaw każdego nieterminala. Nieoficjalnie następujący zestaw nieterminala jest zestawem terminali i $
(co oznacza koniec wejścia), które można znaleźć po tym terminalu w ważnym zdaniu.
Dane wejściowe są podawane jako pojedynczy drukowalny ciąg ASCII lub tablica drukowalnych wierszy ASCII. Możesz wyprowadzać zestawy w dowolnym rozsądnym formacie, używając $
(jako danych wyjściowych lub ciągów znaków w zestawie itp.), Aby wskazać koniec danych wejściowych. Możesz założyć, że dane wejściowe są zawsze prawidłowe zgodnie z poniższym formatem.
Gramatyka bezkontekstowa jest podana w bardzo uproszczony sposób. Każda linia zawiera jedną produkcję. Każda produkcja jest oddzieloną spacjami listą symboli. Terminal to ciąg znaków otoczony apostrofami (np '**'
.). Dla uproszczenia możesz założyć, że terminale nie zawierają spacji, ale byłoby miło, gdyby twój program na to pozwolił. Nieterminal może być dowolnym ciągiem niezawierającym spacji lub $
. Pusta produkcja (zwykle oznaczana ε) jest po prostu linią zawierającą tylko nieterminalny lewy bok. Pierwszy wiersz to produkcja definiująca symbol początkowy.
Na przykład następująca gramatyka:
S → aSa | bSb | ε
Zostanie podany jako:
S 'a' S 'a'
S 'b' S 'b'
S
Przykładowe wejścia / wyjścia:
In:
S 'a' S 'a'
S 'b' S 'b'
S
Out:
S {'a', 'b', $}
In:
S A B C
A 'a'
A C 'b'
A
B C
B 'd' A
B
C 'e'
C 'f'
Out:
S {$}
A {'d', 'e', 'f'}
B {'e', 'f'}
C {'b', 'e', 'f', $}
In:
Start Alice Bob
Alice Charlie 'a'
Alice
Bob Bob 'a' Alice Charlie
Bob '!!!'
Charlie 'b'
Charlie
Out:
Start {$}
Alice {'a', '!!!', 'b', $}
Bob {'a', $}
Charlie {'a', $}
Najkrótszy kod w bajtach wygrywa.
Odpowiedzi:
Perl, 257 bajtów
Obejmuje +4 za
-0p
Podaj gramatykę na STDIN (bez spacji końcowych. Pamiętaj o usunięciu dodatkowej spacji w drugim przykładzie). Zakłada, że nazwy nieterminalne zawierają tylko litery, cyfry i
_
. Używa#
zamiast$
wskazywać koniec wprowadzania. Może obsługiwać literały zawierające spacjeWysyła następujące zestawy jako listę
non-terminal literal
w określonej kolejności. W powyższym przykładzie wyprowadza:follow.pl
:Działa jak pokazano, ale wymienić
\xd8
i\n
ich dosłowne wersji dostać twierdził wynik.Powinno być możliwe poprawienie tego, ponieważ konwersja
first
zestawów nafollow
zestawy jest obecnie bardzo niewygodna.źródło