GATE CS 2016 Set 2 Q.56 (CS Q.46): Parsing and Syntax Analysis (LL and LR)

A student wrote two context-free grammars $G_1$ and $G_2$ 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.

Grammar $G_1$ :
$D \to \text{int } L;$
$L \to \text{id } [ E$
$E \to \text{num}]$
$E \to \text{num}] [ E$

Grammar $G_2$ :
$D \to \text{int } L;$
$L \to \text{id } E$
$E \to E[\text{num}]$
$E \to [\text{num}]$

Which of the grammars correctly generate the declaration mentioned above?

Both $G_1$ and $G_2$

Only $G_1$

Only $G_2$

Neither $G_1$ nor $G_2$

Official answer and solution

Official answer: A
From: Official GATE 2016 answer key

Solution

Trace the derivations of $G_1$ and $G_2$ for generating multidimensional array declarations.

A C-like array declaration of dimension $k \ge 1$ has the form:

\text{int } \text{id } [\text{num}]_1 [\text{num}]_2 \dots [\text{num}]_k ;

Trace Grammar $G_1$ :
$D \to \text{int } L;$
$L \to \text{id } [ E$
$E \to \text{num}] \mid \text{num}] [ E$

For dimension $k = 1$ :

D \implies \text{int } L; \implies \text{int id } [ E; \implies \text{int id } [\text{num}];

For dimension $k = 2$ :

D \implies \text{int id } [ E; \implies \text{int id } [\text{num}] [ E; \implies \text{int id } [\text{num}] [\text{num}];

By applying $E \to \text{num}] [ E$ recursively $(k-1)$ times followed by $E \to \text{num}]$ , $G_1$ generates an array declaration with any dimension $k \ge 1$ . Hence, $G_1$ correctly generates the declaration.

Trace Grammar $G_2$ :
$D \to \text{int } L;$
$L \to \text{id } E$
$E \to E[\text{num}] \mid [\text{num}]$

For dimension $k = 1$ :

D \implies \text{int } L; \implies \text{int id } E; \implies \text{int id } [\text{num}];

For dimension $k = 2$ :

D \implies \text{int id } E; \implies \text{int id } E [\text{num}]; \implies \text{int id } [\text{num}] [\text{num}];

By applying the left-recursive rule $E \to E [\text{num}]$ repeatedly $(k-1)$ times followed by $E \to [\text{num}]$ , $G_2$ generates an array declaration with any dimension $k \ge 1$ . Hence, $G_2$ correctly generates the declaration.

Therefore, both $G_1$ and $G_2$ correctly generate the declaration.

Final answer

Common trap

Assuming $G_1$ is invalid because the opening bracket is in the production for $L$ rather than $E$ , overlooking that the brackets match up identically in the full string.

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 2
Question: 56 of 65, printed as CS Q.46
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