Project ForgeA student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration (dimension at least one), e.g. `int a[10][3];`. Both use D as the start symbol and terminals int, ;, id, [, ], num.
G1: D→int L; L→id[E; E→num]; E→num][E G2: D→int L; L→id E; E→E[num]; E→[num]
Which of the grammars correctly generate the declaration `int a[10][3];`?
- Both G1 and G2
- BOnly G1
- COnly G2
- DNeither G1 nor G2
Explanation
G1: D→int L; → int a[E (via L→id[E) → int a[10][E (via E→num][E) → int a[10][3] (via E→num]) → 'int a[10][3];'. Valid. G2: D→int L; → int a E (via L→id E) → building E: base case E→[num] gives '[10]'; then the recursive E→E[num] appends '[3]' to get '[10][3]' — so L='a[10][3]', giving the same full declaration. Both grammars work.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.