El desafío a continuación requiere que esté familiarizado con la teoría del analizador formal. Si no sabe qué es la pregunta porque no sabe qué significan los términos, las gramáticas sin contexto y los conjuntos de primero / siguiente están cubiertos en muchos cursos universitarios.

Puedo recomendar este curso de Stanford , en particular los folletos 08 y 09 (de la página 7). También he extraído una hoja de trucos de estos folletos. Recomiendo a cualquiera que intente este desafío leerlo .

Escribir un programa o función que, dada una gramática libre de contexto, encuentre el siguiente conjunto de cada no terminal. Informalmente, el siguiente conjunto de un no terminal es un conjunto de terminales y $(es decir, el final de la entrada) que posiblemente pueda encontrar después de ese terminal en una oración válida.

La entrada se proporciona como una sola cadena ASCII imprimible o conjunto de líneas ASCII imprimibles. Puede generar los conjuntos en cualquier formato razonable, utilizando $(ya sea como salida literal o cadena dentro de un conjunto, etc.) para indicar el final de la entrada. Puede suponer que la entrada siempre es válida de acuerdo con el siguiente formato.

La gramática libre de contexto se da de una manera muy simplificada. Cada línea contiene una sola producción. Cada producción es una lista de símbolos separados por espacios. Una terminal es una cadena de caracteres rodeada de apóstrofes (por ejemplo '**'). Para simplificar, puede suponer que los terminales no contienen espacios, pero sería bueno si su programa lo permite. Un no terminal puede ser cualquier cadena que no contenga espacios o $. La producción vacía (normalmente indicada con ε) es simplemente una línea que contiene solo el lado izquierdo no terminal. La primera línea es la producción que define el símbolo de inicio.

Como ejemplo, la siguiente gramática:

S → aSa | bSb | ε

Se dará como:

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

Ejemplo de entradas / salidas:

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

El código más corto en bytes gana.

Perl, 257 bytes

Incluye +4 para -0p

Dé gramática en STDIN (sin espacios finales. Asegúrese de eliminar el espacio adicional en el segundo ejemplo). Asume que los nombres no terminales solo contienen letras, dígitos y _. Utiliza en #lugar de $indicar el final de la entrada. Puede manejar literales que contienen espacios

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

Muestra los siguientes conjuntos como una lista non-terminal literalsin ningún orden en particular. Para el ejemplo anterior, genera:

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

Funciona como se muestra, pero reemplaza \xd8y \npor sus versiones literales para obtener la puntuación reclamada.

Debería ser posible mejorar esto, ya que convertir los firstconjuntos a los followconjuntos es actualmente muy incómodo.