Search code examples
parsinggrammarambiguous-grammar

Follow set example doesn't follow any rules?

  1. S → asg
  2. S → if C then S E
  3. C → bool
  4. E → else S
  5. E → λ

all the lower case and the λ are terminal symbols

I need help deriving the follow set of this grammar. I normally do not have trouble with these problems and I know the rules, but when I practiced this example from my book this is the only thing I could get:

Follow(S) = {$} U Follow(E) 
Follow(C) = 
Follow(E) =
Solution

  • According to https://www.cs.uaf.edu/~cs331/notes/FirstFollow.pdf:

    To compute FOLLOW(A) for all nonterminals A, apply the following rules until nothing can be added to any FOLLOW set:

    1. Place $ in FOLLOW(S), where S is the start symbol and $ is the input right endmarker.
    2. If there is a production A ⇒ αΒβ, then everything in FIRST(β), except for ε, is placed in FOLLOW(B).
    3. If there is a production A ⇒ αΒ, or a production A ⇒ αΒβ where FIRST(β) contains ε (i.e., β ⇒ε), then everything in FOLLOW(A) is in FOLLOW(B).

    Assuming S is the start symbol in your grammar and λ represents an empty string, we get:

    • {$} ⊆ Follow(S) by rule 1.
    • (First(E) \ {λ}) ⊆ Follow(S) by rule 2 / production 2.
    • Follow(E) ⊆ Follow(S) by rule 3 / production 4.
    • (First(then S E) \ {λ}) ⊆ Follow(C) by rule 2 / production 2.
    • Follow(S) ⊆ Follow(E) by rule 3 / production 2.

    First(then S E) is just then (because it's terminal), so we have {then} ⊆ Follow(C).

    This is the only constraint on Follow(C), so the smallest set that satisfies it is:

    Follow(C) = {then}

    Because we have Follow(E) ⊆ Follow(S) and Follow(S) ⊆ Follow(E), it follows (hah) that they're equal:

    Follow(E) = Follow(S)

    Finally we have

    Follow(S) = {$} ∪ (First(E) \ {λ})

    Fortunately First(E) is easy because E only has two productions, one of which is empty and the other starts with a terminal symbol:

    First(E) = {λ, else}

    Therefore

    Follow(S) = {$, else}

    and

    Follow(E) = {$, else}