A student wrote two context-free grammars G1 and G2 for generating a single… — GATE CS 2016 Set 2 Q46

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

                int a[10] [3];

The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.
$\begin{array}{l|l} \text{Grammar } \textbf{G1} & \text{Grammar } \textbf{G2} \\ \hline \text{D} \rightarrow \textbf{int L;} & \text{D} \rightarrow \textbf{int L;}\\ \text{L} \rightarrow \textbf{id [E} & \text{L} \rightarrow \textbf{id E}\\ \text{E} \rightarrow \textbf{num ]} & \text{E} \rightarrow \textbf{E [num]}\\ \text{E} \rightarrow \textbf{num ] [E} & \text{E} \rightarrow \textbf{[num]}\\ \end{array}$ Which of the grammars correctly generate the declaration mentioned above?

View worked solution

Answer: A

To determine which grammars correctly generate the array declaration int a[10] [3];, we can trace the derivations for both $G_1$ and $G_2$ using the terminals: int, ;, id (for a), [, ], and num (for 10 and 3).

Derivation in Grammar $G_1$ :

Using the rules of $G_1$ :

\begin{aligned} D &\Rightarrow \textbf{int } L; \\ &\Rightarrow \textbf{int id [} E; & \quad (\text{using } L \rightarrow \textbf{id [E}) \\ &\Rightarrow \textbf{int id [ num ] [} E; & \quad (\text{using } E \rightarrow \textbf{num ] [E}) \\ &\Rightarrow \textbf{int id [ num ] [ num ]}; & \quad (\text{using } E \rightarrow \textbf{num ]}) \end{aligned}

Substituting id with a, and the first and second num with 10 and 3 respectively, we get:
int a[10] [3];. Thus, $G_1$ correctly generates the declaration.

Derivation in Grammar $G_2$ :

Using the rules of $G_2$ :

\begin{aligned} D &\Rightarrow \textbf{int } L; \\ &\Rightarrow \textbf{int id } E; & \quad (\text{using } L \rightarrow \textbf{id E}) \\ &\Rightarrow \textbf{int id } E \textbf{ [num]}; & \quad (\text{using } E \rightarrow \textbf{E [num]}) \\ &\Rightarrow \textbf{int id [num] [num]}; & \quad (\text{using } E \rightarrow \textbf{[num]}) \end{aligned}

Substituting the terminals, we get:
int a[10] [3];. Thus, $G_2$ also correctly generates the declaration.

Since both grammars successfully generate the given declaration, the correct option is A.

Free practice · Your answers on this page are not saved.

GATE CS 2016 Set 2 Q46 — Parsing (LL, LR)

Related questions