Re: Practical LALR(1) grammer? (Hans Aberg)
18 Jun 2005 23:11:27 -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)
| List of all articles for this month |

From: (Hans Aberg)
Newsgroups: comp.compilers
Date: 18 Jun 2005 23:11:27 -0400
Organization: Mathematics
References: 05-06-074 05-06-076 05-06-079 05-06-086
Keywords: LALR, parse
Posted-Date: 18 Jun 2005 23:11:27 EDT

Karsten Nyblad <> wrote:

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

Bison is in the works of being modularized, admitting multiple parsing
algorithms, and multiple language output. I think that better error
recovery is on the todo list, though other things are on the top of
the stack right now.

A few years ago, it would probably have been correct saying that Bison
was dying a slow death, but I am not sure that is true now, in view of
those changes.

> 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), ...

If you are looking for better error recovery, there seems to be problem
with LALR, in that, when an error token is seen, some further reductions
may be performed. This is especially bothersome if one wants to
interactively display the possible completion in a grammar, since the
display may be erroneous relative what will actually happen in the parser.
It is funny that it is this error recovery problem, and not any proper
parsing problem that, seems speaking against LALR. One can perhaps tweak
LALR, to fix this particular problem, though. Also, as computers get
faster, this gives room for more compression techniques, so that one may
use some kind of compressed LR. There is a mixed bag of possibilities.

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

A Berkeley, they evidently have their own Bison version, tweaked for
their research. One idea of modularizing Bison, is helping to avoid
such duplicate work. You might want to check with Akim Demaille, if it
might be more suitable for you to add some module to Bison.

    Hans Aberg

Post a followup to this message

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