Wed, 13 Feb 2008 19:35:15 +0100

Related articles |
---|

Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Tom) (2008-02-03) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg@math.su.se (Hans Aberg) (2008-02-05) |

Re: Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Thomas Chen) (2008-02-07) |

Re: Full LR(1) parser generator Hyacc 0.9 release DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-02-11) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg_20080207@math.su.se (Hans Aberg) (2008-02-11) |

Re: Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Thomas Chen) (2008-02-12) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg_20080207@math.su.se (Hans Aberg) (2008-02-13) |

Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-14) |

Re: Full LR(1) parser generator Hyacc 0.9 release cfc@shell01.TheWorld.com (Chris F Clark) (2008-02-14) |

Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-23) |

Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-24) |

Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-25) |

Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-26) |

[7 later articles] |

From: | Hans Aberg <haberg_20080207@math.su.se> |

Newsgroups: | comp.compilers |

Date: | Wed, 13 Feb 2008 19:35:15 +0100 |

Organization: | Aioe.org NNTP Server |

References: | 08-02-019 08-02-022 08-02-030 08-02-037 08-02-040 |

Keywords: | parse, LR(1) |

Posted-Date: | 13 Feb 2008 16:02:09 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.