A student wrote two context-free grammars G1 and G2 for generating a single…
2016
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 → intL; D → intL; 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 G1 and G2
- B.
Only G1
- C.
Only G2
- D.
Neither G1 nor G2
Attempted by 31 students.
Show answer & explanation
Correct answer: A
Answer: Both grammars generate the array declaration int a[10][3].
Grammar G1 (right-recursive style) derivation:
D -> int L ;
L -> id E (so we have int id E ; )
E -> [ num ] E (first dimension: int id [ num ] E ; )
E -> [ num ] (second dimension: int id [ num ] [ num ] ; )
Substituting id = a, first num = 10 and second num = 3 gives int a[10][3];
Grammar G2 (left-recursive style) derivation:
D -> int L ;
L -> id E (so we have int id E ; )
E -> E [ num ] (apply left recursion to add a second bracket: int id E [ num ] ; )
Then replace the remaining E by [ num ] to get int id [ num ] [ num ] ;
Again, substituting id = a and the two num values gives int a[10][3];
Conclusion: Both grammars can produce one or more bracketed numeric dimensions. The difference is only in recursion direction (right vs left), but both yield the desired declaration.
A video solution is available for this question — log in and enroll to watch it.