GATE CS 2010 Q38 — Parsing (LL, LR)

To determine the classification of the grammar $S \to aSa \mid bS \mid c$, we can analyze its LL(1) and LR(1) properties.

1. Checking for LL(1)

A grammar is LL(1) if, for every non-terminal $A$ with multiple productions $A \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n$:

1. The $\text{FIRST}$ sets of all alternatives are pairwise disjoint.
2. If any production can derive the empty string $\epsilon$, its $\text{FIRST}$ set must be disjoint from the $\text{FOLLOW}$ set of $A$.

Let's find the $\text{FIRST}$ sets for the three alternatives of $S$:

• $\text{FIRST}(aSa) = \{a\}$
• $\text{FIRST}(bS) = \{b\}$
• $\text{FIRST}(c) = \{c\}$

Since the sets $\{a\}$, $\{b\}$, and $\{c\}$ are pairwise disjoint, and there are no $\epsilon$-productions, there are no FIRST/FIRST or FIRST/FOLLOW conflicts. Therefore, the grammar is LL(1).

2. Checking for LR(1)

A fundamental theorem in compiler design states that every LL(1) grammar is also an LR(1) grammar (i.e., $\text{LL}(1) \subset \text{LR}(1)$). Since the grammar is LL(1), it is guaranteed to be LR(1).

Thus, the grammar is both LL(1) and LR(1).