Skip to content
GATETECH
Official PYQ · 2015Set 3 · Q31Parsing (LL, LR)MCQ1 mark

GATE CS 2015 Set 3 Q31 — Parsing (LL, LR)

Explain with AI

Consider the following grammar G

S→F∣HS \rightarrow F \mid H

F→p∣cF \rightarrow p \mid c

H→d∣cH \rightarrow d \mid c 

Where SS, FF, and HH are non-terminal symbols, p,dp, d, and cc are terminal symbols. Which of the following statement(s) is/are correct?

S1: LL(1) can parse all strings that are generated using grammar G

S2: LR(1) can parse all strings that are generated using grammar G

Choose one option
View worked solution

Answer: D

A grammar is ambiguous if there exists a string that has more than one distinct leftmost derivation (or parse tree).

Let us consider the string cc generated by the grammar GG:

  • Derivation 1: S⇒F⇒cS \Rightarrow F \Rightarrow c
  • Derivation 2: S⇒H⇒cS \Rightarrow H \Rightarrow c

Since the string cc has two distinct leftmost derivations, the grammar GG is ambiguous.

An ambiguous grammar can never be parsed by any deterministic parser, such as LL(1)\text{LL}(1), LR(1)\text{LR}(1), LALR(1)\text{LALR}(1), or SLR(1)\text{SLR}(1).

Therefore:

  • S1 is incorrect: LL(1)\text{LL}(1) cannot parse the grammar.
  • S2 is incorrect: LR(1)\text{LR}(1) cannot parse the grammar.

Thus, neither S1 nor S2 is correct.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Parsing (LL, LR) questions