Re: LR (k) vs. LALR

"Tim Bauer" <>
10 Aug 2004 17:32:49 -0400

          From comp.compilers

Related articles
LR (k) vs. LALR (Profetas) (2004-08-09)
Re: LR (k) vs. LALR (Tim Bauer) (2004-08-10)
Re: LR (k) vs. LALR (Colin Paul Gloster) (2004-08-10)
Re: LR (k) vs. LALR (Jean-Marc Bourguet) (2004-08-11)
Re: LR (k) vs. LALR (2004-08-15)
Re: LR (k) vs. LALR (Clint Olsen) (2004-08-23)
Re: LR (k) vs. LALR (Jeremy Wright) (2004-08-25)
Re: LR (k) vs. LALR (Sylvain Schmitz) (2004-09-03)
[3 later articles]
| List of all articles for this month |

From: "Tim Bauer" <>
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:
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
the heuristics to convert an LALR(k) grammar to LALR(1) might prove useful
to you. I certainly enjoyed the read.
- Tim

Post a followup to this message

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