Find the follow sets

Question

The challenge below requires you to be familiar with formal parser theory. If you don't know what the question is asking because you don't know what the terms mean, context-free grammars and first/follow sets are covered in a lot of university courses.

I can recommend this Stanford course, in particular handouts 08 and 09 (from page 7). I've extracted also extracted a cheat sheet from these handouts - I recommend anyone attempting this challenge to read it.

---

Write a program or function that given a context-free grammar finds the follow set of every nonterminal. Informally, the follow set of a nonterminal is a set of terminals and $ (meaning end-of-input) that you can possibly find after that terminal in a valid sentence.

The input is given as a single printable ASCII string or array of printable ASCII lines. You may output the sets in any reasonable format, using $ (either as literal output, or string inside a set, etc) to indicate the end of input. You may assume that the input is always valid according to the format below.

The context free grammar is given in a very simplified manner. Every line contains a single production. Every production is a space separated list of symbols. A terminal is a string of characters surrounded by apostrophes (e.g. '**'). For simplicity you may assume that terminals do not contain spaces, but it would be nice if your program allows it. A nonterminal may be any string not containing spaces or $. The empty production (normally indicated with ε) is simply a line containing only the left hand side nonterminal. The first line is the production defining the start symbol.

As an example, the following grammar:

S → aSa | bSb | ε

Will be given as:

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

---

Example input / outputs:

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

---

Shortest code in bytes wins.

Answer 1

Perl, 257 bytes

Includes +4 for -0p

Give grammar on STDIN (without trailing spaces. Make sure to remove the extra space in the second example). Assumes non-terminal names only contain letters, digits and _. Uses # instead of $ to indicate end of input. Can handle literals containing spaces

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

Outputs the follow sets as a list of non-terminal literal in no particular order. For the example above it outputs:

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

Works as shown, but replace \xd8 and \n by their literal versions to get the claimed score.

It should be possible to improve this since converting the first sets to the follow sets is currently very awkward.