Consider the following grammar: P → Q Q → R S T | S T T → c | ε R → a | d S →…

Given Grammar:

P → Q
Q → RST | ST
R → a | d
S → Sb | ε
T → c | ε

Analysis

The grammar is not LL(1) due to:

1. Immediate Left Recursion:
   S → Sb leads to infinite recursion in top-down parsing.

2. Non-determinism:
   Q → RST | ST creates choice ambiguity as S ⇒ ε affects FIRST(ST).

Grammar Modification

Eliminating left recursion:

S → bS | ε

FIRST and FOLLOW Sets

FIRST(R) = {a, d}
FIRST(S) = {b, ε}, FOLLOW(S) = {c, $}
FIRST(T) = {c, ε}, FOLLOW(T) = {$}

FIRST(ST) = {b, c, ε}

Since FIRST(RST) = {a, d} and FIRST(ST) = {b, c, ε} are disjoint, and ε ∈ FIRST(ST) with FOLLOW(Q) = {$}, no conflict arises.

Parsing Table Entries

Q: a,d → RST ; b,c,$ → ST
S: b → bS ; c,$ → ε
T: c → c ; $ → ε

Derivation of “dbbbc”

P ⇒ Q ⇒ RST ⇒ dST ⇒ dbST ⇒ dbbST ⇒ dbbbST
⇒ dbbbεT ⇒ dbbbc

Conclusion

After removing left recursion and verifying FIRST–FOLLOW conditions, the grammar becomes LL(1) with no parsing conflicts.