Do follow And No follow?

How do I intuitively understand the construction of follow sets in predictive top-down parsing?

• I have consulted various resources, I do get the overall algorithm, but can not establish a mental model of how this would actually work. Take for example the following LL(1) grammar (It was a CFG defining a subset of C language constructs, I have skimmed extra rules, for now it defines the rules for declaring int variables in a C program;) Program                        -->        void main() { StatementSet } StatementSet                -->        Statement ; PrimeStatementSet PrimeStatementSet      -->        StatementSet | ^ Statement                      -->        DeclarationStatement DeclarationStatement   -->        Type identifier Type                               -->        int I understand that Follow(Program) = {$}. But how would I go about constructing the Follow set for StatementSet and PrimeStatementSet non-terminals? Since StatementSet exists on the RHS of rule 1 and 3, we will look for what follows StatementSet in those two productions, In rule 1, its simple Follow(StatementSet) = { '}' } However in rule 3, since StatementSet is the last member of the production, I need to add the Follow set of the LHS of this rule (i.e. PrimeStatementSet) , to Follow(StatementSet). At this moment Follow(StatementSet) hasn't been fully constructed, but we will leave that be and try to find Follow(PrimeStatementSet), well here is the tricky part, PrimeStatementSet occurs on the RHS of rule 2, but since it also is the last member of the said production, we will have to calculate the Follow of its RHS (i.e. StatementSet) and add that to Follow(PrimeStatementSet), but we can not do that since Follow(StatementSet) isn't complete yet. To my understanding, this process is exhibiting some sort of indirect recursive behaviour in the grammar. Still it is not "Left recursion". So by theory, it shouldn't be a problem in the Follow set construction. It'd be of great help to me if anyone'd take some time and explain to me the magic behind follow set constructions in an intuitive manner under the light of above posted grammar.

• Answer:

  If I understand the details right, the issue is the apparent mutual dependency between FOLLOW of StatementSet and PrimeStatementSet, so we can try to isolate that in a fragment from your grammar. Here is a numbered list of some similar productions, 1) P -> { Ss } 2) Ss -> stmt 3) Ss -> Pss 4) Pss -> Ss 5) Pss -> ^ Ss and Pss should be similarly co-dependent with respect to FOLLOW. Looking at it without thinking in terms of any algorithms or steps yet, what we want to tell from this is that FOLLOW(Ss) must include '}' by production 1, FOLLOW(Pss) must include FOLLOW(Ss) by production 3, and FOLLOW(Ss) must include FOLLOW(Pss) by production 4. The last two points just lead to the conclusion that FOLLOW(Pss) and FOLLOW(Ss) must be equal, since that is the only way they can mutually be (improper) supersets/subsets of each other. For finding out what their elements are, knowing that they're equal doesn't really add any information, save to note that since we know '}' is in FOLLOW(Ss), it must also be in FOLLOW(Pss). Without any further occurrences on right-hand sides to look at, the conclusion becomes that FOLLOW(Pss) = FOLLOW(Ss) = '}', which is consistent with all constraints we've found for them. That kind of reasoning isn't an immediate recipe for an imperative algorithm, but it can be translated into one, as an iteration to a fixed point. The way to produce a step-by-step method for this sort of constraint-propagating problem, is to initialize all the sets to empty, apply the constraints to all productions in one pass, and note whether any sets changed. If there was some change, this pass hasn't determined whether or not the change means something to sets that weren't reached by propagating it yet, so another pass must be made until everything stays the same from beginning to end. When it does, we'll know that nothing can change on the next pass either. If we go about it in that manner, the mutual dependency stops when it adds no further information, just as in our step-less conclusion: production 1: FOLLOW(Ss) includes '}' (something changed) production 2: (no change, RHS is terminals only) production 3: FOLLOW(Pss) includes '}', from FOLLOW(Ss) (something changed) production 4: FOLLOW(Ss) includes '}', from FOLLOW(Pss) (no change) production 5: (no change, RHS is terminals only) ...done! Did something change? (yes, with p1, p3), so do it again: production 1: FOLLOW(Ss) includes '}' (no change) production 2: (no change, RHS is terminals only) production 3: FOLLOW(Pss) includes '}', from FOLLOW(Ss) (no change) production 4: FOLLOW(Ss) includes '}', from FOLLOW(Pss) (no change) production 5: (no change, RHS is terminals only) ...done! Did something change? (no, we're finished!) If it helps, this general approach is also found other places in compiler construction, from the graph traversal that produces closures when converting between finite automata, to finding the maximal fixed-point solution of a set of dataflow equations, it's a handy thing to pick up. Intuition is always hard to communicate, but I hope this could add a useful perspective.