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

Hans Aberg wrote:
> 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.


Token precedence is a way of handling syntax ambiguity. LR(1) grammars
are all non-ambiguous and LR(1) algorithms are not supposed to handle
ambiguity. What Joel exactly wanted is an extension that handles
non-LR(1) grammars (non-LR(1) because of ambiguity) coupled with
precedence rules. I believe he recently published a paper for
this. See page 18 of
http://www.acm.org/conferences/sac/sac2008/TOC.pdf "IELR(1): Practical
LR(1) Parser Tables for Non-LR(1) Grammars with Conflict Resolution".
or here: http://www.cs.clemson.edu/~malloy/papers/papers.html I have
not read this paper carefully yet, but seems now IELR(1) is an
extension of Bison.


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


Hyacc does support token precedence the same way that Yacc and Bison
does. As I said, this is independent from the LR(1) or LALR(1) algorithms.


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


I would be glad to do so if given the chance. But at the same time
implementation of this into Bison (if so) is not without caution
though. I read Yacc source code and it was quite monolithic. I didn't
read Bison source, but according to the dragon book there were
different ways of implementing LALR, and not necessarily compatible
with Hyacc. The way Hyacc implements Pager's algorithm is as an
addition to the canonical Knuth LR(1) algorithm. If Bison and Hyacc do
it in different backbone algorithms, then the incorporation may not be
able to take advantage of the modularization in Bison, and as the
consequence it might be just "piggypacked" instead of
"incorporated". Anyway, detail matters.
[Precedence is not a way of handling ambiguity, it's a way of writing
a grammar more concisely. Anything you can write with precedence in
an LR(1) or LALR grammar you could also write by adding more rules, but
the version using precedence is shorter and easier to follow. -John]

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