Consider the following grammar 𝐺 𝑆 β†’ 𝐹 | 𝐻 𝐹 β†’ 𝑝 | 𝑐 𝐻 β†’ 𝑑 | 𝑐 where…

2015

Consider the following grammar 𝐺

𝑆 β†’ 𝐹 | 𝐻

𝐹 β†’ 𝑝 | 𝑐

𝐻 β†’ 𝑑 | 𝑐

where 𝑆, 𝐹, and 𝐻 are non-terminal symbols, 𝑝, 𝑑, and 𝑐 are terminal symbols. Which of the following statement(s) is/are correct?

S1. LL(1) can parse all strings that are generated using grammar 𝐺

S2. LR(1) can parse all strings that are generated using grammar 𝐺

  1. A.

    Only S1

  2. B.

    Only S2

  3. C.

    Both S1 and S2

  4. D.

    Neither S1 nor S2

Attempted by 137 students.

Show answer & explanation

Correct answer: D

Given grammar: S β†’ F | H, F β†’ p | c, H β†’ d | c

Ambiguity:

  • The string 'c' can be derived in two ways: S β†’ F β†’ c and S β†’ H β†’ c, so the grammar is ambiguous.

Consequences for LL(1):

  • Compute FIRST sets: FIRST(F) = {p, c}, FIRST(H) = {d, c}. They overlap on 'c', so a one-token predictive parser cannot choose between the two alternatives of S when the next token is 'c'. Therefore the grammar is not LL(1).

Consequences for LR(1):

  • Because the grammar is ambiguous, a bottom-up LR(1) parser will face a reduce/reduce conflict on the input 'c' (both reductions F β†’ c and H β†’ c apply). Ambiguous grammars cannot be LR(1).

Final conclusion: Neither of the statements is correct because the grammar is ambiguous, making it neither LL(1) nor LR(1).

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

Explore the full course: Gate Guidance By Sanchit Sir