Re: LR (k) vs. LALR

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

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