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?

Answer: A. Both G1 and G2 — 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…

  1. A.

    Both G1 and G2

  2. B.

    Only G1

  3. C.

    Only G2

  4. D.

    Neither G1 nor G2

Attempted by 38 students.

Show answer & explanation

Correct answer: A

Answer: Both grammars generate the array declaration int a[10][3].

Grammar G1 (right-recursive style) derivation:

  1. D -> int L ;

  2. L -> id E (so we have int id E ; )

  3. E -> [ num ] E (first dimension: int id [ num ] E ; )

  4. 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:

  1. D -> int L ;

  2. L -> id E (so we have int id E ; )

  3. E -> E [ num ] (apply left recursion to add a second bracket: int id E [ num ] ; )

  4. 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.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…