Re: Conflicts in large grammar

[Hans Aberg]

On 5 Aug 2007, at 09:47, Laurence Finston wrote:

> > Since the files are rather large, did you considering provide a  
> > URL instead.
>
> The relevant source code is here:
>
> http://cvs.savannah.gnu.org/viewvc/3dldf/3dldf/Group/CWEB/
> (a subdirectory of the CVS repository for GNU 3DLDF)
>
> It contains the files `parser.output', `parser.y++', `parser.c++',
> `parser.h', and `parser.h++'.  There is also a CWEB file `parser.w'
> which includes all of the other files with the suffix `.w'.  The
> latter contain the source code.

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

$ bison --version
bison (GNU Bison) 2.3a+
Id: ChangeLog,v 1.1702 2007/05/26 20:08:18 jdenny Exp
Written by Robert Corbett and Richard Stallman.

Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There  
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR  
PURPOSE.

> I didn't mention this because I didn't upload any of the versions
> which failed or produced over 800 shift/reduce conflicts.

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.

> > Conflict are a problem if the resolution that Bison does (shift  
> > before reduce,
> > first reduce in rule list) does not result in the correct parsing.  
> > Keeping
> > track of hundreds of conflicts are resoled correctly seems rather  
> > difficult.
>
> In my grammar, shift/reduce conflicts are always resolved correctly by
> shifting.  I can't get rid of the one reduce/reduce conflict, because
> it's been inherited from the grammar of Metafont, which is what my
> grammar is based on.  I've made sure that it is resolved correctly,
> too.
>
> Often, when I add a rule, the number of shift/reduce conflicts
> increases by a small number.  I have therefore watched it grow slowly
> over the years.  If it increases by more than a couple, I fix it,
> otherwise, I don't worry about it.  So far, I've always been able to
> fix large (say, >= 10) increases in the number of shift/reduce
> conflicts.

It is your grammar, but I think it will be unmanageable. 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 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. 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.

  Hans Aberg