Consider two grammars 𝐺1 and 𝐺2 with the production rules given below: 𝐺1:…

2025

Consider two grammars 𝐺1 and 𝐺2 with the production rules given below:

    𝐺1: 𝑆 β†’ 𝑖𝑓 𝐸 π‘‘β„Žπ‘’π‘› 𝑆 | 𝑖𝑓 𝐸 π‘‘β„Žπ‘’π‘› 𝑆 𝑒𝑙𝑠𝑒 𝑆 | π‘Ž

          𝐸 β†’ 𝑏

    𝐺2: 𝑆 β†’ 𝑖𝑓 𝐸 π‘‘β„Žπ‘’π‘› 𝑆 | 𝑀

           𝑀 β†’ 𝑖𝑓 𝐸 π‘‘β„Žπ‘’π‘› 𝑀 𝑒𝑙𝑠𝑒 𝑆 | 𝑐

           𝐸 → 𝑏

where 𝑖𝑓,π‘‘β„Žπ‘’π‘›,𝑒𝑙𝑠𝑒, π‘Ž, 𝑏, 𝑐 are the terminals. Which of the following option(s) is/are CORRECT?

  1. A.

    𝐺1 is not 𝐿𝐿(1) and 𝐺2 is 𝐿𝐿(1).

  2. B.

    𝐺1 is 𝐿𝐿(1) and 𝐺2 is not 𝐿𝐿(1).

  3. C.

    𝐺1 and 𝐺2 are not 𝐿𝐿(1).

  4. D.

    𝐺1 and 𝐺2 are ambiguous.

Attempted by 107 students.

Show answer & explanation

Correct answer: C, D

  • C: Both not LL(1)

    • G₁: Common prefix if E then S in two S-productions β†’ FIRST overlap on if.

    • Gβ‚‚: S-productions if E then S and M (FIRST(M) includes if) β†’ overlap on if.

  • D: Both ambiguous

    • G₁: Classic dangling else (e.g., if b then if b then a else a has 2 parse trees).

    • Gβ‚‚: Similar recursive structure allows multiple if-else pairings for same string.

A video solution is available for this question β€” log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir