Re: LR (k) vs. LALR

"Tim Bauer" <tbauer@cadrc.calpoly.edu>
10 Aug 2004 17:32:49 -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)
[3 later articles]
| List of all articles for this month |

From: "Tim Bauer" <tbauer@cadrc.calpoly.edu>
Newsgroups: comp.compilers
Date: 10 Aug 2004 17:32:49 -0400
Organization: Cal Poly, SLO
References: 04-08-037
Keywords: parse
Posted-Date: 10 Aug 2004 17:32:49 EDT

> [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)?


> 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 following page:
http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html
contains a neat explination of some of the hoops the designers went through
to make the grammar LALR(1). It contains a list of five problems and
shows the solution chosen. While the grammar for Java is probably
irrelevant,
the heuristics to convert an LALR(k) grammar to LALR(1) might prove useful
to you. I certainly enjoyed the read.
Regards,
- Tim


Post a followup to this message

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