Project ForgeSign up free
Compiler Design
Lexical Analysis & Parsing
GATE 2007
Hard

Consider the following two statements: P: Every regular grammar is LL(1). Q: Every regular set has a LR(1) grammar. Which of the following is TRUE?

  • ABoth P and Q are true
  • BP is true and Q is false
  • P is false and Q is true
  • DBoth P and Q are false

Explanation

P is FALSE: being a regular (right-linear) grammar does not automatically guarantee LL(1)-parseability without transformation — some regular grammars are ambiguous or have conflicting productions requiring more lookahead. Q is TRUE: regular languages are a proper subset of deterministic context-free languages, and DCFLs are exactly the languages with an LR(1) grammar, so every regular set has some LR(1) grammar.

Source: GATE CS 2007 (2007)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free