Back to the 2026 paper

Module 2: Syntax Analysis (Parser)

20267m

Consider the grammar:
S→ABCS \to ABC
A→aA∣εA \to aA \mid \varepsilon
B→bB∣εB \to bB \mid \varepsilon
C→cC∣dC \to cC \mid d
Compute the FIRST\text{FIRST} and FOLLOW\text{FOLLOW} sets for all non-terminals. Using these, construct the LL(1)\text{LL}(1) parsing table. Use the parsing table to show the parsing steps for the input string "aabd".

Worked SolutionAI Assisted

Grammar

S→ABCS \to ABC, A→aA∣εA \to aA \mid \varepsilon, B→bB∣εB \to bB \mid \varepsilon, C→cC∣dC \to cC \mid d

FIRST sets

  • FIRST(A)={a,ε}\mathrm{FIRST}(A) = \{a, \varepsilon\}
  • FIRST(B)={b,ε}\mathrm{FIRST}(B) = \{b, \varepsilon\}
  • FIRST(C)={c,d}\mathrm{FIRST}(C) = \{c, d\}
  • FIRST(S)=(FIRST(A)∖ε)∪(FIRST(B)∖ε)∪FIRST(C)={a,b,c,d}\mathrm{FIRST}(S) = (\mathrm{FIRST}(A)\setminus\varepsilon) \cup (\mathrm{FIRST}(B)\setminus\varepsilon) \cup \mathrm{FIRST}(C) = \{a, b, c, d\} (since AA and BB can both vanish, CC is reached)

FOLLOW sets

  • $\mathrm{FOLLOW}(S) = {$}$
  • FOLLOW(A)=(FIRST(B)∖ε)∪FIRST(C)={b,c,d}\mathrm{FOLLOW}(A) = (\mathrm{FIRST}(B)\setminus\varepsilon) \cup \mathrm{FIRST}(C) = \{b, c, d\} (from S→ABCS \to ABC, as BB is nullable)
  • FOLLOW(B)=FIRST(C)={c,d}\mathrm{FOLLOW}(B) = \mathrm{FIRST}(C) = \{c, d\}
  • $\mathrm{FOLLOW}(C) = \mathrm{FOLLOW}(S) = {$}$
Non-terminal FIRST FOLLOW
SS {a,b,c,d}\{a,b,c,d\} ${$}$
AA {a,ε}\{a,\varepsilon\} {b,c,d}\{b,c,d\}
BB {b,ε}\{b,\varepsilon\} {c,d}\{c,d\}
CC {c,d}\{c,d\} ${$}$

LL(1) parsing table

  • S→ABCS \to ABC: FIRST(ABC)={a,b,c,d}\mathrm{FIRST}(ABC) = \{a,b,c,d\}, so fill a,b,c,da,b,c,d.
  • A→aAA \to aA on aa; A→εA \to \varepsilon on FOLLOW(A)=b,c,d\mathrm{FOLLOW}(A) = b,c,d.
  • B→bBB \to bB on bb; B→εB \to \varepsilon on FOLLOW(B)=c,d\mathrm{FOLLOW}(B) = c,d.
  • C→cCC \to cC on cc; C→dC \to d on dd.

| | aa | bb | cc | dd | \0 | `aabd | S→ABCS \to ABC | | 2 | ABC\1 | `aabd | match a |
| 4 | ABC\2 | `abd| matcha | | 6 | ABC\3 | `bd | B→bBB \to bB |
| 8 | bBC\4 | `d | B→εB \to \varepsilon | | 10 | C\5 | `d | match d |
| 12 | $$∣‘ | `` | accept |

The string aabd is accepted.

Similar questions

Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.