Re: Conflicts in large grammar

[Hans Aberg]

On 3 Aug 2007, at 16:49, Laurence Finston wrote:

> I've run into a problem with the grammar of GNU 3DLDF.  It's rather  
> large,
> and I believe that's part of the problem, so it's not
> possible to provide a minimal example.  I tried to attached the
> debugging output files from three runs of Bison in a tarball,
> but I kept getting my message returned.

Since the files are rather large, did you considering provide a URL  
instead.

> I've now attached them as plain
> text files.
>
> I would like to have the following rule:
>
> point_primary: GET_POINT numeric_secondary  
> conic_section_lattice_primary
>
> When I run Bison, however, I get the following, not very informative
> message:  Abort
>
> Bison succeeds when I change the rule, with varying numbers of  
> conflicts:
>
> point_primary: GET_POINT LEFT_PARENTHESIS numeric_secondary COMMA
> conic_section_lattice_expression RIGHT_PARENTHESIS
>
> -->
>
> parser.y++: conflicts: 421 shift/reduce, 1 reduce/reduce
>
> There were 420 s/r conflicts before I added the rule.  I don't  
> consider
> this to be a problem.

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.

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.

> (See debugging output file `p0.txt' in attached tarball.)
>
> *********************
>
> point_primary: GET_PATH_POINT LEFT_PARENTHESIS numeric_secondary COMMA
> conic_section_lattice_expression RIGHT_PARENTHESIS
>
> -->
>
> parser.y++: conflicts: 424 shift/reduce, 1 reduce/reduce
>
> (See `p1.txt' in attached tarball.)
>
> *********************
>
> point_primary: GET_POINT numeric_secondary COMMA
> conic_section_lattice_expression
>
> parser.y++: conflicts: 844 shift/reduce, 1 reduce/reduce
>
> (See `p2.txt' in attached tarball.)
>
> ************************
>
> The relationship between the states and the rules seems to be rather
> complex.

Right, that is dictated by the LALR(1) algorithm (plus some  
optimizations).

> When Bison has failed before, I've sometimes been able to
> fix the problem by using a `<type>_secondary' or `<type>_tertiary'
> rather than a `<type>_primary' or making a similar substition.
> This didn't work in this case.

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.

> I also tried using a different token instead of `GET_POINT', namely
> `GET_PATH_POINT'.  The results were similar, but not completely
> the same.  I really don't want to be using parentheses or
> different tokens like this if I can avoid it.

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.

> My grammar is likely to become larger and more complex as I add  
> symbols
> and and rules for more geometrical entities, so I'm afraid this will
> keep happening.
>
> Any suggestions would be much appreciated.

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

  Hans Aberg