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.

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 spacje

perl -M5.010 follow.pl
E T e
e '+' T e
e
T F t
t '*' F t
t
F '(' E ')'
F 'id'
^D

Wysyła następujące zestawy jako listę non-terminal literalw określonej kolejności. W powyższym przykładzie wyprowadza:

F ')'
F #
t ')'
t #
T ')'
T #
F '+'
t '+'
T '+'
F '*'
e ')'
e #
E ')'
E #

follow.pl:

#!/usr/bin/perl -0n
s/'.*?'/~$&/eg;s% (?=(\w.*\n))%$_.=">$1"%reg;/\s/;$_.=">$` #\n";s%^((\w+)\K ?\S*).*%$s{$1}++||"\$a.=s/ $2\\b/$&/rg"%eemgr,s%^(\w+ ).*?(\w+)$%"\$a.=s/>$1/>$2 /rg"%eermg,$_.=$a,s%>.*\xd8\K .*%%g,s%.+\n%$&x!/\n$&/g%eg until$$_++;s/\xd8.*?\xd8/~$&/eg;say/>(\w+ \W\S*\n)/g

Działa jak pokazano, ale wymienić \xd8i \nich dosłowne wersji dostać twierdził wynik.

Powinno być możliwe poprawienie tego, ponieważ konwersja firstzestawów na followzestawy jest obecnie bardzo niewygodna.