Re: Conflict counterexamples

[Adrian Vogelsgesang]

Hi Akim, hi Vincent

> Vincent Imbimbo recently contributed a complete system to generate 
> counterexamples when there are conflicts
That's amazing!
Thanks for building that feature! :)
I didn't have time to try it yet, but I am pretty sure this will help me save a 
lot of time


To your questions:

> 1. Where
I would definitely prefer to have it on the command line instead of the .output 
file. 

First, our CI and our build scripts at the project I am working on don't keep 
the .output file around, but they report stderr/stdout. We could of course 
adjust our build scripts, but stderr would make my life easier.

Furthermore for myself when debugging a grammar having to open the .output file 
is always an extra step. I would prefer not to have to do that extra step.

And last, but not least: Afaict, bison prints errors in a gcc-compatible 
format. Many IDEs support directly highlighting the parts of your code which 
correspond to a warning produced by gcc. It would be amazing if I could see the 
errors, including counterexamples directly in vim or VisualStudio Code - 
however I never tried and I am not sure if it would actually work

> 2. When
Your proposed solution sounds good to me

> 3. How
Preferably in a format such that vim/VisualStudio Code can pick it up and 
render it next to the corresponding lines.
Not actually sure what that requires...

Among the two styles which you shared, I personally prefer the first one, i.e.
[ "if"  exp  "then"  exp ::=[ "if"  exp  "then"  exp  • ]  "else"  exp ]
vs.
["if"  exp  "then"  exp ::=[ "if"  exp  "then"  exp  •  "else"  exp ] ]
since that makes the ambiguity more obvious to me.

Those are the most valuable two lines to me and they should be right next to 
each other. By comparing those two lines, the ambiguity becomes obvious.

In your example, it took me some time to actually spot them. I am not sure what 
all those other lines actually tell me, I would prefer to reduce the verbosity 
a bit. To make it even simpler to spot the ambiguities, one could align the two 
derivation under each over horizontally, such that the different position of 
the "]" becomes more obvious.

The 2nd example makes it easier to understand the "state of the parse stack" 
than the first example.
E.g., it was easier to me to understand which of the derivations corresponds to 
a reduce ("finish this level and go back up"), and which one corresponds to a 
shift ("stay on the same level").
The ambiguity on the other hand is less obvious since it only becomes apparent 
after mentally combining multiple lines.

Usually I care more about the "what is ambiguous" than about "is it a reduce or 
a shift".
That's because to fix my grammar I have to understand "why is it ambiguous?" 
first.
Only after that I can consider my options ("introduce a new keyword", 
"restructure my language", "use %prec to resolve the conflict", "change 
operator precedence", ...).
Personally, I usually settle for one of the first two options, i.e. changing 
the language. And for those options I never actually care "which one is the 
shift, which one is the reduce".

The distinction "which one is the reduce, which one is the shift" is really 
only necessary if I want to resolve the conflict by annotating my grammar with 
corresponding precedence rules. I am currently wondering, if we might want to 
simplify this use case, too, and add hints like "to choose derivation one, add 
%prec ..." to the error message

Cheers,
Adrian


On 05/06/2020, 16:08, "bison-patches on behalf of Akim Demaille" 
<bison-patches-bounces+avogelsgesang=tableau.com@gnu.org on behalf of 
akim.demaille@gmail.com> wrote:

    Hi all,
    
    Vincent Imbimbo recently contributed a complete system to generate 
counterexamples when there are conflicts.  It works well, and will be the 
foremost feature of Bison 3.7.
    
    $ bison -Wcounterexample foo.y
    Shift-Reduce Conflict:
    7:    1 exp: "if" exp "then" exp .
    7:    2 exp: "if" exp "then" exp . "else" exp
    On Symbol: "else"
    Example  "if"  exp  "then"  "if"  exp  "then"  exp  •  "else"  exp
    First  derivation  exp ::=[ "if"  exp  "then"  exp ::=[ "if"  exp  "then"  
exp  • ]  "else"  exp ]
    Second derivation  exp ::=[ "if"  exp  "then"  exp ::=[ "if"  exp  "then"  
exp  •  "else"  exp ] ]
    foo.y: avertissement: 1 conflit par décalage/réduction [-Wconflicts-sr]
    
    
    However, there is a number of design decisions to make.
    
    
    1. Where
    
    We need to decide where the counterexamples should appear.  Vincent has 
added a -Wcounterexample flag, and the diagnostics are then on stderr.
    
    Historically if you wanted to understand your conflicts, you had to read 
the *.output file; on this regard, I believe it makes more sense to issue this 
additional information into the *.output file too.  However, one could also 
claim that now, precisely thanks to -Wcounterexample, in many cases you no 
longer need to go to your *.output, the diagnostic may suffice.
    
    One answer, of course, could be that it should be the user's choice: 
--report=counterexample adds this information in the report, and 
-Wcounterexample does that for the diagnostics.
    
    
    2. When
    
    Vincent had originally included -Wcounterexample into -Wall (I think that 
was more by accident than by design).  I removed it from -Wall, because looking 
for counterexamples can be very costly (after all, grammar ambiguity is 
undecidable...).  There's a timeout mechanism that guarantees that bison 
terminates, but still, running these computations when you don't actually care 
about them (i.e., when you accepted your conflicts and use the -Wall in your 
CI) is a pure waste of time and resources.
    
    If -Wcounterexample is not part of -Wall, then people should be told of its 
existence, since most of them don't read the manual or/and NEWS.  I think we 
should issue a message such as:
    
    $ bison -Wall foo.y
    foo.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    foo.y: warning: counterexamples can be generated.  Rerun with option 
'-Wcounterexample'. [-Wother]
    
    
    3. How
    
    There might be other ways to display the diagnostics.  For instance, I have 
been playing with colors (if you're reading the mail in text, that won't work 
here):
    
    $ bison -Wcounterexample foo.y
    Shift-Reduce Conflict:
    7:    1 exp: "if" exp "then" exp .
    7:    2 exp: "if" exp "then" exp . "else" exp
    On Symbol: "else"
    Example  "if"  exp  "then"  "if"  exp  "then"  exp  •  "else"  exp
    First  derivation  exp ::=[ "if"  exp  "then"  exp ::=[ "if"  exp  "then"  
exp  • ]  "else"  exp ]
    "if"  exp  "then"  "if"  exp  "then"  exp  •  "else"  exp
    
    Second derivation  exp ::=[ "if"  exp  "then"  exp ::=[ "if"  exp  "then"  
exp  •  "else"  exp ] ]
    "if"  exp  "then"  "if"  exp  "then"  exp  •  "else"  exp
    
    foo.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
    
    But there are certainly other ways we could display the derivations, say:
    
    First  derivation
      exp
      |
      +- "if"  exp  "then" exp "else"  exp
                           |
                           +- "if"  exp  "then"  exp  •
    
    Second derivation
      exp
      |
      +- "if"  exp  "then"  exp
                            |
                            +- "if"  exp  "then"  exp  •  "else"  exp
    
    
    or
    
    First  derivation
      [exp]
      => "if"  exp  "then" [exp] "else"  exp
      => "if"  exp  "then" "if" exp "then"  exp •  "else"  exp
    
    Second derivation
      [exp]
      => "if"  exp  "then" [exp]
      => "if"  exp  "then" "if" exp "then"  exp  •  "else"  exp
    
    We could also use graphviz to generate images.  I don't think I can attach 
images here, but if you have graphviz/dot, I attach both the result and the dot 
sources for two different ways to render the counterexamples.
    
    Opinions, suggestions, comments would be most welcome.  Cheers!