Re: Conflicts in large grammar

[Laurence Finston]

On Sat, 4 Aug 2007, Hans Aberg 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.

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

> 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. 

> Have you tried resolving them using precedences %left, etc.? Look in the
> conflicting state, and apply the precedences to the tokens immediately before
> and after the "." in the conflicting shift/reduce states.

No, because the point of the `<type>_primary', `<type>_secondary', 
`<type>_tertiary', `<type>_expression' hierarchy is to set the
precedence of the rules.  This allows very fine control.  It is also
inherited from the grammar of Metafont.  I did set precedences when
declaring a few non-terminal symbols when I first started writing this
grammar, before I really understood how the expression hierarchy
worked, but I'm pretty sure that they have no effect.  I've never
gotten around to seeing what happens if I get rid of them.

> 
> So one has to fiddle around with the grammar a bit. If you had given
> a link to 
> the .y grammar, folks might have done some test-compiles.
 
It would be great if anyone wanted to.  However, `parser.y++' is not
very readable in itself and contains no comments.  
It is generated from 96 CWEB files (the files with the suffix `.w') 
containing the declarations, rules, etc.  

> For example, you have a rule
>  any_variable:
>    ...
>    | color_variable
>    ...
>  ;
> and then
>  ...
>  color_variable: variable . COLOR;
>  ...
> 
> This means that any_variable does not have a token in it, to determine which
> state to go to, which might generate shift/reduce conflicts. It might be
> better with
>  any_variable:
>    ...
>    | variable . COLOR
>    ...
>  ;

> Anyway, because of the way LALR(1) works, fiddling around a bit like that
> might help. The reason is that lookahead is just one token, so it might help
> having a token in the state. The algorithm can resolve some, but for example,
> shift/reduce resolution requires is more crude.

Thanks, that makes a lot of sense.  I was thinking about
trying to get rid of the `any_variable' rules entirely.  That may get
rid of a lot of the s/r conflicts.

> I think you need to focus on getting rid of the shift/reduce conflicts you
> already have.

Thank you very much for your help.

Laurence