edited by
35,344 views
75 votes
75 votes

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?

  1. Both P and Q are true
  2. P is true and Q is false
  3. P is false and Q is true
  4. Both P and Q are false
edited by

8 Answers

Best answer
96 votes
96 votes

Answer: option C

LL Grammar: Grammars which can be parsed by an LL parser.

LL parser: Parses the input from Left to right, and constructs a Leftmost derivation of the sentence(i.e. it is always the leftmost non-terminal which is rewritten). LL parser is a top-down parser for a subset of context-free languages.
An LL parser is called an LL(k) parser if it uses k tokens of lookahead when parsing a sentence and can do it without backtracking.

Consider a Grammar $G$:

  • $S \rightarrow a\mid aa$

This grammar is Regular but cannot be parsed by a LL(1) parser w/o backtracking, because here, lookahead is of 1 symbol only and in the grammar for both productions, parser while looking at just one(first) symbol, which is $a$, fails to select the correct rule for parsing.

Hence, not every Regular grammar is LL(1); Statement P is False.

LR Grammar: Grammars which can be parsed by LR parsers.

LR Parser: They are a type of bottom-up parsers that efficiently handle deterministic context-free languages(DCFL) in guaranteed linear time.

All Regular Languages are also DCFL. Hence, they all can be parsed by a LR(1) grammar. 

Hence, Statement Q is True.

selected by
45 votes
45 votes

P: This is false.

Every regular language is LL(1) meaning we have a LL(1) grammar for it. But we can not say same about every Regular Grammar. For example, every regular language can be represented by Left & Right Linear Grammar, where Left Linear Grammar is not LL(1), Right linear is.

Example $aa$* we can represent this as $S \rightarrow Sa|a$ which is not LL(1) ,but $S \rightarrow a|aS$ is LL(1).

Q: This is true because of every LL(1) is LR(1).

All regular sets have Right recursive grammar, which is LL(1) & Every LL(1) is LR(1).

We can also say that LR(1) accepts DCFL & Regular languages are subset of DCFL.

So Answer is C.

edited by
14 votes
14 votes
P : FALSE because a left-linear regular grammar can be left-recursive and left recursive languages cannot be LL(1)

Q: TRUE because every regular set (or language) has a right-linear deterministic (or left-factored) unambiguous grammar and thus, every regular language can have an LL(1) grammar. Since every LL(1) grammar is also LR(1), Q is true.

NOTE : For, every regular language, there exists an unambiguous grammar because regular languages are acceptable by DFAs and unambiguity is a property of non-determinism.
edited by
4 votes
4 votes
since every regular set can be written is left recursive as well in right recursive and a grammar written in right recursive is LL(1) and we know every LL(1) is LR(1) . So it is true
Answer:

Related questions

15 votes
15 votes
3 answers
4
Kathleen asked Sep 21, 2014
9,565 views
Which one of the following is a top-down parser?Recursive descent parser.Operator precedence parser.An LR(k) parser.An LALR(k) parser.