Grammar that bison/byacc reports 35 reduce/reduce conflicts but happy none

[mingodad]

While converting this grammar https://github.com/diku-dk/futhark/blob/master/src/Language/Futhark/Parser/Parser.y to use in https://mingodad.github.io/parsertl-playground/playground/ I found that bison/yacc/kmyacc reports 35 reduce/reduce conflicts but happy none.

Attached is the grammar converted using happy -i command line to get the expanded grammar and adding the missing parts manually (%tokens, %prec, ...):

happy -v
Happy Version 1.19.8 Copyright (c) 1993-1996 Andy Gill, Simon Marlow (c) 1997-2005 Simon Marlow

happy -i Parser.y

bison-nb -v Parser-yacc.y
Parser-yacc.y: warning: 35 reduce/reduce conflicts [-Wconflicts-rr]
Parser-yacc.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
Parser-yacc.y:209.8-21: warning: rule useless in parser due to conflicts [-Wother]
  209 | Exp2 : Atom ".." Exp2 ;
      |        ^~~~~~~~~~~~~~

grammars.zip

[andreasabel]

The translation of these precedences https://github.com/diku-dk/futhark/blob/aaf9939c6955abf2b55ff0b1f3e07f445ea2b537/src/Language/Futhark/Parser/Parser.y#L165-L186 to bison seems to be written at

• https://github.com/BenHanson/parsertl14/issues/15

@mingodad What would be an example that parses wrongly with the happy-generated parser because happy misses conflicts? And what would be the LR state that should display a conflict? (For LR state description see e.g. the happy-generated .info file.)

[andreasabel]

The happy grammar has this:

%right '...' '..'
%left juxtprec

RangeExp
  : Exp2 '...' Exp2     
  | Exp2 '..' Exp2 '...' Exp2 

Exp2 
     | RangeExp                  
     | Exp2 '..' Atom            
     | Atom '..' Exp2   
     | ApplyList 

ApplyList 
          : Atom ApplyList %prec juxtprec
          | Atom %prec juxtprec

The bison grammar has the same:

%right "..." ".."
%left juxtprec

RangeExp : Exp2 "..." Exp2 ;
RangeExp : Exp2 ".." Exp2 "..." Exp2 ;

Exp2 : RangeExp ;
Exp2 : Exp2 ".." Atom ;
Exp2 : Atom ".." Exp2 ;        
Exp2 : ApplyList ;
ApplyList : Atom ApplyList %prec juxtprec ;
ApplyList : Atom %prec juxtprec ;

The counterexample given by bison is:

$ bison -Wcounterexamples --report=cex Parser-yacc.y 
Parser-yacc.y: warning: 35 reduce/reduce conflicts [-Wconflicts-rr]
Parser-yacc.y: warning: reduce/reduce conflict on tokens "...", ...
  Example: Exp2 ".." Atom • "..." Exp2
  First reduce derivation
    RangeExp
    ↳ 274: Exp2                    "..." Exp2
           ↳ 170: Exp2 ".." Atom •
  Second reduce derivation
    RangeExp
    ↳ 277: Exp2 ".." Exp2                 "..." Exp2
                     ↳ 178: ApplyList
                            ↳ 180: Atom •
Parser-yacc.y:209.8-21: warning: rule useless in parser due to conflicts [-Wother]
  209 | Exp2 : Atom ".." Exp2 ;
      |        ^~~~~~~~~~~~~~

So bison claims here that Atom -> ApplyList -> Exp2 is a valid reduction even if the next token is "..." which has a higher precedence ("...") than the rule ApplyList: Atom (juxtprec).

According to happys spec, this is not a valid reduction, see https://haskell-happy.readthedocs.io/en/latest/using.html#how-precedence-works . So, from the perspective of happy, there is no conflict.

@mingodad Can you argue that a conflict actually exists? Or how should we proceed with this issue?

[mingodad]

The documentation https://haskell-happy.readthedocs.io/en/latest/using.html#how-precedence-works clearly talk about shift/reduce but not about reduce/reduce. I'm still making my head around this issue like in the lemon parser as well https://sqlite.org/forum/forumpost/9cb2fc0e6e11768c .

The main issue is applying precedence to mask/hide/resolve reduce/reduce conflicts intentional or unintentional, I mean we can add precedence to solve shift/reduce conflicts but it also can hide as solved reduce/reduce conflicts in other places without letting us now about then.

For example the sqlite3 grammar splitting expr in expr/expr2 seems to fix the reduce/reduce conflict (still in testing) like PostgreSQL does (also CG-SQL) see https://mingodad.github.io/parsertl-playground/playground/ in examples SQLite3 parser (partially working) and SQLite3 modified parser (partially working).

I'm still working on it and as soon I found an answer I'll tell you.

[ricomariani]

I hadn't considered the possibly that bison doesn't use precedence at all for the reduce/reduce case. In this case it seems that one of the choices would immediately lead to a syntax error and happy figures that out. I think Bison doesn't have enough lookahead to see that it will be in a corner...

[BenHanson]

The best I could find is https://www.ibm.com/docs/en/zos/2.1.0?topic=ambiguities-rules-help-remove

"Precedence is not consulted in reduce-reduce conflicts. yacc always reduces by the earliest grammar rule, regardless of precedence"

I wasn't sure if this also applied to bison, which is why I resorted to looking at the bison source code.