4
$\begingroup$

Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar."

And wiki says, "a language can be generated by an LR(k) grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar"

Is the first statement in that discussion forum is correct?

I found wiki statement at many places but nowhere I found the first statement except in that discussion.

Please tell me if first one is correct or not, and If possible provide some source that confirms this statement. Thanks in advance.

$\endgroup$
5
  • $\begingroup$ Have you checked standard textbooks? $\endgroup$ Jan 10, 2017 at 10:55
  • $\begingroup$ I didn't find it anywhere. $\endgroup$ Jan 10, 2017 at 12:34
  • $\begingroup$ Try less-standard textbooks. This is a classical topic and the answer shouldn't be too hard to find. $\endgroup$ Jan 10, 2017 at 12:35
  • $\begingroup$ "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar" you mean, this statement is true ? $\endgroup$ Jan 10, 2017 at 12:36
  • $\begingroup$ I have no idea, but every textbook with a decent treatment of these grammar families would contain an answer. $\endgroup$ Jan 10, 2017 at 12:39

1 Answer 1

4
$\begingroup$

The linked discussion thread comes from comp.compilers, which at one time was the definitive discussion forum for questions of this form (disclaimer: I was a constant reader and occasional contributor to that forum, so my opinion might be biased.)

The rather interesting discussion thread in question dates from October 2002, and was an attempt to discover if there were unambiguous languages (not grammars) which could not be parsed with any $LR$ algorithm. In the course of the discussion, Sönke Kannapinn noted that the $LR(k)$, $LALR(k)$ and $SLR(k)$ sets of languages are identical, for all $k\ge 0$. (That's the message cited in the question, but in a more readable presentation.)

Kannapinn cites the source of his assertion: the 1990 text Parsing Theory Vol II by S. Sippu & E. Soisalon-Soininen, which definitely should be considered a "standard" textbook (as Kannapinn notes in an earlier message in the same thread). The question is addressed in Chapter 6.6 (SLR(k) Parsing, from pages 70-84), which terminates with Theorem 6.71:

For any fixed $k>=0$, the families of $LR(k)$ languages, LALR(k) languages and SLR(k) languages are all equal.

The proof is too long to reproduce here, but the textbook should be available in any good university library. (If it isn't, demand that they acquire it.)

Coincidentally, there was another similar discussion thread the next year, in which I offered a simpler proof outline. I reproduce it here (without modification aside from an attempt to fight with MathJax and Markdown to make it a bit more readable), in case it's useful to someone, although of course it might be wrong since discussion posts in comp.compiler are not subject to the thorough review accorded to Springer Monographs. So if you find an error, let me know, and if you find the formatting ugly, feel free to fix it.

Take an $LR(1)$ grammar $$G = <N, T, P, S>$$ and create $$G' = <N', T, P', <S,\$> >$$ where $N'$ is a subset of $N \times T$ (that is, the non-terminals in G' are the cartesian product of the original non-terminals and the original terminals.) $N'$ and $P'$ are constructed basically with the LR construction: Start with $N' = \{<S, \$>\}$ and repeat the following until no new non-terminals are added:
  • Let $<A, a>$ be an element of $N'$ for which there are no productions in $P'$. Now, for each production in $P$ of the form: $$A \to w_1 w_2 ... w_n$$ add all possible productions $$<A, a> \to w'_1 w'_2 ... w'_n$$ where $$w'_i = w_i \text{ if } w_i \in T$$ $$w'_i = <w_i, b> \text{ for each } b \in FIRST(w_{i+1}...w_n ++ a) \text{ if } w_ \in N$$ The second definition is multiple valued, so you might have to add a lot of rules :)
  • Furthermore, if any new rule mentions a non-terminal $<W, w>$ which is not yet in $N'$, add it to $N'$
It is clear that this must terminate, because all the sets are finite. Also, the function $FIRST$ used above never yields epsilon.

Now, I assert that $G'$ recognises exactly the same language as $G$, and furthermore that if $G$ is $LR(1)$ then $G'$ is $SLR(1)$, because it is impossible to have a reduce/reduce conflict between $<W, a>$ and $<W, b>$.

Of course, all this has done is move the lookahead sets into the definition of the non-terminals, so the resulting $SLR$ table is going to be just as big as the original $LR$ table (bigger, actually, since no merging of lookaheads has been done), but I think it does answer the original question.

$\endgroup$
1
  • $\begingroup$ Thank you so much, you made it simple otherwise it won't be possible for me to figure out. But unfortunately I can't upvote as i am new user :( If u can give me some hint for this also then this would be great cs.stackexchange.com/questions/68455/… Thnks in advance :) $\endgroup$ Jan 10, 2017 at 17:14

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.