Re: LR Grammars not in LALR(1) or LR(1)

"=?Windows-1252?Q?S=F6nke_Kannapinn?=" <soenke.kannapinn@wincor-nixdorf.com> wrote:


>"Hans Aberg" wrote:
>> but I have an old book by Robin Hunter, "Compilers...", which says on page
>> 103 that LR(k) grammars are LR(1) grammars, and even LR(0) if each sentence
>> is given an end-marker, citing a paper by Hopcroft and Ullman, "Introduction
>< to Automata Theory, Languages and Computation" 1979.


>That's wrong! (Hope it's not wrong in that book!)
>It mixes up the concepts of 'language' and 'grammar'.
>The class of LR(k) languages (!) is identical to the class of
>LR(1) languages (!), for k >= 1.
>But not every LR(k) grammar is also an LR(1) grammar.


Sorry, I was sloppy in the use of the terminology. It should (of course) be:


    but I have an old book by Robin Hunter, "Compilers...", which says
    on page 103 that LR(k) languages are LR(1) languages, and even LR(0)
    if each sentence is given an end-marker, citing a paper by Hopcroft
    and Ullman, "Introduction to Automata Theory, Languages and
    Computation" 1979.


A language L is called LR(k) if there exists a grammar G which is
LR(k) which generates the language L, i.e. L = L(G). This is a
non-constructive set theoretic definition, which causes problems when
one takes a language L and want by an algorithm to determine whether
it is LR(k) for some k: There is no such algorithm.


It is also a problem when trying to rewrite a language from LR(k) to
LR(1) because the rewriting may not be useful with respect to the
semantics. Then that shows up in error recovery problems.


This is why GLR compilers may be suitable when studying error recovery
problem in LR(k) grammars, despite the existence of such _language_
rewriting theorems.


This reminds me that Susan L. Graham <graham@cs.berkeley.edu> who works
with error recovery in GLR parsers recently sent me a paper by Tim A.
Wagner and herself, "Incremental Analysis of Real Programming Languages".
-- Perhaps this can give some inputs to the original poster.


Also, the Bison manual <http://gnu.org>, sec. 5.7, "Mysterious
Reduce/Reduce Conflicts" has an example of a grammar which is not LALR(1).


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

Return to the comp.compilers page.
Search the comp.compilers archives again.