FIRST and FOLLOW sets, part 2

In my last post we looked at FIRST sets. That's the hard part. Today's topic, FOLLOW sets, are easy.

In the grammar restrictions post I defined FOLLOW as

the set of possible first tokens for the following sentence

So now that we have the FIRST set for every grammar element, we can get each element's FOLLOW set by finding the FIRST set for every element that follows it.

Let's define:

S, A, B, and C as sentences in the grammar

The FOLLOW rules are:

1. For S → AB, S → [A]B, S → {A}B
   
   
   
   • If ∀ B, B ≠ ∈
     FOLLOW(A) includes FIRST(B)
     
   • If ∃ B, B = ∈
     FOLLOW(A) includes FOLLOW(S)
     
   
   
   
2. For S → AB, S → A[B], S → A{B}
   
   
   
   • FOLLOW(B) includes FOLLOW(N)
     
   
   
   
3. For S → AB | AC
   
   
   
   • FOLLOW(A) includes FIRST(B) ∪ FIRST(C)
     
   
   
   

From these three simple rules (and the FIRST sets), we can construct the FOLLOW sets for all the elements of the grammar.

The complete set of FOLLOW sets for SPTL is available in gnumeric format or csv format.