A student wrote two context-free grammars G1 and G2 for generatin
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
|
Grammar G1 |
Grammar G2 |
|
D → int L; |
D → int L; |
|
L → id[E |
L → idE |
|
E → num] |
E → E[num] |
|
E → num][E |
E → [num] |
Which of the grammars correctly generate the declaration mentioned above?
A. Both <strong>G1</strong> and <strong>G2</strong>
B. Only <strong>G1</strong>
C. Only <strong>G2</strong>
D. Neither <strong>G1</strong> nor <strong>G2</strong>
Please scroll down to see the correct answer and solution guide.
Right Answer is: A
SOLUTION
Grammar G1 is:
D → int L;
L → id [E
E → num]
E → num] [E
Generate one dimensional array: a[10]
D → int L
→ int id[E
→ int id[num]
This leads to int a[10]
Generate two-dimensional array: int a [10] [3];
D → int L;
→ int id [E;
→ int id [num] [E;
→ int id [num] [num];
This leads to int a[10][3]
It correctly generates declaration given.
Grammar G2 is:
D → int L;
L → idE
E → E[num]
E → [num]
Generate one dimensional array: a[10]
D → int L;
→ int idE
→ int id[num]
This leads to int a[10]
Generate two-dimensional array: int a [10] [3];
int a[10][3];
D → int L;
→ int id E;
→ int id E[num];
→ int id [num] [num];
This leads to int a[10][3]
So, both grammar G1 and G2 generates the given declaration.