Le défi ci-dessous vous oblige à être familier avec la théorie formelle de l'analyseur. Si vous ne savez pas ce que la question pose parce que vous ne savez pas ce que signifient les termes, les grammaires sans contexte et les ensembles premier / suivant sont couverts dans de nombreux cours universitaires.

Je peux recommander ce cours de Stanford , en particulier les documents 08 et 09 (à partir de la page 7). J'ai extrait également extrait une feuille de triche de ces documents - je recommande à tous ceux qui tentent ce défi de le lire .

Écrivez un programme ou une fonction qui, étant donné une grammaire sans contexte, trouve l'ensemble de suivi de chaque non terminal. De manière informelle, l'ensemble suivant d'un terminal non terminal est un ensemble de terminaux et $(signifiant fin d'entrée) que vous pouvez éventuellement trouver après ce terminal dans une phrase valide.

L'entrée est donnée sous la forme d'une seule chaîne ASCII imprimable ou d'un tableau de lignes ASCII imprimables. Vous pouvez sortir les ensembles dans n'importe quel format raisonnable, en utilisant $(soit comme sortie littérale, soit une chaîne à l'intérieur d'un ensemble, etc.) pour indiquer la fin de l'entrée. Vous pouvez supposer que l'entrée est toujours valide selon le format ci-dessous.

La grammaire sans contexte est donnée de manière très simplifiée. Chaque ligne contient une seule production. Chaque production est une liste de symboles séparés par des espaces. Un terminal est une chaîne de caractères entourée d'apostrophes (par exemple '**'). Pour simplifier, vous pouvez supposer que les terminaux ne contiennent pas d'espaces, mais ce serait bien si votre programme le permet. Un non terminal peut être n'importe quelle chaîne ne contenant pas d'espaces ou $. La production vide (normalement indiquée par ε) est simplement une ligne contenant uniquement le côté gauche non terminal. La première ligne est la production définissant le symbole de départ.

À titre d'exemple, la grammaire suivante:

S → aSa | bSb | ε

Sera donné comme:

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

Exemple d'entrées / sorties:

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

Le code le plus court en octets gagne.

Perl, 257 octets

Comprend +4 pour -0p

Donnez de la grammaire sur STDIN (sans espaces de fin. Assurez-vous de supprimer l'espace supplémentaire dans le deuxième exemple). Suppose que les noms non terminaux contiennent uniquement des lettres, des chiffres et _. Utilise #au lieu de $pour indiquer la fin de l'entrée. Peut gérer des littéraux contenant des espaces

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

Sort les ensembles suivants sous forme de liste non-terminal literalsans ordre particulier. Pour l'exemple ci-dessus, il génère:

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

Fonctionne comme indiqué, mais remplacez \xd8et \npar leurs versions littérales pour obtenir le score revendiqué.

Il devrait être possible d'améliorer cela, car la conversion des firstensembles en followensembles est actuellement très délicate.