Re: Practical LALR(1) grammer?

Karsten Nyblad <>
16 Jun 2005 00:09:25 -0400

          From comp.compilers

Related articles
Practical LALR(1) grammer? (2005-06-12)
Re: Practical LALR(1) grammer? (2005-06-13)
Re: Practical LALR(1) grammer? (2005-06-13)
Re: Practical LALR(1) grammer? (Andrew Wilson) (2005-06-13)
Re: Practical LALR(1) grammer? (Karsten Nyblad) (2005-06-16)
Re: Practical LALR(1) grammer? (2005-06-18)
An "open" letter to Karsten Nyblad (and other compiler compiler implem (Chris F Clark) (2005-06-18)
Re: An "open" letter to Karsten Nyblad (and other compiler compiler im (2005-06-21)
| List of all articles for this month |

From: Karsten Nyblad <>
Newsgroups: comp.compilers
Date: 16 Jun 2005 00:09:25 -0400
Organization: Compilers Central
References: 05-06-074 05-06-076 05-06-079
Keywords: LALR
Posted-Date: 16 Jun 2005 00:09:25 EDT

Hans Aberg wrote:
> John Levine <> wrote:
>>[I agree, the main appeal of LALR is that its tables used up less of
>>a 64K address space. -John]
> I had a discussion with Paul Hilfinger where he thought that, in view
> of cheaper memory, perhaps Bison should be given an LR(1) option, more
> convenient for GLR. Also, when an error token is detected, LR(1)
> issues an error immediately, whereas LALR(1) may perform additional
> reductions. This is inconvenient in error recovery, and especially in
> interactive interfaces, where one wants to display the valid extension
> of an partially entered text. So perhaps LALR(1) will slowly move out
> of use, as LR(1) becomes more readily available.

Todays computers are large enough to handle LALR(K) with K larger than
1. I am building a parser generator that can handle LALR(K), and is
capable of generating the internal data structures for an LALR(8)
parser for Ada83 in 1GB. That can be combined with state splitting
such that you can handle LR(K) grammars. Normally there are only a
few states in a parser, where you need more than one tokens lookahead.
Thus the parser generator needs only generating lookahead sets for
larger values of K in a few states.

I am trying to build such a parser generator. I have introduced new
disambiguate rules on top of the normal #left, #right and #not. This
rules specify that the parser generator should use a larger value of K
than one and/or that it should use LR(K) state splitting. However, it
is a considerable work to write such a parser generator. I think I
will have more than 30,000 lines of code, before I am finished.

IMHO bison is an outdated tool. The error recovery is neither good at
correcting errors nor easy to program. The attribute handling does
not used symbols, etc. If you exclude GLR, it represents state of the
art 1975.

Karsten Nyblad

Post a followup to this message

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