GATE CS 2005 Q14 — Parsing (LL, LR)

A predictive parser (such as an $\text{LL}(1)$ parser) must be deterministic. This means that for any non-terminal and lookahead symbol, there must be at most one production rule that can be applied. Consequently, no ambiguous grammar can be parsed by a predictive parser.

Let us check if the given grammar is ambiguous:

We can show ambiguity by generating the string () using two different leftmost derivations:

• Derivation 1:
  $A \Rightarrow (A) \Rightarrow (\epsilon) = ()$
• Derivation 2:
  $A \Rightarrow AA \Rightarrow (A)A \Rightarrow (\epsilon)A \Rightarrow ()A \Rightarrow ()\epsilon = ()$

Since the string () has more than one leftmost derivation (and thus multiple distinct parse trees), the grammar is ambiguous. Therefore, it is not suitable for predictive parsing.