What will be the “First” and “Follow” of E and F for the following grammar? E…

2017

What will be the “First” and “Follow” of E and F for the following grammar?

E -> TE'
E' -> +TE' / ε
T -> FT'
T' -> *FT' / ε
F -> id / (E)

Answer: B. First(E)={id, (}, Follow(E)={$, )}, First(F)={id, (}, Follow(F)={*, $, ), +} — Concept: First(X) is the set of terminals that can begin some string derivable from X (plus ε if X can derive the empty string). Follow(X) is the set of…

  1. A.

    First(E)={id, (, ε}, Follow(E)={ε, )}, First(F)={id, ), $}, Follow(F)={*, $, (}

  2. B.

    First(E)={id, (}, Follow(E)={$, )}, First(F)={id, (}, Follow(F)={*, $, ), +}

  3. C.

    First(E)={id, ), ε}, Follow(E)={ε, )}, First(F)={id, )}, Follow(F)={*, $, (, +}

  4. D.

    First(E)={id, )}, Follow(E)={$, )}, First(F)={id, (, $}, Follow(F)={*, $, ), +}

Attempted by 225 students.

Show answer & explanation

Correct answer: B

Concept: First(X) is the set of terminals that can begin some string derivable from X (plus ε if X can derive the empty string). Follow(X) is the set of terminals that can immediately follow X in some derivation from the start symbol, and the end-marker $ always belongs to Follow(start symbol). Both are propagated through every production where the non-terminal appears, using the nullable-tail rule: if whatever comes right after X in a production can itself vanish (derive ε), then whatever follows that vanishing piece also flows into Follow(X).

Applying this to the grammar: E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → id | ( E ).

  1. F → id | (E), so First(F) = {id, (}.

  2. T → F T′, and F can never derive ε, so First(T) = First(F) = {id, (}.

  3. E → T E′, and T can never derive ε, so First(E) = First(T) = {id, (}.

  4. E is the start symbol, so the end-marker $ belongs to Follow(E).

  5. The only production placing a symbol right after E is F → ( E ), which puts ) immediately after E, so Follow(E) = {$, )}.

  6. T appears only in E → T E′. Since First(E′) = {+, ε}, the terminal + is added directly to Follow(T); because ε ∈ First(E′), Follow(E) is also inherited, giving Follow(T) = {+, $, )}.

  7. F appears in T → F T′ and T′ → * F T′. Since First(T′) = {*, ε}, the terminal * is added directly to Follow(F); because ε ∈ First(T′), Follow(T) is also inherited, giving Follow(F) = {*, +, $, )}.

Cross-check: Trace the string id + id * id. After the first id, the next token is +, matching the + in Follow(T) and Follow(F); after the final id the input ends, matching the $ present in every Follow set; and any parenthesised sub-expression such as (id) always closes with ), matching the ) member of Follow(E) and Follow(F). Every predicted Follow member shows up at a real boundary in the string, confirming the sets.

Result: First(E) = {id, (}, Follow(E) = {$, )}, First(F) = {id, (}, Follow(F) = {*, +, $, )}.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…