Re: Conflicts in large grammar

[Laurence Finston]

On Sun, 5 Aug 2007, Hans Aberg wrote:

> When I tried it, it worked:
> $ bison parser.y++
> parser.y++: conflicts: 455 shift/reduce, 1 reduce/reduce

I never upload non-working versions.  If I have a similar question
again, I'll upload examples to an ftp server.  Sorry for the
inconvenience this time.

> So then it hard for anyone but yourself to fix the problem. If you are sure it
> is a bug, report it to Bison Bugs <address@hidden>. Be sure to include
> relevant data.

No, I'm sure it's not a bug in Bison, just something Bison's not meant
or equipped to handle, or me trying to use Bison in a way it's not
meant to be used.

> It is your grammar, but I think it will be unmanageable. 

Well, it's not completely mine.  It's based on the grammar of
Metafont, written by Donald Knuth.  However, he implemented his parser
from scratch in Pascal. I used his description of the grammar in
Backus-Naur as the basis of the rules I've written in Bison.  

However, Metafont doesn't define that many types or operations, so my 
grammar has become much larger than the grammar of Metafont.  I've also 
made some changes because of the way Bison works.

While it is somewhat large and complex, many of the rules fall
into patterns that are repeated over and over for the various types.
I have a pretty good overview of it, having written every line of it.
I'm sure it would be difficult for someone else to understand, coming
to it now, without having read it when it was smaller and simpler.  I
think a knowledge of the rules of the Metafont grammar would be nearly
indispensable.  It's a moot point, however, since no one has ever
expressed an interest in understanding it.  

The problem (if it is a problem) with the shift/reduce conflicts appeared 
very early on.  The correct resolution is always to shift, so I didn't 
worry about it, unless a rule caused a large increase in the number of
s/r conflicts.  I didn't think that it caused extra work for Bison or
that they needed to be kept track of.  If they do, I may have problems
that will probably not be so easy to solve.

> The Bison has a
> suggestion for fixing reduce/reduce conflicts. In, some cases, when it can't
> be resolve compile time, one may have to use GLR (%glr). 

I'll have to look this up, but I think there may have been some issue
with using GLR.  If the `yyparse' generated when using this option
isn't thread-safe, I won't be able to use it.

There is only one reduce/reduce conflict.  I don't remember the
details, since I wrote those rules so long ago, but it has to with the
syntax for defining a `path' using `points' and "connectors", i.e.,
something very basic to a Metafont-like language.  I determined at the
time after a lot of fiddling that I couldn't do anything about it, but
that the parser behaved the way I wanted it to.

> I think there is an
> example of how to do that with C++. But one has been able to make a LALR(1)
> for C++, too. 

I'm not sure whether this is relevant, but I only use C++ in the
actions;  Bison generates the regular C version of `yyparse'.

> So it is a question of style. Even if a language has given
> grammar, it may not be adapted for a parser general. So rewriting it
> is normal implementing.

I'm sure you're right, and it's always been a matter of compromise.
I've been getting very good results with Bison for the 6 years I've
been working on this project.  I simply don't have the knowledge to
write a parser from scratch, and I doubt that I would want to
implement one the way Knuth did in the 1980's using Pascal, even if I
had the leisure to read through his code.  I'm sure he did it very
well, but that's not the point.

If I had invented the grammar from scratch, I surely would have tried
to avoid all shift/reduce conflicts.  However, they seem to be
inherent in Knuth's rules, when one tries to implement them using
Bison.  

I just tried getting rid of all the `any_variable: <type>_variable'
rules, but it didn't work:  I got five fewer s/r conflicts but four
additional r/r conflicts, and input that previously worked caused an
error at run-time.  That is, it caused an error in one of my
functions, not an error affecting the run environment.  Obviously,
this will require some thorough investigation. 

I don't really think that my grammar needs a major rewrite, even if I
had the time for something like that.  I will try to get rid of any
unnecessary rules and simplify the grammar wherever I can.  I had
already determined that it works better to have more rules that are
simpler instead of fewer rules that are more complicated.

In case anyone wants to try running the program, there's an option for
outputting the debugging output produced by Bison, namely
`--bison-trace' (can be abbreviated to `-bi').

I've put an example in the attached file `ttemp.txt'.

Thanks again,

Laurence

ttemp.txt
Description: Text document