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