Re: LR (k) vs. LALR

Sylvain Schmitz <schmitz@i3s.unice.fr>
3 Sep 2004 12:31:20 -0400

          From comp.compilers
Related articles
LR (k) vs. LALR profetas@gmail.com (Profetas) (2004-08-09)
Re: LR (k) vs. LALR tbauer@cadrc.calpoly.edu (Tim Bauer) (2004-08-10)
Re: LR (k) vs. LALR Colin_Paul_Gloster@ACM.org (Colin Paul Gloster) (2004-08-10)
Re: LR (k) vs. LALR jm@bourguet.org (Jean-Marc Bourguet) (2004-08-11)
Re: LR (k) vs. LALR kamalp@acm.org (2004-08-15)
Re: LR (k) vs. LALR clint@0lsen.net (Clint Olsen) (2004-08-23)
Re: LR (k) vs. LALR jeremy.wright@microfocus.com (Jeremy Wright) (2004-08-25)
Re: LR (k) vs. LALR schmitz@i3s.unice.fr (Sylvain Schmitz) (2004-09-03)
Re: LR (k) vs. LALR kamalp@acm.org (2004-09-03)
Re: LR (k) vs. LALR gsc@zip.com.au (Sean Case) (2004-09-07)
Re: LR (k) vs. LALR cfc@shell01.TheWorld.com (Chris F Clark) (2004-09-07)
| List of all articles for this month |
From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 3 Sep 2004 12:31:20 -0400
Organization: Compilers Central
References: 04-08-037 04-08-055 04-08-073 04-08-098
Keywords: LALR, parse
Posted-Date: 03 Sep 2004 12:31:20 EDT

Kamal R. Prasad wrote:
> Jean-Marc Bourguet <jm@bourguet.org> wrote
>
>>Every language for which a LR(1) grammar LR(1) exists has also an
>>LALR(1) grammar. (Search for the archive of this group, I started a
>>thread on the subject).
>
> The BNF remains the same as in LR(1), but the number of parser states
> is reduced in an LALR(1) parser. Either Im making a mistake or the
> text above is misleading to indicate that the grammar needs to be
> changed when moving from Lr(1) to LALR(1).
> [The moderator may want to filter out erroneous statements].


The class of LALR(1) grammars is a proper subset of the class of LR(1)
grammars, so yes, once you have obtained a LR(1) grammar for your
language, you might have to modify your grammar a bit further to make it
LALR(1). This generally involves introducing new rules to avoid some
state merges done by the LR(0) automaton which underlies the LALR(1) parser.


Regards,


--
      Sylvain


Post a followup to this message

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