Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20237m

Find the FIRST an FOLLOW form the following production:
S→aBDhS \to aBDh
B→cCB \to cC
C→bC∣ϵC \to bC | \epsilon
D→EFD \to EF
E→g∣ϵE \to g | \epsilon
F→f∣ϵF \to f | \epsilon

Worked SolutionAI Assisted

First and Follow for the given grammar

Grammar:
S→aBDhB→cCC→bC∣ϵD→EFE→g∣ϵF→f∣ϵ \begin{array}{rcl} S &\to& aBDh\\ B &\to& cC\\ C &\to& bC \mid \epsilon\\ D &\to& EF\\ E &\to& g \mid \epsilon\\ F &\to& f \mid \epsilon \end{array}

Step 1 — FIRST sets

Compute allowed terminals that begin derivations (plus ϵ\epsilon if nullable).

  • FIRST(a)={a}, FIRST(b)={b}, FIRST(c)={c}, FIRST(g)={g}, FIRST(f)={f}, FIRST(h)={h}\mathrm{FIRST}(a) = \{a\},\ \mathrm{FIRST}(b)=\{b\},\ \mathrm{FIRST}(c)=\{c\},\ \mathrm{FIRST}(g)=\{g\},\ \mathrm{FIRST}(f)=\{f\},\ \mathrm{FIRST}(h)=\{h\}
  • FIRST(C)={b,ϵ}\mathrm{FIRST}(C) = \{b, \epsilon\} (from C→bCC\to bC and C→ϵC\to\epsilon)
  • FIRST(E)={g,ϵ}\mathrm{FIRST}(E) = \{g, \epsilon\}
  • FIRST(F)={f,ϵ}\mathrm{FIRST}(F) = \{f, \epsilon\}
  • FIRST(D)\mathrm{FIRST}(D): D→EFD\to EF. FIRST(E)={g,ϵ}\{g,\epsilon\} → take gg; since E nullable, take FIRST(F)={f,ϵ}\{f,\epsilon\} → ff; since both nullable, include ϵ\epsilon.
    FIRST(D)={g,f,ϵ}\mathrm{FIRST}(D) = \{g, f, \epsilon\}
  • FIRST(B)={c}\mathrm{FIRST}(B) = \{c\} (from B→cCB\to cC). (B is not nullable since cc is a terminal.)
  • FIRST(S)\mathrm{FIRST}(S): S→aBDhS\to aBDh → starts with terminal a.
    FIRST(S)={a}\mathrm{FIRST}(S) = \{a\}

Step 2 — FOLLOW sets

The follow of a nonterminal XX is the set of terminals that can appear immediately to the right of XX in some sentential form.

  • FOLLOW(S)FOLLOW(S): S is the start symbol → ${$}$.
    FOLLOW(S)={$}\mathrm{FOLLOW}(S) = \{\$\}

  • FOLLOW(B)FOLLOW(B): from S→a B D hS\to a\,B\,D\,h, after BB comes DD, so we add FIRST(D)∖{ϵ}={g,f}\mathrm{FIRST}(D)\setminus\{\epsilon\} = \{g,f\}. Also DD is nullable, so we add $\mathrm{FOLLOW}(S) = {$}$.
    FOLLOW(B)={g, f, $}\mathrm{FOLLOW}(B) = \{g,\ f,\ \$\}

  • FOLLOW(C)FOLLOW(C): from B→c CB\to c\,C (C at the end), so FOLLOW(C)=FOLLOW(B)\mathrm{FOLLOW}(C) = \mathrm{FOLLOW}(B).
    FOLLOW(C)={g, f, $}\mathrm{FOLLOW}(C) = \{g,\ f,\ \$\}

  • FOLLOW(D)FOLLOW(D): from S→aBD hS\to aBD\,h, after DD comes terminal h.
    FOLLOW(D)={h}\mathrm{FOLLOW}(D) = \{h\}

  • FOLLOW(E)FOLLOW(E): from D→E FD\to E\,F, after EE comes FF, so add FIRST(F)∖{ϵ}={f}\mathrm{FIRST}(F)\setminus\{\epsilon\} = \{f\}. Since FF is nullable, also add FOLLOW(D)={h}\mathrm{FOLLOW}(D)=\{h\}.
    FOLLOW(E)={f, h}\mathrm{FOLLOW}(E) = \{f,\ h\}

  • FOLLOW(F)FOLLOW(F): from D→EFD\to EF (F at the end), so FOLLOW(F)=FOLLOW(D)\mathrm{FOLLOW}(F) = \mathrm{FOLLOW}(D).
    FOLLOW(F)={h}\mathrm{FOLLOW}(F) = \{h\}

Final answer:
FIRST(S)={a},FIRST(B)={c},FIRST(C)={b,ϵ},FIRST(D)={g,f,ϵ},FIRST(E)={g,ϵ},FIRST(F)={f,ϵ}{\small \mathrm{FIRST}(S)=\{a\},\quad \mathrm{FIRST}(B)=\{c\},\quad \mathrm{FIRST}(C)=\{b,\epsilon\},\quad \mathrm{FIRST}(D)=\{g,f,\epsilon\},\quad \mathrm{FIRST}(E)=\{g,\epsilon\},\quad \mathrm{FIRST}(F)=\{f,\epsilon\}}
FOLLOW(S)={$},FOLLOW(B)={g,f,$},FOLLOW(C)={g,f,$},FOLLOW(D)={h},FOLLOW(E)={f,h},FOLLOW(F)={h}{\small \mathrm{FOLLOW}(S)=\{\$\},\quad\mathrm{FOLLOW}(B)=\{g,f,\$\},\quad\mathrm{FOLLOW}(C)=\{g,f,\$\},\quad\mathrm{FOLLOW}(D)=\{h\},\quad\mathrm{FOLLOW}(E)=\{f,h\},\quad\mathrm{FOLLOW}(F)=\{h\}}

Similar questions

Student FinanceWeb Platform

Pocketly — Personal Finance for Students

Keep your hostel and college expenses under control. Track accounts, log spending in seconds, and stay within your monthly budget.