Search code examples
compiler-constructioncontext-free-grammarll-grammar

How does FOLLOW work for the following CFG?


The original cfg is

S -> S + S | SS | (S) | S* | a

After refactoring and eliminating left recursion, I arrive at the following reduction:

S -> TB
B -> AB | e
A -> +S | TB | *
T -> (S) | a

When calculating follow(B), online sources that I can find say that it should be {$}. However, based on the rules in the dragon book, it looks like follow(B) = follow(S) + follow(A), because of rule 3 (a production A -> aB causes everything in follow(A) to be in follow(B).

Am I understanding the rule incorrectly?


Solution

  • No, your internet source is wrong. Your understanding of the FOLLOW algorithm is fine (and also appears in the class notes you are quoting).

    It's actually an odd example for an exercise in parsing, since the grammar is ambiguous. Refactoring and left-recursion elimination do not remove ambiguity; the end result is still ambiguous, and ambiguous grammars will always have parsing conflicts.