GATE CS 2015 Set 3 Q.41 (CS Q.31): Parsing and Syntax Analysis (LL and LR)

Consider the following grammar $G$

\begin{aligned} S & \to F \mid H \\ F & \to p \mid c \\ H & \to d \mid c \end{aligned}

where $S, F,$ and $H$ are non-terminal symbols, $p, d,$ and $c$ are terminal symbols. Which of the following statement(s) is/are correct?
S1. LL(1) can parse all strings that are generated using grammar $G$
S2. LR(1) can parse all strings that are generated using grammar $G$

Only S1

Only S2

Both S1 and S2

Neither S1 nor S2

Official answer and solution

Official answer: D
From: Official GATE 2015 answer key

Solution

Check whether the grammar is ambiguous, which immediately determines LL(1) and LR(1) compatibility.

The given grammar $G$ is:

\begin{aligned} S & \to F \mid H \\ F & \to p \mid c \\ H & \to d \mid c \end{aligned}

Consider the terminal string c. It has two distinct leftmost derivations:

$S \implies F \implies c$
$S \implies H \implies c$
Since a string in $L(G)$ has two distinct parse trees (and two distinct leftmost derivations), grammar $G$ is ambiguous.

It is a fundamental theorem of formal language theory that no ambiguous grammar can be LL( $k$ ) or LR( $k$ ) for any $k \ge 1$ :

LL(1) parsing table will have multiple entries in $M[S, c]$ ( $S \to F$ and $S \to H$ ).
LR(1) parser will have a reduce-reduce conflict on lookahead $ (or lookahead c).

Therefore, neither LL(1) nor LR(1) can parse all strings using grammar $G$ (Option D).

Final answer

Common trap

Assuming LR(1) can parse any grammar with 1 lookahead, forgetting that ambiguity is fatal for both LL and LR parsers.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 41 of 65, printed as CS Q.31
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source