Die folgende Herausforderung erfordert, dass Sie mit der formalen Parsertheorie vertraut sind. Wenn Sie nicht wissen, was die Frage ist, weil Sie nicht wissen, was die Begriffe bedeuten, werden in vielen Universitätskursen kontextfreie Grammatiken und First / Follow-Sets behandelt.

Ich kann diesen Stanford-Kurs empfehlen , insbesondere die Handouts 08 und 09 (ab Seite 7). Ich habe auch einen Spickzettel aus diesen Handouts extrahiert. Ich empfehle jedem, der diese Herausforderung versucht, sie zu lesen .

Schreiben Sie ein Programm oder eine Funktion, die bei einer kontextfreien Grammatik die Folgemenge jedes Nichtterminals findet. Informell ist die folgende Menge eines Nichtterminals eine Menge von Terminals und $(was das Ende der Eingabe bedeutet), die Sie möglicherweise nach diesem Terminal in einem gültigen Satz finden können.

Die Eingabe erfolgt als einzelne druckbare ASCII-Zeichenfolge oder als Array druckbarer ASCII-Zeilen. Sie können die Sätze in jedem vernünftigen Format ausgeben, indem Sie $(entweder als Literalausgabe oder als Zeichenfolge in einem Satz usw.) das Ende der Eingabe angeben. Sie können davon ausgehen, dass die Eingabe immer im unten angegebenen Format gültig ist.

Die kontextfreie Grammatik wird sehr vereinfacht angegeben. Jede Linie enthält eine einzelne Produktion. Jede Produktion ist eine durch Leerzeichen getrennte Liste von Symbolen. Ein Terminal ist eine Zeichenfolge, die von Apostrophen umgeben ist (z '**'. B. ). Der Einfachheit halber können Sie davon ausgehen, dass Terminals keine Leerzeichen enthalten, aber es wäre schön, wenn Ihr Programm dies zulässt. Ein Nichtterminal kann eine beliebige Zeichenfolge sein, die keine Leerzeichen oder enthält $. Die leere Produktion (normalerweise mit ε gekennzeichnet) ist einfach eine Zeile, die nur das linke Nicht-Terminal enthält. Die erste Zeile ist die Produktion, die das Startsymbol definiert.

Als Beispiel die folgende Grammatik:

S → aSa | bSb | ε

Wird angegeben als:

S 'a' S 'a'
S 'b' S 'b'
S

Beispiel Ein- / Ausgänge:

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', $}

Kürzester Code in Bytes gewinnt.

Perl, 257 Bytes

Beinhaltet +4 für -0p

Geben Sie die Grammatik für STDIN an (ohne nachfolgende Leerzeichen. Entfernen Sie das zusätzliche Leerzeichen im zweiten Beispiel). Nimmt an, dass Namen von Nicht-Terminals nur Buchstaben, Ziffern und enthalten _. Wird #anstelle von verwendet $, um das Ende der Eingabe anzuzeigen. Kann mit Literalen umgehen, die Leerzeichen enthalten

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

Gibt die folgenden Sätze in einer Liste non-terminal literalohne bestimmte Reihenfolge aus. Für das obige Beispiel gibt es Folgendes aus:

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

Funktioniert wie gezeigt, aber ersetzen Sie \xd8und \ndurch ihre Literalversionen, um die beanspruchte Punktzahl zu erhalten.

Es sollte möglich sein, dies zu verbessern, da das Konvertieren der firstSätze in die followSätze derzeit sehr umständlich ist.