Re: Grammar LR(1) but not LALR(1)

Oliver Zeigermann <oliver@zeigermann.de>
2 Nov 2003 14:44:33 -0500

          From comp.compilers
Related articles
Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-10-31)
Re: Grammar LR(1) but not LALR(1) oliver@zeigermann.de (Oliver Zeigermann) (2003-11-02)
Re: Grammar LR(1) but not LALR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2003-11-02)
Re: Grammar LR(1) but not LALR(1) stefan@infoiasi.ro (ANDREI Stefan) (2003-11-08)
Re: Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-11-08)
Re: Grammar LR(1) but not LALR(1) RLake@oxfam.org.uk (2003-11-11)
| List of all articles for this month |
From: Oliver Zeigermann <oliver@zeigermann.de>
Newsgroups: comp.compilers
Date: 2 Nov 2003 14:44:33 -0500
Organization: T-Online
References: 03-10-139
Keywords: parse, LR(1), question
Posted-Date: 02 Nov 2003 14:44:33 EST

If I understand this correctly it boils down to the question: If there
is an LR(1) grammar for a language, is there an LALR(1) grammar for the
same language as well? If I remember correctly, the simple answer is
"yes" (can not find it the literature, though). The long answer is there
is no known algorithm that does so in all possible cases, but you will
hava to do it by hand.


Experts, any pointer to this stuff in the literature? Or am I wrong?


Oliver


> I'm convinced that such a transformation (contructing an LALR(1)
> grammar by duplicating productions) is possible for every LR(1)
> grammars, such duplication preventing the merge of the states LR(1)
> automaton.

Post a followup to this message

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