Search code examples
parsingcompiler-constructionll-grammar

Can a follow-follow conflict exist in a grammar?


I know that First/First and First/Follow conflicts exist in a grammar which makes the grammar "not LL(1)". I was just wondering if Follow/Follow conflict exist in a grammar.


Solution

  • Yes, this is possible, but it requires an unusual configuration to make it happen. Consider the following grammar, which has been augmented with a new start symbol:

    S' → S$

    S → tT

    T → A | B

    A → ε

    B → ε

    Now, let's imagine trying to fill in our LL(1) parse table, which is shown here:

              $          t
         +----------+----------+
     S'  |          | S' -> S$ |
         +----------+----------+
     S   |          | S -> tT  |
         +----------+----------+
     T   | T -> A   |          |
         | T -> B   |          |
         +----------+----------+
     A   | A -> e   |          |
         +----------+----------+
     B   | B -> e   |          |
         +----------+----------+
    

    Notice that there are two items in the entry for (T, $). And that makes sense: if we have the active nonterminal T and see a $, we know that we need to select a production that's going to expand out to the empty string. And we have two different ways of doing this: we could use T → A or T → B, with the ultimate goal of expanding each of those nonterminals out to the empty string. This is a problem - we can't predict which route to take.

    Now, what sort of conflict is this? It can't be a FIRST/FIRST conflict, because FIRST(A) = {ε} and FIRST(B) = {ε}, so neither A nor B has any terminals in its first set. It can't be a FIRST/FOLLOW conflict for the same reason.

    That means that it's the rare FOLLOW/FOLLOW conflict - we know that we'd choose the production based on what's in the FOLLOW sets of A and B, and yet they're exactly identical to one another and so the parser can't choose what to do next unambiguously.