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

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.