Re: Full LR(1) parser generator Hyacc 0.9 release

Thomas Chen wrote:
> I actually was in contact with the Bison maintainer's team last April,
> unfortunately one member (Joel) was not interested in combining this
> work into it, because he thought it couldn't handle a problem caused
> by using precedence rules to handle ambiguity (Bison couldn't do it
> either at least by then).


His making an LR(1) implementation, and what he said, it looks to me,
the the Pager algorithm cannot handle token precedence. So it does not
fit with what he is doing.


> Personally I don't think it matters, since a LR(1) algorithm is
> designed for LR(1) grammars, and all LR(1) grammars are unambiguous.
> Any solution to ambiguity are side patches, and should be orthogonal
> to LR(1) or LALR(1) algorithms. So incorporating Pager's LR(1)
> algorithm, and solve the above issue independently should not be a
> problem in my opinion.


Token precedence is sort of a standard programming technique. So if it
is not present, programmers may feel at a loss. It is though rather
limited: it only works for some S/R conflicts.


As for the resolving of grammars that lie outside the algorithm, that
can be handled using GLR techniques.


A problem with LALR compression is that the states are merged in a way
that in the event of an input error token, some extra actions may be
executed before the error is reported. This causes problems when
trying to implement exact error recovery, and also in interactive
parsers that want to report the possible completion - they are not in
the current state if using such a compression method.


So I think there should be a LR(1) parser algorithm that does not make
compression having this problem.


> Bison has been the combined efforts of many people. I would
> appreciate the idea of incorporating this into Bison.


It should though be possible to implement it into Bison as a separate
module: users invoke it say by a command %%lr-pager or something.


      Hans Aberg

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