Let’s solve the Exercise step by step.
Given Grammar
A→BCD
B→bB|ε
C→Cg|g|Ch|i
D→AB|ε
✅ FIRST Sets
✅⃣ FIRST(B)
B → bB | ε
From bB, FIRST = { b }
From ε, add ε
FIRST(B) = { b, ε }
✅⃣ FIRST(C)
C → Cg | g | Ch | i
Check productions:
g ⇒ add g
i ⇒ add i
Cg and Ch are left recursive, but C must eventually produce g or i
So:
FIRST(C) = { g, i }
✅⃣ FIRST(D)
D → AB | ε
Check AB:
FIRST(A) needed.
✅⃣ FIRST(A)
A→BCD
We compute step-by-step:
FIRST(B) = { b, ε }
FIRST(C) = { g, i }
Since B can produce ε:
FIRST(A) includes:
FIRST(B) − {ε} = { b }
FIRST(C) = { g, i }
So:
FIRST(A) = { b, g, i }
Now return to FIRST(D)
D → AB | ε
FIRST(A) = { b, g, i }
So:
FIRST(D) = { b, g, i, ε }
✅ Final FIRST Sets
FIRST(A) = { b, g, i }
FIRST(B) = { b, ε }
FIRST(C) = { g, i }
FIRST(D) = { b, g, i, ε }
✅ FOLLOW Sets
Assume A is start symbol
→ add $ to FOLLOW(A)
✅⃣ FOLLOW(A)
A→BCD
D→AB
From start symbol:
FOLLOW(A) = { $ }
From D → A B:
After A comes B
Add FIRST(B) − {ε} = { b }
If B → ε, add FOLLOW(D)
We will compute systematically.
✅⃣ FOLLOW(B)
Occurrences:
A→BCD
After B comes C
Add FIRST(C) = { g, i }
Also in:
D→AB
B at end → add FOLLOW(D)
✅⃣ FOLLOW(C)
A→BCD
After C comes D
Add FIRST(D) − {ε} = { b, g, i }
Since D → ε possible → add FOLLOW(A)
✅⃣ FOLLOW(D)
A→BCD
D at end → add FOLLOW(A)
Now compute completely:
FOLLOW(A)
Start: { $ }
From C → ...? none
From D → A B:
Add FIRST(B) − {ε} = { b }
So:
FOLLOW(A) = { $, b }
FOLLOW(D)
From A → B C D
Add FOLLOW(A)
So:
FOLLOW(D) = { $, b }
FOLLOW(C)
From A → B C D
Add FIRST(D) − {ε} = { b, g, i }
Since D has ε, add FOLLOW(A) = { $, b }
So:
FOLLOW(C) = { b, g, i, $, b }
Remove duplicate b:
FOLLOW(C) = { b, g, i, $ }
FOLLOW(B)
From A → B C D
Add FIRST(C) = { g, i }
From D → A B
B at end → add FOLLOW(D) = { $, b }
So:
FOLLOW(B) = { g, i, $, b }
✅ Final FOLLOW Sets
FOLLOW(A) = { $, b }
FOLLOW(B) = { g, i, $, b }
FOLLOW(C) = { b, g, i, $ }
FOLLOW(D) = { $, b }
If you want, I can also show this in table format (like exam writing style).
This looks like a solid workout for LL(1) parsing theory! Let's dive into the first grammar
from your exercise. I'll break down the FIRST and FOLLOW sets and build the parsing table
for you.
Part 2: Parsing Grammar G
The grammar provided is:
1. $S \rightarrow [ SX ] \mid a$
2. $X \rightarrow \epsilon \mid +SY \mid Yb$
3. $Y \rightarrow \epsilon \mid -SXc$
A. FIRST and FOLLOW Sets
To calculate these, we look at what terminals can appear at the start of a string (FIRST) and
what can follow a non-terminal (FOLLOW).
Non-Terminal FIRST FOLLOW
S $\{ [, a \}$ $\{ \$, ], +, -, b, c \}$
X $\{ \epsilon, +, -, b \}$ $\{ ] \}$
Y $\{ \epsilon, - \}$ $\{ b, c \}$
Key Logic:
C. Top-Down Parsing for [a+a-ac]
To parse this string, we use a stack (starting with $S$) and match against the input.
Great! Let’s tackle Part 3. This grammar is a classic example used to demonstrate why some
languages need a little "massaging" before a top-down parser can handle them.
Part 3: Analyzing and Transforming Grammar G
The grammar provided is:
1. $A' \rightarrow A$
2. $A \rightarrow xA \mid yA \mid y$
C. Why is this grammar NOT LL(1)?
D. Transform the Grammar into LL(1)
We fix this using Left Factoring. We pull out the common prefix (y) and create a new non-
terminal to handle the remainder.
E. Parse Table for the Transformed Grammar
Now, every cell has at most one production. The grammar is officially LL(1) compliant!
Would you like to try tracing a specific string, like xyy, through this new table to see
how the conflict is resolved?
4.