Re: LR (k) vs. LALR

Jean-Marc Bourguet <jm@bourguet.org>
11 Aug 2004 12:59:19 -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)
[1 later articles]
| List of all articles for this month |

From: Jean-Marc Bourguet <jm@bourguet.org>
Newsgroups: comp.compilers
Date: 11 Aug 2004 12:59:19 -0400
Organization: Compilers Central
References: 04-08-037 04-08-055
Keywords: parse

"Tim Bauer" <tbauer@cadrc.calpoly.edu> writes:


> > [Some grammars are easier to express with more than one token of lookahead.
> > You can rewrite gramars to LR(1), but sometimes at the cost of huge and
> > ugly bloat. -John]
>
> Didn't Knuth prove that any LR(k) grammar can be rewritten to LR(1), albeit
> at a potential exponetial increase in the parse tables (number of distinct
> parse items).
> However, does this extend to an LALR(k) conversion to LALR(1)?


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


> > I have a grammar that requires more than one token of look ahead,
> > is there any way that it could be solved using yacc or Bison?
>
> I do have a suggestion here. I typically see compilers/interpreters
> make some syntactic concessions and offload extra checking to the
> semantic checker.


The major raison I do this is that it is easier to give good error
message and have some good error recovery.


Yours,


--
Jean-Marc


Post a followup to this message

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