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

"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.


"tj brandowsky" wrote:
> I'm really looking I guess for a good text that is rich in automata
> theory, talkings about Chomskey, and then goes into rigorous
> definitions if LR(k), GLR, LALR(k), LL(k).


I suggest the two volumes on parsing theory by Sippu and
Soisalon-Soininen:


Sippu, S. and E. Soisalon-Soininen (1988).
        Parsing Theory. Vol.1: Languages and Parsing,
        Vol. 15 of EATCS Monographs on Theoretical Computer Science.
        Springer.
Sippu, S. and E. Soisalon-Soininen (1990).
        Parsing Theory. Vol.2: LR(k) and LL(k) Parsing,
        Vol. 20 of EATCS Monographs on Theoretical Computer Science.
        Springer.


Modern formal presentation style; in depth; mathematically rigorous in
almost every detail.


For me, the modern "classic" reference on parsing theory, succeding
Aho and Ullman's "The Theory of Parsing, Translation and Compiling".
(No Hopcroft here, John!)


Regards,
Soenke.


--
Dr. Soenke Kannapinn
String.concat[ "kan", "@", "cs.tu-berlin.de" ]

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