O desafio abaixo exige que você esteja familiarizado com a teoria formal do analisador. Se você não sabe o que a pergunta está perguntando, porque não sabe o que significam os termos, gramáticas sem contexto e conjuntos de primeiro / seguir são abordados em muitos cursos universitários.

Posso recomendar este curso de Stanford , em particular os folhetos 08 e 09 (da página 7). Também extraí uma folha de dicas dessas apostilas - recomendo que qualquer um que tente esse desafio a leia .

Escreva um programa ou função que, dada uma gramática livre de contexto, encontre o seguinte conjunto de todos os termos não terminais. Informalmente, o conjunto a seguir de um $termo não terminal é um conjunto de terminais e (que significa final de entrada) que você pode encontrar após esse terminal em uma frase válida.

A entrada é fornecida como uma única sequência ASCII imprimível ou matriz de linhas ASCII imprimíveis. Você pode emitir os conjuntos em qualquer formato razoável, usando $(como saída literal ou string dentro de um conjunto, etc.) para indicar o final da entrada. Você pode assumir que a entrada é sempre válida de acordo com o formato abaixo.

A gramática livre de contexto é dada de uma maneira muito simplificada. Cada linha contém uma única produção. Toda produção é uma lista de símbolos separada por espaço. Um terminal é uma sequência de caracteres cercados por apóstrofos (por exemplo '**'). Para simplificar, você pode assumir que os terminais não contêm espaços, mas seria bom se o seu programa permitir. Um não-terminal pode ser qualquer sequência que não contenha espaços ou $. A produção vazia (normalmente indicada com ε) é simplesmente uma linha contendo apenas o lado esquerdo não-terminal. A primeira linha é a produção que define o símbolo de início.

Como exemplo, a seguinte gramática:

S → aSa | bSb ε

Será dado como:

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

Exemplo de entradas / saídas:

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

O código mais curto em bytes vence.

Perl, 257 bytes

Inclui +4 para -0p

Dê gramática ao STDIN (sem espaços à direita. Remova o espaço extra no segundo exemplo). Supõe que nomes não terminais contenham apenas letras, dígitos e _. Usa em #vez de $para indicar o final da entrada. Pode lidar com literais contendo espaços

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

Produz os seguintes conjuntos como uma lista non-terminal literalem nenhuma ordem específica. Para o exemplo acima, ele gera:

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 mostrado, mas substitua \xd8e \npor suas versões literais para obter a pontuação reivindicada.

Deveria ser possível melhorar isso, pois a conversão dos firstconjuntos para os followconjuntos é atualmente muito incômoda.