CODEWITHSUNDEEP
parsinggrammarambiguous-grammar
WJosh Vetter
WJosh Vetter

Reputation: 37

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) =

Upvotes: 0

Views: 381

Answers (1)

melpomene
melpomene

Reputation: 85877

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}

Upvotes: 1

Related Questions