tests/counterexample.at

   1 # Exercising Bison on counterexamples.                         -*- Autotest -*-
   2
   3 # Copyright (C) 2020-2021 Free Software Foundation, Inc.
   4
   5 # This program is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation, either version 3 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17
  18 AT_BANNER([[Counterexamples.]])
  19
  20 # AT_BISON_CHECK_CEX(TREE, FLAT)
  21 # ------------------------------
  22 m4_define([AT_BISON_CHECK_CEX],
  23 [AT_KEYWORDS([cex])
  24
  25 AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
  26 # FIXME: Avoid trailing white spaces.
  27 AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g;s/ *$//;' stderr]],
  28          [], [$1])
  29
  30 m4_pushdef([AT_SET_ENV_IF],
  31            [[YYFLAT=1; export YYFLAT;]]m4_defn([AT_SET_ENV_IF]))
  32 AT_BISON_CHECK([-Wcounterexamples input.y], [0], [], [stderr])
  33 AT_CHECK([[sed -e 's/time limit exceeded: [0-9][.0-9]*/time limit exceeded: XXX/g' stderr]],
  34          [], [$2])
  35 m4_popdef([AT_SET_ENV_IF])
  36
  37 ])
  38
  39 ## --------------------- ##
  40 ## Simple Unifying S/R.  ##
  41 ## --------------------- ##
  42
  43 AT_SETUP([Unifying S/R])
  44
  45 AT_DATA([[input.y]],
  46 [[%token A B C
  47 %%
  48 s: a x | y c;
  49 a: A;
  50 c: C;
  51 x: B | B C;
  52 y: A | A B;
  53 ]])
  54
  55 AT_BISON_CHECK_CEX(
  56 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
  57 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
  58   Example: A . B C
  59   Shift derivation
  60     s
  61     `-> 2: y            c
  62            `-> 8: A . B `-> 4: C
  63   Reduce derivation
  64     s
  65     `-> 1: a          x
  66            `-> 3: A . `-> 6: B C
  67 input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
  68 ]],
  69 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
  70 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
  71   Example           A . B C
  72   Shift derivation  s -> [ y -> [ A . B ] c -> [ C ] ]
  73   Reduce derivation s -> [ a -> [ A . ] x -> [ B C ] ]
  74 input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
  75 ]])
  76
  77 AT_CLEANUP
  78
  79 ## ------------------- ##
  80 ## Deep Unifying S/R.  ##
  81 ## ------------------- ##
  82
  83 AT_SETUP([Deep Unifying S/R])
  84
  85 AT_DATA([[input.y]],
  86 [[%token A B C
  87 %%
  88 s: ac | a bc;
  89 ac: A ac C | b;
  90 b: B | B b;
  91 a: A | A a;
  92 bc: B bc C | B C;
  93 ]])
  94
  95 AT_BISON_CHECK_CEX(
  96 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
  97 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
  98   Example: A . B C
  99   Shift derivation
 100     s
 101     `-> 1: ac
 102            `-> 3: A ac                C
 103                     `-> 4: b
 104                            `-> 5: . B
 105   Reduce derivation
 106     s
 107     `-> 2: a          bc
 108            `-> 7: A . `-> 10: B C
 109 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 110   Example: A A . B B C C
 111   Shift derivation
 112     s
 113     `-> 1: ac
 114            `-> 3: A ac                                    C
 115                     `-> 3: A ac                         C
 116                              `-> 4: b
 117                                     `-> 6: . b
 118                                              `-> 5: B B
 119   Reduce derivation
 120     s
 121     `-> 2: a                   bc
 122            `-> 8: A a          `-> 9: B bc          C
 123                     `-> 7: A .          `-> 10: B C
 124 input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
 125 ]],
 126 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 127 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 128   Example           A . B C
 129   Shift derivation  s -> [ ac -> [ A ac -> [ b -> [ . B ] ] C ] ]
 130   Reduce derivation s -> [ a -> [ A . ] bc -> [ B C ] ]
 131 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 132   Example           A A . B B C C
 133   Shift derivation  s -> [ ac -> [ A ac -> [ A ac -> [ b -> [ . b -> [ B B ] ] ] C ] C ] ]
 134   Reduce derivation s -> [ a -> [ A a -> [ A . ] ] bc -> [ B bc -> [ B C ] C ] ]
 135 input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
 136 ]])
 137
 138 AT_CLEANUP
 139
 140 ## ------------------------------------ ##
 141 ## S/R Conflict with Nullable Symbols.  ##
 142 ## ------------------------------------ ##
 143
 144 AT_SETUP([S/R Conflict with Nullable Symbols])
 145
 146 AT_DATA([[input.y]],
 147 [[%token A B X Y
 148 %%
 149 s: ax by | A xby;
 150 ax: A x;
 151 x: %empty | X x;
 152 by: B y;
 153 y: %empty | Y y;
 154 xby: B | X xby Y;
 155 ]])
 156
 157 AT_BISON_CHECK_CEX(
 158 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 159 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 160   Example: A . B
 161   Shift derivation
 162     s
 163     `-> 2: A xby
 164              `-> 9: . B
 165   Reduce derivation
 166     s
 167     `-> 1: ax                       by
 168            `-> 3: A x               `-> 6: B y
 169                     `-> 4: %empty .          `-> 6: %empty
 170 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 171   First example: A X . B Y $end
 172   Shift derivation
 173     $accept
 174     `-> 0: s                               $end
 175            `-> 2: A xby
 176                     `-> 10: X xby        Y
 177                               `-> 9: . B
 178   Second example: A X . B y $end
 179   Reduce derivation
 180     $accept
 181     `-> 0: s                                                   $end
 182            `-> 1: ax                                by
 183                   `-> 3: A x                        `-> 6: B y
 184                            `-> 5: X x
 185                                     `-> 4: %empty .
 186 input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
 187 ]],
 188 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 189 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 190   Example           A . B
 191   Shift derivation  s -> [ A xby -> [ . B ] ]
 192   Reduce derivation s -> [ ax -> [ A x -> [ . ] ] by -> [ B y -> [ ] ] ]
 193 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 194   First example     A X . B Y $end
 195   Shift derivation  $accept -> [ s -> [ A xby -> [ X xby -> [ . B ] Y ] ] $end ]
 196   Second example    A X . B y $end
 197   Reduce derivation $accept -> [ s -> [ ax -> [ A x -> [ X x -> [ . ] ] ] by -> [ B y ] ] $end ]
 198 input.y:5.4-9: warning: rule useless in parser due to conflicts [-Wother]
 199 ]])
 200
 201 AT_CLEANUP
 202
 203 ## ---------------------------- ##
 204 ## Non-unifying Ambiguous S/R.  ##
 205 ## ---------------------------- ##
 206
 207 AT_SETUP([Non-unifying Ambiguous S/R])
 208
 209 AT_DATA([[input.y]],
 210 [[%token A B C D E
 211 %%
 212 g: s | x;
 213 s: A x E | A x D E;
 214 x: b cd | bc;
 215 b: B;
 216 cd: C D;
 217 bc: B C;
 218 ]])
 219
 220 AT_BISON_CHECK_CEX(
 221 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 222 input.y: warning: shift/reduce conflict on token C [-Wcounterexamples]
 223   First example: B . C $end
 224   Shift derivation
 225     $accept
 226     `-> 0: g                          $end
 227            `-> 2: x
 228                   `-> 6: bc
 229                          `-> 9: B . C
 230   Second example: B . C D $end
 231   Reduce derivation
 232     $accept
 233     `-> 0: g                                   $end
 234            `-> 2: x
 235                   `-> 5: b          cd
 236                          `-> 7: B . `-> 8: C D
 237 input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
 238 ]],
 239 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 240 input.y: warning: shift/reduce conflict on token C [-Wcounterexamples]
 241   First example     B . C $end
 242   Shift derivation  $accept -> [ g -> [ x -> [ bc -> [ B . C ] ] ] $end ]
 243   Second example    B . C D $end
 244   Reduce derivation $accept -> [ g -> [ x -> [ b -> [ B . ] cd -> [ C D ] ] ] $end ]
 245 input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
 246 ]])
 247
 248 AT_CLEANUP
 249
 250 ## ------------------------------ ##
 251 ## Non-unifying Unambiguous S/R.  ##
 252 ## ------------------------------ ##
 253
 254 AT_SETUP([Non-unifying Unambiguous S/R])
 255
 256 AT_DATA([[input.y]],
 257 [[%token A B
 258 %%
 259 s: t | s t;
 260 t: x | y;
 261 x: A;
 262 y: A A B;
 263 ]])
 264
 265 AT_BISON_CHECK_CEX(
 266 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 267 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 268   First example: A . A B $end
 269   Shift derivation
 270     $accept
 271     `-> 0: s                            $end
 272            `-> 1: t
 273                   `-> 4: y
 274                          `-> 6: A . A B
 275   Second example: A . A $end
 276   Reduce derivation
 277     $accept
 278     `-> 0: s                                               $end
 279            `-> 2: s                        t
 280                   `-> 1: t                 `-> 3: x
 281                          `-> 3: x                 `-> 5: A
 282                                 `-> 5: A .
 283 ]],
 284 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 285 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 286   First example     A . A B $end
 287   Shift derivation  $accept -> [ s -> [ t -> [ y -> [ A . A B ] ] ] $end ]
 288   Second example    A . A $end
 289   Reduce derivation $accept -> [ s -> [ s -> [ t -> [ x -> [ A . ] ] ] t -> [ x -> [ A ] ] ] $end ]
 290 ]])
 291
 292 AT_CLEANUP
 293
 294 ## ----------------------- ##
 295 ## S/R after first token.  ##
 296 ## ----------------------- ##
 297
 298 AT_SETUP([S/R after first token])
 299
 300 AT_DATA([[input.y]],
 301 [[%token A B X Y
 302 %%
 303 a: r t | s;
 304 r: b;
 305 b: B;
 306 t: A xx | A x xy;
 307 s: b A xx y;
 308 x: X;
 309 xx: X X;
 310 xy: X Y;
 311 y: Y;
 312 ]])
 313
 314 AT_BISON_CHECK_CEX(
 315 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 316 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 317   Example: b . A X X Y
 318   Shift derivation
 319     a
 320     `-> 2: s
 321            `-> 7: b . xx           y
 322                       `-> 9: A X X `-> 11: Y
 323   Reduce derivation
 324     a
 325     `-> 1: r          t
 326            `-> 3: b . `-> 6: A x        xy
 327                                `-> 8: X `-> 10: X Y
 328 input.y: warning: shift/reduce conflict on token X [-Wcounterexamples]
 329   First example: A X . X
 330   Shift derivation
 331     a
 332     `-> 1: t
 333            `-> 5: A xx
 334                     `-> 9: X . X
 335   Second example: X . X xy
 336   Reduce derivation
 337     a
 338     `-> 1: x          t
 339            `-> 8: X . `-> 6: X xy
 340 input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
 341 input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
 342 ]],
 343 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 344 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 345   Example           b . A X X Y
 346   Shift derivation  a -> [ s -> [ b . xx -> [ A X X ] y -> [ Y ] ] ]
 347   Reduce derivation a -> [ r -> [ b . ] t -> [ A x -> [ X ] xy -> [ X Y ] ] ]
 348 input.y: warning: shift/reduce conflict on token X [-Wcounterexamples]
 349   First example     A X . X
 350   Shift derivation  a -> [ t -> [ A xx -> [ X . X ] ] ]
 351   Second example    X . X xy
 352   Reduce derivation a -> [ x -> [ X . ] t -> [ X xy ] ]
 353 input.y:4.4: warning: rule useless in parser due to conflicts [-Wother]
 354 input.y:8.4: warning: rule useless in parser due to conflicts [-Wother]
 355 ]])
 356
 357 AT_CLEANUP
 358
 359 ## ----------------------------- ##
 360 ## Unifying R/R counterexample.  ##
 361 ## ----------------------------- ##
 362
 363 AT_SETUP([Unifying R/R counterexample])
 364
 365 AT_DATA([[input.y]],
 366 [[%token A
 367 %%
 368 a : A b ;
 369 b : A | b;
 370 ]])
 371
 372 AT_BISON_CHECK_CEX(
 373 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
 374 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 375   Example: A b .
 376   First reduce derivation
 377     a
 378     `-> 1: A b .
 379   Second reduce derivation
 380     a
 381     `-> 1: A b
 382              `-> 3: b .
 383 input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
 384 ]],
 385 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
 386 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 387   Example                  A b .
 388   First reduce derivation  a -> [ A b . ]
 389   Second reduce derivation a -> [ A b -> [ b . ] ]
 390 input.y:4.9: warning: rule useless in parser due to conflicts [-Wother]
 391 ]])
 392
 393 AT_CLEANUP
 394
 395 ## --------------------------------- ##
 396 ## Non-unifying R/R LR(1) conflict.  ##
 397 ## --------------------------------- ##
 398
 399 AT_SETUP([Non-unifying R/R LR(1) conflict])
 400
 401 AT_DATA([[input.y]],
 402 [[%token A B C D
 403 %%
 404 s: a A | B a C | b C | B b A;
 405 a: D;
 406 b: D;
 407 ]])
 408
 409 AT_BISON_CHECK_CEX(
 410 [[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
 411 input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples]
 412   First example: D . A $end
 413   First reduce derivation
 414     $accept
 415     `-> 0: s                   $end
 416            `-> 1: a          A
 417                   `-> 5: D .
 418   Second example: B D . A $end
 419   Second reduce derivation
 420     $accept
 421     `-> 0: s                     $end
 422            `-> 4: B b          A
 423                     `-> 6: D .
 424 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 425 ]],
 426 [[input.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
 427 input.y: warning: reduce/reduce conflict on tokens A, C [-Wcounterexamples]
 428   First example            D . A $end
 429   First reduce derivation  $accept -> [ s -> [ a -> [ D . ] A ] $end ]
 430   Second example           B D . A $end
 431   Second reduce derivation $accept -> [ s -> [ B b -> [ D . ] A ] $end ]
 432 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 433 ]])
 434
 435 AT_CLEANUP
 436
 437 ## --------------------------------- ##
 438 ## Non-unifying R/R LR(2) conflict.  ##
 439 ## --------------------------------- ##
 440
 441 AT_SETUP([Non-unifying R/R LR(2) conflict])
 442
 443 AT_DATA([[input.y]],
 444 [[%token H J K X
 445 %%
 446 s: a J;
 447 a: H i;
 448 i: X | i J K;
 449 ]])
 450
 451 AT_BISON_CHECK_CEX(
 452 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 453 input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
 454 time limit exceeded: XXX
 455   First example: H i . J K $end
 456   Shift derivation
 457     $accept
 458     `-> 0: a                       $end
 459            `-> 2: H i
 460                     `-> 4: i . J K
 461   Second example: H i . J $end
 462   Reduce derivation
 463     $accept
 464     `-> 0: s                     $end
 465            `-> 1: a            J
 466                   `-> 2: H i .
 467 input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
 468 ]],
 469 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 470 input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
 471 time limit exceeded: XXX
 472   First example     H i . J K $end
 473   Shift derivation  $accept -> [ a -> [ H i -> [ i . J K ] ] $end ]
 474   Second example    H i . J $end
 475   Reduce derivation $accept -> [ s -> [ a -> [ H i . ] J ] $end ]
 476 input.y:4.4-6: warning: rule useless in parser due to conflicts [-Wother]
 477 ]])
 478
 479 AT_CLEANUP
 480
 481 ## -------------------- ##
 482 ## Cex Search Prepend.  ##
 483 ## -------------------- ##
 484
 485 # Tests prepend steps in uniying counterexample
 486 # graph search
 487
 488 AT_SETUP([Cex Search Prepend])
 489
 490 AT_DATA([[input.y]],
 491 [[%token N A B C D
 492 %%
 493 s: n | n C;
 494 n: N n D | N n C | N a B | N b;
 495 a: A;
 496 b: A B C | A B D;
 497 ]])
 498
 499 AT_BISON_CHECK_CEX(
 500 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 501 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 502   Example: N A . B C
 503   Shift derivation
 504     s
 505     `-> 1: n
 506            `-> 6: N b
 507                     `-> 8: A . B C
 508   Reduce derivation
 509     s
 510     `-> 2: n                     C
 511            `-> 5: N a          B
 512                     `-> 7: A .
 513 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 514   Example: N N A . B D C
 515   Shift derivation
 516     s
 517     `-> 1: n
 518            `-> 4: N n                       C
 519                     `-> 6: N b
 520                              `-> 9: A . B D
 521   Reduce derivation
 522     s
 523     `-> 2: n                                C
 524            `-> 3: N n                     D
 525                     `-> 5: N a          B
 526                              `-> 7: A .
 527 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 528 ]],
 529 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 530 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 531   Example           N A . B C
 532   Shift derivation  s -> [ n -> [ N b -> [ A . B C ] ] ]
 533   Reduce derivation s -> [ n -> [ N a -> [ A . ] B ] C ]
 534 input.y: warning: shift/reduce conflict on token B [-Wcounterexamples]
 535   Example           N N A . B D C
 536   Shift derivation  s -> [ n -> [ N n -> [ N b -> [ A . B D ] ] C ] ]
 537   Reduce derivation s -> [ n -> [ N n -> [ N a -> [ A . ] B ] D ] C ]
 538 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 539 ]])
 540
 541 AT_CLEANUP
 542
 543 ## ------------------- ##
 544 ## R/R cex with prec.  ##
 545 ## ------------------- ##
 546
 547 # Tests that counterexamples containing rules using
 548 # precedence/associativity directives work.
 549
 550 AT_SETUP([R/R cex with prec])
 551
 552 AT_DATA([[input.y]],
 553 [[%left b
 554 %right c
 555 %%
 556 S: B C | C B;
 557 A : B  | C  | %empty;
 558 B : A b A;
 559 C : A c A;
 560 ]])
 561
 562 AT_BISON_CHECK_CEX(
 563 [[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
 564 input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
 565   Example: B . b c
 566   First reduce derivation
 567     S
 568     `-> 1: B                                 C
 569            `-> 6: A          b A             `-> 7: A             c A
 570                   `-> 3: B .   `-> 6: %empty        `-> 7: %empty   `-> 7: %empty
 571   Second reduce derivation
 572     S
 573     `-> 1: B C
 574              `-> 7: A                                             c A
 575                     `-> 3: B                                        `-> 7: %empty
 576                            `-> 6: A               b A
 577                                   `-> 5: %empty .   `-> 6: %empty
 578 input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
 579   Example: C . c b
 580   First reduce derivation
 581     S
 582     `-> 2: C                                 B
 583            `-> 7: A          c A             `-> 6: A             b A
 584                   `-> 4: C .   `-> 7: %empty        `-> 6: %empty   `-> 6: %empty
 585   Second reduce derivation
 586     S
 587     `-> 2: C B
 588              `-> 6: A                                             b A
 589                     `-> 4: C                                        `-> 6: %empty
 590                            `-> 7: A               c A
 591                                   `-> 5: %empty .   `-> 7: %empty
 592 ]],
 593 [[input.y: warning: 4 reduce/reduce conflicts [-Wconflicts-rr]
 594 input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
 595   Example                  B . b c
 596   First reduce derivation  S -> [ B -> [ A -> [ B . ] b A -> [ ] ] C -> [ A -> [ ] c A -> [ ] ] ]
 597   Second reduce derivation S -> [ B C -> [ A -> [ B -> [ A -> [ . ] b A -> [ ] ] ] c A -> [ ] ] ]
 598 input.y: warning: reduce/reduce conflict on tokens b, c [-Wcounterexamples]
 599   Example                  C . c b
 600   First reduce derivation  S -> [ C -> [ A -> [ C . ] c A -> [ ] ] B -> [ A -> [ ] b A -> [ ] ] ]
 601   Second reduce derivation S -> [ C B -> [ A -> [ C -> [ A -> [ . ] c A -> [ ] ] ] b A -> [ ] ] ]
 602 ]])
 603
 604 AT_CLEANUP
 605
 606 ## ------------------- ##
 607 ## Null nonterminals.  ##
 608 ## ------------------- ##
 609
 610 AT_SETUP([Null nonterminals])
 611
 612 AT_DATA([[input.y]],
 613 [[%token A
 614 %%
 615 a : b d | c d ;
 616 b : ;
 617 c : ;
 618 d : a | c A | d;
 619 ]])
 620
 621 AT_BISON_CHECK_CEX(
 622 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 623 input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
 624 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 625   First example: . c A A $end
 626   First reduce derivation
 627     $accept
 628     `-> 0: a                                   $end
 629            `-> 1: b               d
 630                   `-> 3: %empty . `-> 6: c A A
 631   Second example: . c A A $end
 632   Second reduce derivation
 633     $accept
 634     `-> 0: a                                   $end
 635            `-> 2: c               d
 636                   `-> 4: %empty . `-> 6: c A A
 637 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 638 time limit exceeded: XXX
 639   First example: b . c A A $end
 640   First reduce derivation
 641     $accept
 642     `-> 0: a                                                   $end
 643            `-> 1: b d
 644                     `-> 5: a
 645                            `-> 1: b               d
 646                                   `-> 3: %empty . `-> 6: c A A
 647   Second example: b . A $end
 648   Second reduce derivation
 649     $accept
 650     `-> 0: a                                 $end
 651            `-> 1: b d
 652                     `-> 6: c               A
 653                            `-> 4: %empty .
 654 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 655 time limit exceeded: XXX
 656   First example: c . c A A $end
 657   First reduce derivation
 658     $accept
 659     `-> 0: a                                                   $end
 660            `-> 2: c d
 661                     `-> 5: a
 662                            `-> 1: b               d
 663                                   `-> 3: %empty . `-> 6: c A A
 664   Second example: c . A $end
 665   Second reduce derivation
 666     $accept
 667     `-> 0: a                                 $end
 668            `-> 2: c d
 669                     `-> 6: c               A
 670                            `-> 4: %empty .
 671 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 672 time limit exceeded: XXX
 673   First example: b c . A
 674   Shift derivation
 675     a
 676     `-> 1: b d
 677              `-> 6: c . A
 678   Second example: b c . c A A $end
 679   Reduce derivation
 680     $accept
 681     `-> 0: a                                                                   $end
 682            `-> 1: b d
 683                     `-> 5: a
 684                            `-> 2: c d
 685                                     `-> 5: a
 686                                            `-> 1: b               d
 687                                                   `-> 3: %empty . `-> 6: c A A
 688 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 689   First example: b c . c A A $end
 690   First reduce derivation
 691     $accept
 692     `-> 0: a                                                                   $end
 693            `-> 1: b d
 694                     `-> 5: a
 695                            `-> 2: c d
 696                                     `-> 5: a
 697                                            `-> 1: b               d
 698                                                   `-> 3: %empty . `-> 6: c A A
 699   Second example: b c . A $end
 700   Second reduce derivation
 701     $accept
 702     `-> 0: a                                                 $end
 703            `-> 1: b d
 704                     `-> 5: a
 705                            `-> 2: c d
 706                                     `-> 6: c               A
 707                                            `-> 4: %empty .
 708 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 709   First example: b c . A
 710   Shift derivation
 711     a
 712     `-> 1: b d
 713              `-> 6: c . A
 714   Second example: b c . A $end
 715   Reduce derivation
 716     $accept
 717     `-> 0: a                                                 $end
 718            `-> 1: b d
 719                     `-> 5: a
 720                            `-> 2: c d
 721                                     `-> 6: c               A
 722                                            `-> 4: %empty .
 723 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 724   Example: b d .
 725   First reduce derivation
 726     a
 727     `-> 1: b d .
 728   Second reduce derivation
 729     a
 730     `-> 1: b d
 731              `-> 7: d .
 732 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 733   Example: c d .
 734   First reduce derivation
 735     a
 736     `-> 2: c d .
 737   Second reduce derivation
 738     a
 739     `-> 2: c d
 740              `-> 7: d .
 741 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 742 input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
 743 ]],
 744 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 745 input.y: warning: 6 reduce/reduce conflicts [-Wconflicts-rr]
 746 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 747   First example            . c A A $end
 748   First reduce derivation  $accept -> [ a -> [ b -> [ . ] d -> [ c A A ] ] $end ]
 749   Second example           . c A A $end
 750   Second reduce derivation $accept -> [ a -> [ c -> [ . ] d -> [ c A A ] ] $end ]
 751 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 752 time limit exceeded: XXX
 753   First example            b . c A A $end
 754   First reduce derivation  $accept -> [ a -> [ b d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ]
 755   Second example           b . A $end
 756   Second reduce derivation $accept -> [ a -> [ b d -> [ c -> [ . ] A ] ] $end ]
 757 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 758 time limit exceeded: XXX
 759   First example            c . c A A $end
 760   First reduce derivation  $accept -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] $end ]
 761   Second example           c . A $end
 762   Second reduce derivation $accept -> [ a -> [ c d -> [ c -> [ . ] A ] ] $end ]
 763 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 764 time limit exceeded: XXX
 765   First example     b c . A
 766   Shift derivation  a -> [ b d -> [ c . A ] ]
 767   Second example    b c . c A A $end
 768   Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
 769 input.y: warning: reduce/reduce conflict on token A [-Wcounterexamples]
 770   First example            b c . c A A $end
 771   First reduce derivation  $accept -> [ a -> [ b d -> [ a -> [ c d -> [ a -> [ b -> [ . ] d -> [ c A A ] ] ] ] ] ] $end ]
 772   Second example           b c . A $end
 773   Second reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ]
 774 input.y: warning: shift/reduce conflict on token A [-Wcounterexamples]
 775   First example     b c . A
 776   Shift derivation  a -> [ b d -> [ c . A ] ]
 777   Second example    b c . A $end
 778   Reduce derivation $accept -> [ a -> [ b d -> [ a -> [ c d -> [ c -> [ . ] A ] ] ] ] $end ]
 779 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 780   Example                  b d .
 781   First reduce derivation  a -> [ b d . ]
 782   Second reduce derivation a -> [ b d -> [ d . ] ]
 783 input.y: warning: reduce/reduce conflict on token $end [-Wcounterexamples]
 784   Example                  c d .
 785   First reduce derivation  a -> [ c d . ]
 786   Second reduce derivation a -> [ c d -> [ d . ] ]
 787 input.y:5.4: warning: rule useless in parser due to conflicts [-Wother]
 788 input.y:6.15: warning: rule useless in parser due to conflicts [-Wother]
 789 ]])
 790
 791 AT_CLEANUP
 792
 793 ## --------------------------- ##
 794 ## Non-unifying Prefix Share.  ##
 795 ## --------------------------- ##
 796
 797 AT_SETUP([Non-unifying Prefix Share])
 798
 799 # Tests for a counterexample which should start its derivation
 800 # at a shared symbol rather than the start symbol.
 801
 802 AT_DATA([[input.y]],
 803 [[%token H J
 804 %%
 805 s: a | a J;
 806 a: H i J J
 807 i: %empty | i J;
 808 ]])
 809
 810 AT_BISON_CHECK_CEX(
 811 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 812 input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
 813   Example: H i J . J J
 814   Shift derivation
 815     s
 816     `-> 2: a                J
 817            `-> 3: H i J . J
 818   Reduce derivation
 819     s
 820     `-> 1: a
 821            `-> 3: H i            J J
 822                     `-> 5: i J .
 823 input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
 824 ]],
 825 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 826 input.y: warning: shift/reduce conflict on token J [-Wcounterexamples]
 827   Example           H i J . J J
 828   Shift derivation  s -> [ a -> [ H i J . J ] J ]
 829   Reduce derivation s -> [ a -> [ H i -> [ i J . ] J J ] ]
 830 input.y:5.13-15: warning: rule useless in parser due to conflicts [-Wother]
 831 ]])
 832
 833 AT_CLEANUP
 834
 835 ## -------------------- ##
 836 ## Deep Null Unifying.  ##
 837 ## ---------------------##
 838
 839 # Tests that nested nullable nonterminals
 840 # are derived correctly.
 841
 842 AT_SETUP([Deep Null Unifying])
 843
 844 AT_DATA([[input.y]],
 845 [[%token A D
 846 %%
 847 s: A a d | A a a d;
 848 a: b;
 849 b: c
 850 c: %empty
 851 d: D;
 852 ]])
 853
 854 AT_BISON_CHECK_CEX(
 855 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 856 input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
 857   Example: A a . D
 858   Shift derivation
 859     s
 860     `-> 1: A a d
 861                `-> 6: . D
 862   Reduce derivation
 863     s
 864     `-> 2: A a a                             d
 865                `-> 3: b                      `-> 6: D
 866                       `-> 4: c
 867                              `-> 5: %empty .
 868 ]],
 869 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 870 input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
 871   Example           A a . D
 872   Shift derivation  s -> [ A a d -> [ . D ] ]
 873   Reduce derivation s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] ]
 874 ]])
 875
 876 AT_CLEANUP
 877
 878 ## ------------------------ ##
 879 ## Deep Null Non-unifying.  ##
 880 ## -------------------------##
 881
 882 # Tests that expand_to_conflict works with nullable sybols
 883
 884 AT_SETUP([Deep Null Non-unifying])
 885
 886 AT_DATA([[input.y]],
 887 [[%token A D E
 888 %%
 889 s: A a d | A a a d E;
 890 a: b;
 891 b: c
 892 c: %empty
 893 d: D;
 894 ]])
 895
 896 AT_BISON_CHECK_CEX(
 897 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 898 input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
 899   First example: A a . D $end
 900   Shift derivation
 901     $accept
 902     `-> 0: s                     $end
 903            `-> 1: A a d
 904                       `-> 6: . D
 905   Second example: A a . D E $end
 906   Reduce derivation
 907     $accept
 908     `-> 0: s                                                   $end
 909            `-> 2: A a a                             d        E
 910                       `-> 3: b                      `-> 6: D
 911                              `-> 4: c
 912                                     `-> 5: %empty .
 913 ]],
 914 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 915 input.y: warning: shift/reduce conflict on token D [-Wcounterexamples]
 916   First example     A a . D $end
 917   Shift derivation  $accept -> [ s -> [ A a d -> [ . D ] ] $end ]
 918   Second example    A a . D E $end
 919   Reduce derivation $accept -> [ s -> [ A a a -> [ b -> [ c -> [ . ] ] ] d -> [ D ] E ] $end ]
 920 ]])
 921
 922 AT_CLEANUP