Re: Practical LALR(1) grammer?

Hans Aberg wrote:
> John Levine <johnl@iecc.com> 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

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