GATE CS 2007 Q53 — Parsing (LL, LR)

To determine the truth value of the statements, let us analyze them individually:

Statement P: Every regular grammar is LL(1)

• A regular grammar can have conflicts that prevent it from being $LL(1)$. For example, consider the following right-linear (regular) grammar: $$S \to aS \mid a$$
• For this grammar, both production rules for $S$ start with the terminal $a$. Specifically: $$\text{First}(aS) \cap \text{First}(a) = \{a\} \cap \{a\} = \{a\} \neq \emptyset$$ This creates a first-first conflict, meaning the parser cannot decide which production to choose with a single lookahead token.
• Therefore, this regular grammar is not $LL(1)$, making statement P false.

Statement Q: Every regular set has a LR(1) grammar

• A "regular set" is a regular language.
• Every regular language is a Deterministic Context-Free Language (DCFL).
• The class of languages generated by $LR(1)$ grammars is precisely the class of DCFLs.
• Since every regular language is a DCFL, there always exists an $LR(1)$ grammar for any given regular language.
• Therefore, statement Q is true.

Thus, P is false and Q is true, which corresponds to option C.