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.

Improve this question
$\endgroup$
15
  • $\begingroup$ Why do you think your grammar is LR(0)? $\endgroup$
    – Yuval Filmus
    Jan 9, 2017 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, 2017 at 14:35
  • 1
    $\begingroup$ Hm. In Sipser's book, he says that every DCFL has an LR(0) grammar... $\endgroup$
    – xavierm02
    Jan 10, 2017 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, 2017 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, 2017 at 21:16

2 Answers 2

Reset to default
3
+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.

Improve this answer
$\endgroup$
0
$\begingroup$

As an conceptual understanding we can think of it as the grammars which satisfies prefix property can be reduced without even using look ahead as those can be accepted by DPDA which accepts through empty stack, but if language is not satisfying the prefix property we will have to check whether the look ahead is $ or any character, if its $ then we can reduce it otherwise we will have to scan input further. DPDA(empty stack acceptance) is less powerful than DPDA(final state acceptance), thats why LR(0) is less powerful than LR(1) Hope this helps.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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