GATE CS 1999 Q2.15 — Parsing (LL, LR)

To determine if a grammar that is both left and right recursive for a non-terminal is ambiguous, we must consider whether the recursive non-terminal is useful (i.e., reachable from the start symbol and capable of deriving a terminal string).

For a grammar to be ambiguous, there must exist at least one string in its language $L(G)$ that has more than one distinct parse tree. Consider the following cases:

• Case 1 (Ambiguous): If the non-terminal $A$ is reachable and can derive terminal strings, such as in:
  $S \rightarrow A$
  $A \rightarrow aA \mid Aa \mid b$
  The string $aba$ has multiple distinct parse trees, making the grammar ambiguous.
• Case 2 (Unambiguous): If the recursive non-terminal is unreachable or cannot derive any terminal string, such as in:
  $S \rightarrow x$
  $A \rightarrow aA \mid Aa$
  Here, the language is $L(G) = \{x\}$. Since the only string in the language has a unique parse tree, the grammar is unambiguous.

Because the ambiguity depends on whether the grammar is reduced and the non-terminal is useful, the given information is not sufficient to decide.