Path: utzoo!mnetor!tmsoft!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!think.com!paperboy!hsdndev!spdcc!iecc!compilers-sender
From: grosch@gmdka.uucp (Josef Grosch)
Newsgroups: comp.compilers
Subject: Re: references to yacc(1) grammar tools sought
Keywords: yacc, debug, question
Message-ID: <9102071109.AA20819@gmdka.uucp>
Date: 7 Feb 91 13:09:09 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: Josef Grosch <grosch@gmdka.uucp>
Organization: GMD-Forschungsstelle Karlsruhe, Germany
Lines: 30
Approved: compilers@iecc.cambridge.ma.us

DaviD W. Sanderson (dws@cs.wisc.edu) writes:

> I am looking for references to tools for manipulating or debugging
> yacc grammars.
> For instance, one such tool might illustrate ambiguities in a grammar
> by exhibiting sequences of grammar symbols that can be parsed more than
> one way (and hopefully showing at least two derivation trees).

The following article describes a solution to this problem:

%A Frank DeRemer
%A Thomas Pennello
%T Efficient Computation of LALR(1) Look-Ahead Sets
%J TOPLAS
%V 4
%N 4
%P 615-649
%D OCT 1982

In case of ambiguities in the grammar, derivation trees can be printed
that illustrate the conflict. We have implemented this algorithm in our
parser generator Lalr. Using a preprocessor, yacc input can be directly
processed by this tool. Our experiences are very satisfying. Looking at the
derivation trees printed for conflicts you can more or less locate the
problem immediately. The time for debugging grammars is reduced significantly.

Josef Grosch (grosch@gmdka)
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.