|LR (k) vs. LALR email@example.com (Profetas) (2004-08-09)|
|Re: LR (k) vs. LALR firstname.lastname@example.org (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 email@example.com (Jean-Marc Bourguet) (2004-08-11)|
|Re: LR (k) vs. LALR firstname.lastname@example.org (2004-08-15)|
|Re: LR (k) vs. LALR email@example.com (Clint Olsen) (2004-08-23)|
|Re: LR (k) vs. LALR firstname.lastname@example.org (Jeremy Wright) (2004-08-25)|
|Re: LR (k) vs. LALR email@example.com (Sylvain Schmitz) (2004-09-03)|
|Re: LR (k) vs. LALR firstname.lastname@example.org (2004-09-03)|
|Re: LR (k) vs. LALR email@example.com (Sean Case) (2004-09-07)|
|Re: LR (k) vs. LALR cfc@shell01.TheWorld.com (Chris F Clark) (2004-09-07)|
|From:||firstname.lastname@example.org (Kamal R. Prasad)|
|Date:||15 Aug 2004 22:18:30 -0400|
|References:||04-08-037 04-08-055 04-08-073|
|Posted-Date:||15 Aug 2004 22:18:30 EDT|
Jean-Marc Bourguet <email@example.com> wrote in message news:04-08-073...
> "Tim Bauer" <firstname.lastname@example.org> 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)?
You reduce from LR(k) to LR(1), and then the LR(1) grammar is handled
by the LALR(1) parser generator.
> 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].
> > > 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?
By definition -no. Yacc [or its gnu equivalent Bison] does not support
more than one lookahead. Feeding such a grammar to it will result in a
reduce-reduce conflict. You need to modify your grammar to reduce
those conflicts and yet achieve the purpose.
Return to the
Search the comp.compilers archives again.