Consider the following context-free grammar where the start symbol is 𝑆 and…

GATE Β· 2024 Β· CS Β· Set 2 Β· Computer Science & IT

Consider the following context-free grammar where the start symbol is 𝑆 and the set of terminals is {π‘Ž,𝑏,𝑐,𝑑}.

                𝑆 β†’ π΄π‘Žπ΄π‘ | π΅π‘π΅π‘Ž

                𝐴 β†’ 𝑐𝑆 | πœ–

                𝐡 β†’ 𝑑𝑆 | πœ–

The following is a partially-filled LL(1) parsing table

a

b

c

d

$

S

𝑆 β†’ π΄π‘Žπ΄π‘

𝑆 β†’ π΅π‘π΅π‘Ž

(1)

(2)

A

 𝐴 β†’Β πœ–

(3)

𝐴 → 𝑐𝑆

B

(4)

π΅Β β†’Β πœ–

𝐡 → 𝑑𝑆

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, β€œblank” denotes that the corresponding cell is empty.

  1. A.

    (1) 𝑆 β†’ π΄π‘Žπ΄π‘ (2) 𝑆 β†’ π΅π‘π΅π‘Ž (3) 𝐴 β†’ πœ– (4) 𝐡 β†’ πœ–

  2. B.

    (1) 𝑆 β†’ π΅π‘π΅π‘Ž (2) 𝑆 β†’ π΄π‘Žπ΄π‘ (3) 𝐴 β†’ πœ– (4) 𝐡 β†’ πœ–

  3. C.

    (1) 𝑆 β†’ π΄π‘Žπ΄π‘ (2) 𝑆 β†’ π΅π‘π΅π‘Ž (3) blank (4) blank

  4. D.

    (1) 𝑆 β†’ π΅π‘π΅π‘Ž (2) 𝑆 β†’ π΄π‘Žπ΄π‘ (3) blank (4) blank

Attempted by 137 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…