Re: Bison - LR(1) parser-generator

[Hans Aberg]

On 10 Apr 2007, at 15:59, Rob Quill wrote:

> Did I imagine it, or did I read somewhere that one of the suggested
> improvements of Bison was to make it produce LR(1) parsers,

Yes.

> as LALR(1)
> is used because they produce smaller tables, but now the memory
> restriction is not so great, it is not as necessary to use LALR?

LR(1) is bigger and may grow exponentially. But one flaw of LALR(1)  
is that the states are being merged in a way that an error token may  
not be reported immediately, but some reductions may take place  
before that. This destroys (or makes difficult) accurate error  
handling, and also, makes it difficult for an interactive parser that  
wants to display the completion tokens (as they will be spread on a  
sequence of reductions). One can though merge states in LR(k) as well  
in the same manner as in LALR(1).

This stuff has been discussed here and there in the Bison lists.

  Hans Aberg