# Grammar to Set - Follow

## Grammar2Set #5 :: 05-05-2018

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.