Follow

Contents/Index

Preface
Syntax of Input
Nullable
First
@Follow
The Application

Finally we want to calculate Follow. This is done by calculating constraints. But first we add the production S \rightarrow S' $ as a start production where S' is the original start production of that grammar. Let M \rightarrow \alpha N \beta be a production where \alpha, \beta be possibly empty. The constraints is now obtained as

1. Let m = First(\beta). If m \neq \emptyset, add the constraint m \subset Follow(N)
2. If M \neq N and Nullable(\beta), add the constraint Follow(M) \subset Follow(N). Note that \beta = \emptyset \Rightarrow Nullable(\beta) = true

Then we solve the constraints with fixpoint-iteration as follows

1. Init empty solved dictionary.
2. For every constraint add every First set to solved.
3. Now iterate through constraints adding Follow-sets to solved until no new elements are added.

Again this algorithm is bound to stop because we are adding from a finite set. At some point new elements simply can't exist.

The Follow-sets are tiresome at best to calculate. Observe the following grammar

A \rightarrow "a" B "c" D . . . D \rightarrow "(" E ")" E \rightarrow A E E \rightarrow

Stolen but modified from a problem sheet with answer key. The answer key has a problem, I'm pretty sure. We can loosely calculate

{")"} \subset Follow(E) First(E) \subset Follow(A) Follow(E) \subset Follow(A) \Rightarrow {")"} \subset Follow(A)

The last line since Nullable(E) = true. From the same problem sheet, but where I first made a mistake:

C \rightarrow A B "c0" "c1" E F

Where Nullable(A) = Nullable(B) = true. Here

First(B) \subset Follow(A) {"c0"} \subset Follow(A)

Anyway. Follow works solely on the right hand side of a grammar. Take this grammar with added S production

S \rightarrow A $ A \rightarrow B C "a" B \rightarrow "b" C | C \rightarrow "c" A |

We have Nullable(A) = false, Nullable(B) = Nullable(C) = true. And we have

First(A) = {"a","b","c"} First(B) = {"b"} First(C) = {"c"} First(C "a") = {"c","a"}

to calculate Follow we obtain constraints:

{$} \subset Follow(A) First(C "a") \subset Follow(B) First("a") \subset Follow(C) Follow(B) \subset Follow(C) Follow(C) \subset Follow(A)

First iteration:

{$} \subset Follow(A) {"a","c"} \subset Follow(B) {"a"} \subset Follow(C) {"a","c"} \subset Follow(C) {"a","c",$} \subset Follow(A)

Second iteration

{"a","c"} \subset Follow(C) {"a","c"} \subset Follow(A)

No new elements are added, and we have

{"a","c",$} = Follow(A) {"a","c"} = Follow(B) {"a","c"} = Follow(C)

Again that spectacular HashSet comes to our rescue. We add elements element wise until all adds return false.