7
$\begingroup$

There are two important theorems about LR(k) grammars and DCFL. Mentioned here.

  1. A language has an LR(1) grammar iff it is DCFL.
  2. A language has an LR(0) grammar iff it is DCFL and has prefix property.

I have counter example for 2nd theorem, plz see if it is valid counterexample. (Ofcourse its not valid and I am wrong, But what wrong I am doing here ?)

DCFL without prefix property: $\{b(ab)^n \mid n\geq0\}$

2nd theorem says it should not have $LR(0)$ grammar, but here it is-

$ S \rightarrow Sab \\S \rightarrow b$

PS: This is my first question here, sorry if I violated any protocol.

$\endgroup$
  • $\begingroup$ Why do you think your grammar is LR(0)? $\endgroup$ – Yuval Filmus Jan 9 '17 at 14:22
  • $\begingroup$ @YuvalFilmus I took this example from "LR Parsing: Theory and Practice By Nigel P. Chapman" page 69 (books.google.co.in/…) $\endgroup$ – user3699192 Jan 9 '17 at 14:35
  • 1
    $\begingroup$ Hm. In Sipser's book, he says that every DCFL has an LR(0) grammar... $\endgroup$ – xavierm02 Jan 10 '17 at 0:22
  • $\begingroup$ I have another book that says that LR(0) and finite implies the prefix property. (In fact, they prove that if for two non-empty words $u$ and $v$, both $u$ and $uv$ are in $L$, then $uv^n$ is in $L$ for every $n$) $\endgroup$ – xavierm02 Jan 10 '17 at 0:31
  • 1
    $\begingroup$ yes, we are. We are giving the language prefix property and using LR(0) parser. As per definition the language should not have LR(0) grammar, but with a slight modification we can get an LR(0) grammar. I do not think a question like "is this language LR(0)" will come in any standard examination for this or similar languages as that depends on the definition being used. In literature there are many things like this - a good examination avoids them whereas a bad examination concentrates on them :) $\endgroup$ – Arjun Suresh Feb 2 '17 at 21:16
2
+50
$\begingroup$

Your grammar is $\mathrm{LR}(0)$ by adding a $\mathrm{\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\$$ when constructing the $\mathrm{LR}(0)$ automaton (and it is a standard construction).

Omitting syntactical purposes, every DCFL $\mathrm{L}$ can be parsed by an $\mathrm{LR}(0)$ grammar for $\mathrm{L}\$$. What makes $\mathrm{LR}(k)$ ($k>0$) more practical is that it may include more syntactical information which is very important in compiler design. Otherwise, all these techniques would never be used in practice. In that case, $\mathrm{LL}(k)$ with local manipulation for expressions would be used instead, even with prohibitive cost of time and space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.