Re: LR Grammars not in LALR(1) or LR(1)

thp@cs.ucr.edu wrote:


>+ Even though precedence rules can be made a part of the grammar:


>Hmmmmm. Suppose we have a YACC input that uses disambiguation rules.
>Does the standard way of removing the precedence and associativity
>ambiguities by introducing new nonterminals and grammar rules always
>yield an LALR(1) grammar? It would be nice if that were so.


I really don't know.


The topic shows up if one is going to write a parser generator that
may make use of different parsing algorithms: Then one wants a system
that defines a grammar for a language that is independent of the
parsing algorithm, so that the parsing remains the same when the
parsing algorithm is changed.


>+ I got the references:
>+ http://www.cs.uu.nl/people/visser/ftp/BSVV02.pdf


>These appear to be very useful techniques. Do you know if any tool has
>been built around them?


This showed up for the GNU Bison parser: A Spanish fellow wanted
implement an algorithm called DR. There are from time to time requests
for other algorithms like LR(1). There is a other Bison descendant
called Berkeley Yacc which is used together with Tomita and GLR
parsers (or so I think).


So Bison has made some small moves towards enabling that.


Then one would want to be able to compare those algorithms by merely
change the parsing algorithm. And then the method of disambiguation should
be independent of the parsing algorithm.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>
[Bison is actually a descendant of Berkeley Yacc, but unless something
has changed radically, they both use the same table generating and
parsing algorithms. -John]

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