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.