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

Thomas Chen wrote:


> Token precedence is a way of handling syntax ambiguity.


John Levine wrote:


  > [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]


Though I haven't seen a formal proof of the latter, I agree that is the
gist of it.


Thomas Chen wrote:


> LR(1) grammars
> are all non-ambiguous and LR(1) algorithms are not supposed to handle
> ambiguity.


So here the problem is one does not design LR(1) or whatever language
class languages: one designs computer languages that hopefully, by some
tweaking can be implemented using the parser generator as a tool.


So one is programing, and as indicated above, using precedences help to
structure the code. So it would be useful even if it does not enlarge
the language class. Not having it, might be frustrating.


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


I haven't followed his work closely, but if your interpretation seems
right, it is a %ielr, not %lr ,option.


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


Token precedences depend on the parsing algorithm, or at least, I
haven't seen a proof that it is parsing algorithm independent:


I made a method where precedences can be implemented by constraining the
expansions in the rules. Then I know that such a grammar with restraints
can be rewritten into a CFG. So by that I know, it is a properly of the
grammar alone and not the parsing algorithm.


It would be nice to see something similar for token precedences. The
variations I have seen just modifies the generated push-down automaton.


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


I think that the Bison LALR(1) uses optimizations beyond what is
mentioned in the Aho, Sethi & Ullman book. Also, one point is that it
does not need to compute any LR(1) states, but only SLR(0) or something,
so that the computations are linear, not exponential.


At the same time, it means that the LALR(1) algorithm implementation
parts are likely not of big help if one wants to implement LR(1).


And that, in turn, makes it interesting to have at least of
unadulterated LR(1) implementation into Bison. It could then be helpful
for implementing variations having various optimizations.


> The way Hyacc implements Pager's algorithm is as an
> addition to the canonical Knuth LR(1) algorithm.


So such optimizing versions of LR(1) might be interesting if one can
select them by some option. - It is then possible for experts to compare.


> If Bison and Hyacc do
> it in different backbone algorithms, ...


Likely, Bison does not have anything right now helping tho implement
algorithmic parts of LR(1).


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


Akim Demaille worked on this modularization, so ask him, I think. (Check
the Bison lists.)


      Hans Aberg

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