1 # Exercising Bison on conflicts. -*- Autotest -*- 2 3 # Copyright (C) 2002-2005, 2007, 2009-2012 Free Software Foundation, 4 # Inc. 5 6 # This program is free software: you can redistribute it and/or modify 7 # it under the terms of the GNU General Public License as published by 8 # the Free Software Foundation, either version 3 of the License, or 9 # (at your option) any later version. 10 # 11 # This program is distributed in the hope that it will be useful, 12 # but WITHOUT ANY WARRANTY; without even the implied warranty of 13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 # GNU General Public License for more details. 15 # 16 # You should have received a copy of the GNU General Public License 17 # along with this program. If not, see <http://www.gnu.org/licenses/>. 18 19 AT_BANNER([[Conflicts.]]) 20 21 22 ## ---------------- ## 23 ## S/R in initial. ## 24 ## ---------------- ## 25 26 # I once hacked Bison in such a way that it lost its reductions on the 27 # initial state (because it was confusing it with the last state). It 28 # took me a while to strip down my failures to this simple case. So 29 # make sure it finds the s/r conflict below. 30 31 AT_SETUP([S/R in initial]) 32 33 AT_DATA([[input.y]], 34 [[%expect 1 35 %% 36 exp: e 'e'; 37 e: 'e' | /* Nothing. */; 38 ]]) 39 40 AT_BISON_CHECK([-o input.c input.y], 0, [], 41 [[input.y:4.9: warning: rule useless in parser due to conflicts: e: /* empty */ 42 ]]) 43 44 AT_BISON_CHECK([-fcaret -o input.c input.y], 0, [], 45 [[input.y:4.9: warning: rule useless in parser due to conflicts 46 e: 'e' | /* Nothing. */; 47 ^ 48 ]]) 49 50 AT_CLEANUP 51 52 53 ## ------------------- ## 54 ## %nonassoc and eof. ## 55 ## ------------------- ## 56 57 AT_SETUP([%nonassoc and eof]) 58 59 AT_BISON_OPTION_PUSHDEFS 60 AT_DATA_GRAMMAR([input.y], 61 [[ 62 %{ 63 #include <stdio.h> 64 #include <stdlib.h> 65 #include <string.h> 66 #include <assert.h> 67 68 #define YYERROR_VERBOSE 1 69 ]AT_YYERROR_DEFINE[ 70 /* The current argument. */ 71 static const char *input; 72 73 static int 74 yylex (void) 75 { 76 static size_t toknum; 77 assert (toknum <= strlen (input)); 78 return input[toknum++]; 79 } 80 81 %} 82 83 %nonassoc '<' '>' 84 85 %% 86 expr: expr '<' expr 87 | expr '>' expr 88 | '0' 89 ; 90 %% 91 int 92 main (int argc, const char *argv[]) 93 { 94 input = argc <= 1 ? "" : argv[1]; 95 return yyparse (); 96 } 97 ]]) 98 AT_BISON_OPTION_POPDEFS 99 100 m4_pushdef([AT_NONASSOC_AND_EOF_CHECK], 101 [AT_BISON_CHECK([$1[ -o input.c input.y]]) 102 AT_COMPILE([input]) 103 104 m4_pushdef([AT_EXPECTING], [m4_if($2, [correct], [[, expecting $end]])]) 105 106 AT_PARSER_CHECK([./input '0<0']) 107 AT_PARSER_CHECK([./input '0<0<0'], [1], [], 108 [syntax error, unexpected '<'AT_EXPECTING 109 ]) 110 111 AT_PARSER_CHECK([./input '0>0']) 112 AT_PARSER_CHECK([./input '0>0>0'], [1], [], 113 [syntax error, unexpected '>'AT_EXPECTING 114 ]) 115 116 AT_PARSER_CHECK([./input '0<0>0'], [1], [], 117 [syntax error, unexpected '>'AT_EXPECTING 118 ]) 119 120 m4_popdef([AT_EXPECTING])]) 121 122 # Expected token list is missing. 123 AT_NONASSOC_AND_EOF_CHECK([], [[incorrect]]) 124 125 # We must disable default reductions in inconsistent states in order to 126 # have an explicit list of all expected tokens. 127 AT_NONASSOC_AND_EOF_CHECK([[-Dlr.default-reductions=consistent]], 128 [[correct]]) 129 130 # lr.default-reductions=consistent happens to work for this test case. 131 # However, for other grammars, lookahead sets can be merged for 132 # different left contexts, so it is still possible to have an incorrect 133 # expected list. Canonical LR is almost a general solution (that is, it 134 # can fail only when %nonassoc is used), so make sure it gives the same 135 # result as above. 136 AT_NONASSOC_AND_EOF_CHECK([[-Dlr.type=canonical-lr]], [[correct]]) 137 138 # parse.lac=full is a completely general solution that does not require 139 # any of the above sacrifices. Of course, it does not extend the 140 # language-recognition power of LALR to (IE)LR, but it does ensure that 141 # the reported list of expected tokens matches what the given parser 142 # would have accepted in place of the unexpected token. 143 AT_NONASSOC_AND_EOF_CHECK([[-Dparse.lac=full]], [[correct]]) 144 145 m4_popdef([AT_NONASSOC_AND_EOF_CHECK]) 146 147 AT_CLEANUP 148 149 150 151 ## -------------------------------------- ## 152 ## %error-verbose and consistent errors. ## 153 ## -------------------------------------- ## 154 155 AT_SETUP([[%error-verbose and consistent errors]]) 156 157 m4_pushdef([AT_CONSISTENT_ERRORS_CHECK], [ 158 159 AT_BISON_OPTION_PUSHDEFS([$1]) 160 161 m4_pushdef([AT_YYLEX_PROTOTYPE], 162 [AT_SKEL_CC_IF([[int yylex (yy::parser::semantic_type *lvalp)]], 163 [[int yylex (YYSTYPE *lvalp)]])]) 164 165 AT_SKEL_JAVA_IF([AT_DATA], [AT_DATA_GRAMMAR])([input.y], 166 [AT_SKEL_JAVA_IF([[ 167 168 %code imports { 169 import java.io.IOException; 170 }]], [[ 171 172 %code {]AT_SKEL_CC_IF([[ 173 #include <cassert> 174 #include <string>]], [[ 175 #include <assert.h> 176 #include <stdio.h> 177 ]AT_YYERROR_DECLARE])[ 178 ]AT_YYLEX_PROTOTYPE[; 179 #define USE(Var) 180 } 181 182 ]AT_SKEL_CC_IF([[%defines]], [[%define api.pure]])])[ 183 184 ]$1[ 185 186 %error-verbose 187 188 %% 189 190 ]$2[ 191 192 ]AT_SKEL_JAVA_IF([[%code lexer {]], [[%%]])[ 193 194 /*--------. 195 | yylex. | 196 `--------*/]AT_SKEL_JAVA_IF([[ 197 198 public String input = "]$3["; 199 public int index = 0; 200 public int yylex () 201 { 202 if (index < input.length ()) 203 return input.charAt (index++); 204 else 205 return 0; 206 } 207 public Object getLVal () 208 { 209 return new Integer(1); 210 }]], [[ 211 212 ]AT_YYLEX_PROTOTYPE[ 213 { 214 static char const *input = "]$3["; 215 *lvalp = 1; 216 return *input++; 217 }]])[ 218 ]AT_YYERROR_DEFINE[ 219 ]AT_SKEL_JAVA_IF([[ 220 }; 221 222 %%]])[ 223 224 /*-------. 225 | main. | 226 `-------*/]AT_SKEL_JAVA_IF([[ 227 228 class input 229 { 230 public static void main (String args[]) throws IOException 231 { 232 YYParser p = new YYParser (); 233 p.parse (); 234 } 235 }]], [AT_SKEL_CC_IF([[ 236 237 int 238 main (void) 239 { 240 yy::parser parser; 241 return parser.parse (); 242 }]], [[ 243 244 int 245 main (void) 246 { 247 return yyparse (); 248 }]])])[ 249 ]]) 250 251 AT_FULL_COMPILE([[input]]) 252 253 m4_pushdef([AT_EXPECTING], [m4_if($5, [ab], [[, expecting 'a' or 'b']], 254 $5, [a], [[, expecting 'a']], 255 $5, [b], [[, expecting 'b']])]) 256 257 AT_SKEL_JAVA_IF([AT_JAVA_PARSER_CHECK([[input]], [[0]]], 258 [AT_PARSER_CHECK([[./input]], [[1]]]), 259 [[]], 260 [[syntax error, unexpected ]$4[]AT_EXPECTING[ 261 ]]) 262 263 m4_popdef([AT_EXPECTING]) 264 m4_popdef([AT_YYLEX_PROTOTYPE]) 265 AT_BISON_OPTION_POPDEFS 266 267 ]) 268 269 m4_pushdef([AT_PREVIOUS_STATE_GRAMMAR], 270 [[%nonassoc 'a'; 271 272 start: consistent-error-on-a-a 'a' ; 273 274 consistent-error-on-a-a: 275 'a' default-reduction 276 | 'a' default-reduction 'a' 277 | 'a' shift 278 ; 279 280 default-reduction: /*empty*/ ; 281 shift: 'b' ; 282 283 // Provide another context in which all rules are useful so that this 284 // test case looks a little more realistic. 285 start: 'b' consistent-error-on-a-a 'c' ; 286 ]]) 287 288 m4_pushdef([AT_PREVIOUS_STATE_INPUT], [[a]]) 289 290 # Unfortunately, no expected tokens are reported even though 'b' can be 291 # accepted. Nevertheless, the main point of this test is to make sure 292 # that at least the unexpected token is reported. In a previous version 293 # of Bison, it wasn't reported because the error is detected in a 294 # consistent state with an error action, and that case always triggered 295 # the simple "syntax error" message. 296 # 297 # The point isn't to test IELR here, but state merging happens to 298 # complicate this example. 299 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr]], 300 [AT_PREVIOUS_STATE_GRAMMAR], 301 [AT_PREVIOUS_STATE_INPUT], 302 [[$end]], [[none]]) 303 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 304 %glr-parser]], 305 [AT_PREVIOUS_STATE_GRAMMAR], 306 [AT_PREVIOUS_STATE_INPUT], 307 [[$end]], [[none]]) 308 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 309 %language "c++"]], 310 [AT_PREVIOUS_STATE_GRAMMAR], 311 [AT_PREVIOUS_STATE_INPUT], 312 [[$end]], [[none]]) 313 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 314 %language "java"]], 315 [AT_PREVIOUS_STATE_GRAMMAR], 316 [AT_PREVIOUS_STATE_INPUT], 317 [[end of input]], [[none]]) 318 319 # Even canonical LR doesn't foresee the error for 'a'! 320 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 321 %define lr.default-reductions consistent]], 322 [AT_PREVIOUS_STATE_GRAMMAR], 323 [AT_PREVIOUS_STATE_INPUT], 324 [[$end]], [[ab]]) 325 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 326 %define lr.default-reductions accepting]], 327 [AT_PREVIOUS_STATE_GRAMMAR], 328 [AT_PREVIOUS_STATE_INPUT], 329 [[$end]], [[ab]]) 330 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]], 331 [AT_PREVIOUS_STATE_GRAMMAR], 332 [AT_PREVIOUS_STATE_INPUT], 333 [[$end]], [[ab]]) 334 335 # Only LAC gets it right. 336 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr 337 %define parse.lac full]], 338 [AT_PREVIOUS_STATE_GRAMMAR], 339 [AT_PREVIOUS_STATE_INPUT], 340 [[$end]], [[b]]) 341 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 342 %define parse.lac full]], 343 [AT_PREVIOUS_STATE_GRAMMAR], 344 [AT_PREVIOUS_STATE_INPUT], 345 [[$end]], [[b]]) 346 347 m4_popdef([AT_PREVIOUS_STATE_GRAMMAR]) 348 m4_popdef([AT_PREVIOUS_STATE_INPUT]) 349 350 m4_pushdef([AT_USER_ACTION_GRAMMAR], 351 [[%nonassoc 'a'; 352 353 // If $$ = 0 here, then we know that the 'a' destructor is being invoked 354 // incorrectly for the 'b' set in the semantic action below. All 'a' 355 // tokens are returned by yylex, which sets $$ = 1. 356 %destructor { 357 if (!$$) 358 fprintf (stderr, "Wrong destructor.\n"); 359 } 'a'; 360 361 // Rather than depend on an inconsistent state to induce reading a 362 // lookahead as in the previous grammar, just assign the lookahead in a 363 // semantic action. That lookahead isn't needed before either error 364 // action is encountered. In a previous version of Bison, this was a 365 // problem as it meant yychar was not translated into yytoken before 366 // either error action. The second error action thus invoked a 367 // destructor that it selected according to the incorrect yytoken. The 368 // first error action would have reported an incorrect unexpected token 369 // except that, due to the bug described in the previous grammar, the 370 // unexpected token was not reported at all. 371 start: error-reduce consistent-error 'a' { USE ($][3); } ; 372 373 error-reduce: 374 'a' 'a' consistent-reduction consistent-error 'a' 375 { USE (($][1, $][2, $][5)); } 376 | 'a' error 377 { USE ($][1); } 378 ; 379 380 consistent-reduction: /*empty*/ { 381 assert (yychar == ]AT_SKEL_CC_IF([[yyempty_]], [[YYEMPTY]])[); 382 yylval = 0; 383 yychar = 'b'; 384 } ; 385 386 consistent-error: 387 'a' { USE ($][1); } 388 | /*empty*/ %prec 'a' 389 ; 390 391 // Provide another context in which all rules are useful so that this 392 // test case looks a little more realistic. 393 start: 'b' consistent-error 'b' ; 394 ]]) 395 m4_pushdef([AT_USER_ACTION_INPUT], [[aa]]) 396 397 AT_CONSISTENT_ERRORS_CHECK([[]], 398 [AT_USER_ACTION_GRAMMAR], 399 [AT_USER_ACTION_INPUT], 400 [['b']], [[none]]) 401 AT_CONSISTENT_ERRORS_CHECK([[%glr-parser]], 402 [AT_USER_ACTION_GRAMMAR], 403 [AT_USER_ACTION_INPUT], 404 [['b']], [[none]]) 405 AT_CONSISTENT_ERRORS_CHECK([[%language "c++"]], 406 [AT_USER_ACTION_GRAMMAR], 407 [AT_USER_ACTION_INPUT], 408 [['b']], [[none]]) 409 # No Java test because yychar cannot be manipulated by users. 410 411 AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reductions consistent]], 412 [AT_USER_ACTION_GRAMMAR], 413 [AT_USER_ACTION_INPUT], 414 [['b']], [[none]]) 415 416 # Canonical LR doesn't foresee the error for 'a'! 417 AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reductions accepting]], 418 [AT_USER_ACTION_GRAMMAR], 419 [AT_USER_ACTION_INPUT], 420 [[$end]], [[a]]) 421 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]], 422 [AT_USER_ACTION_GRAMMAR], 423 [AT_USER_ACTION_INPUT], 424 [[$end]], [[a]]) 425 426 AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full]], 427 [AT_USER_ACTION_GRAMMAR], 428 [AT_USER_ACTION_INPUT], 429 [['b']], [[none]]) 430 AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full 431 %define lr.default-reductions accepting]], 432 [AT_USER_ACTION_GRAMMAR], 433 [AT_USER_ACTION_INPUT], 434 [[$end]], [[none]]) 435 436 m4_popdef([AT_USER_ACTION_GRAMMAR]) 437 m4_popdef([AT_USER_ACTION_INPUT]) 438 439 m4_popdef([AT_CONSISTENT_ERRORS_CHECK]) 440 441 AT_CLEANUP 442 443 444 445 ## ------------------------------------------------------- ## 446 ## LAC: %nonassoc requires splitting canonical LR states. ## 447 ## ------------------------------------------------------- ## 448 449 # This test case demonstrates that, when %nonassoc is used, canonical 450 # LR(1) parser table construction followed by conflict resolution 451 # without further state splitting is not always sufficient to produce a 452 # parser that can detect all syntax errors as soon as possible on one 453 # token of lookahead. However, LAC solves the problem completely even 454 # with minimal LR parser tables. 455 456 AT_SETUP([[LAC: %nonassoc requires splitting canonical LR states]]) 457 AT_BISON_OPTION_PUSHDEFS 458 AT_DATA_GRAMMAR([[input.y]], 459 [[%code { 460 #include <stdio.h> 461 ]AT_YYERROR_DECLARE[ 462 ]AT_YYLEX_DECLARE[ 463 } 464 465 %error-verbose 466 %nonassoc 'a' 467 468 %% 469 470 start: 471 'a' problem 'a' // First context. 472 | 'b' problem 'b' // Second context. 473 | 'c' reduce-nonassoc // Just makes reduce-nonassoc useful. 474 ; 475 476 problem: 477 look reduce-nonassoc 478 | look 'a' 479 | look 'b' 480 ; 481 482 // For the state reached after shifting the 'a' in these productions, 483 // lookahead sets are the same in both the first and second contexts. 484 // Thus, canonical LR reuses the same state for both contexts. However, 485 // the lookahead 'a' for the reduction "look: 'a'" later becomes an 486 // error action only in the first context. In order to immediately 487 // detect the syntax error on 'a' here for only the first context, this 488 // canonical LR state would have to be split into two states, and the 489 // 'a' lookahead would have to be removed from only one of the states. 490 look: 491 'a' // Reduction lookahead set is always ['a', 'b']. 492 | 'a' 'b' 493 | 'a' 'c' // 'c' is forgotten as an expected token. 494 ; 495 496 reduce-nonassoc: %prec 'a'; 497 498 %% 499 ]AT_YYERROR_DEFINE[ 500 ]AT_YYLEX_DEFINE(["aaa"])[ 501 502 int 503 main (void) 504 { 505 return yyparse (); 506 } 507 ]]) 508 AT_BISON_OPTION_POPDEFS 509 510 # Show canonical LR's failure. 511 AT_BISON_CHECK([[-Dlr.type=canonical-lr -o input.c input.y]], 512 [[0]], [[]], 513 [[input.y: conflicts: 2 shift/reduce 514 ]]) 515 AT_COMPILE([[input]]) 516 AT_PARSER_CHECK([[./input]], [[1]], [[]], 517 [[syntax error, unexpected 'a', expecting 'b' 518 ]]) 519 520 # It's corrected by LAC. 521 AT_BISON_CHECK([[-Dlr.type=canonical-lr -Dparse.lac=full \ 522 -o input.c input.y]], [[0]], [[]], 523 [[input.y: conflicts: 2 shift/reduce 524 ]]) 525 AT_COMPILE([[input]]) 526 AT_PARSER_CHECK([[./input]], [[1]], [[]], 527 [[syntax error, unexpected 'a', expecting 'b' or 'c' 528 ]]) 529 530 # IELR is sufficient when LAC is used. 531 AT_BISON_CHECK([[-Dlr.type=ielr -Dparse.lac=full -o input.c input.y]], 532 [[0]], [[]], 533 [[input.y: conflicts: 2 shift/reduce 534 ]]) 535 AT_COMPILE([[input]]) 536 AT_PARSER_CHECK([[./input]], [[1]], [[]], 537 [[syntax error, unexpected 'a', expecting 'b' or 'c' 538 ]]) 539 540 AT_CLEANUP 541 542 ## ------------------------- ## 543 ## Unresolved SR Conflicts. ## 544 ## ------------------------- ## 545 546 AT_SETUP([Unresolved SR Conflicts]) 547 548 AT_KEYWORDS([report]) 549 550 AT_DATA([input.y], 551 [[%token NUM OP 552 %% 553 exp: exp OP exp | NUM; 554 ]]) 555 556 AT_BISON_CHECK([-o input.c --report=all input.y], 0, [], 557 [input.y: conflicts: 1 shift/reduce 558 ]) 559 560 # Check the contents of the report. 561 AT_CHECK([cat input.output], [], 562 [[State 5 conflicts: 1 shift/reduce 563 564 565 Grammar 566 567 0 $accept: exp $end 568 569 1 exp: exp OP exp 570 2 | NUM 571 572 573 Terminals, with rules where they appear 574 575 $end (0) 0 576 error (256) 577 NUM (258) 2 578 OP (259) 1 579 580 581 Nonterminals, with rules where they appear 582 583 $accept (5) 584 on left: 0 585 exp (6) 586 on left: 1 2, on right: 0 1 587 588 589 State 0 590 591 0 $accept: . exp $end 592 1 exp: . exp OP exp 593 2 | . NUM 594 595 NUM shift, and go to state 1 596 597 exp go to state 2 598 599 600 State 1 601 602 2 exp: NUM . 603 604 $default reduce using rule 2 (exp) 605 606 607 State 2 608 609 0 $accept: exp . $end 610 1 exp: exp . OP exp 611 612 $end shift, and go to state 3 613 OP shift, and go to state 4 614 615 616 State 3 617 618 0 $accept: exp $end . 619 620 $default accept 621 622 623 State 4 624 625 1 exp: . exp OP exp 626 1 | exp OP . exp 627 2 | . NUM 628 629 NUM shift, and go to state 1 630 631 exp go to state 5 632 633 634 State 5 635 636 1 exp: exp . OP exp 637 1 | exp OP exp . [$end, OP] 638 639 OP shift, and go to state 4 640 641 OP [reduce using rule 1 (exp)] 642 $default reduce using rule 1 (exp) 643 ]]) 644 645 AT_CLEANUP 646 647 648 649 ## ----------------------- ## 650 ## Resolved SR Conflicts. ## 651 ## ----------------------- ## 652 653 AT_SETUP([Resolved SR Conflicts]) 654 655 AT_KEYWORDS([report]) 656 657 AT_DATA([input.y], 658 [[%token NUM OP 659 %left OP 660 %% 661 exp: exp OP exp | NUM; 662 ]]) 663 664 AT_BISON_CHECK([-o input.c --report=all input.y]) 665 666 # Check the contents of the report. 667 AT_CHECK([cat input.output], [], 668 [[Grammar 669 670 0 $accept: exp $end 671 672 1 exp: exp OP exp 673 2 | NUM 674 675 676 Terminals, with rules where they appear 677 678 $end (0) 0 679 error (256) 680 NUM (258) 2 681 OP (259) 1 682 683 684 Nonterminals, with rules where they appear 685 686 $accept (5) 687 on left: 0 688 exp (6) 689 on left: 1 2, on right: 0 1 690 691 692 State 0 693 694 0 $accept: . exp $end 695 1 exp: . exp OP exp 696 2 | . NUM 697 698 NUM shift, and go to state 1 699 700 exp go to state 2 701 702 703 State 1 704 705 2 exp: NUM . 706 707 $default reduce using rule 2 (exp) 708 709 710 State 2 711 712 0 $accept: exp . $end 713 1 exp: exp . OP exp 714 715 $end shift, and go to state 3 716 OP shift, and go to state 4 717 718 719 State 3 720 721 0 $accept: exp $end . 722 723 $default accept 724 725 726 State 4 727 728 1 exp: . exp OP exp 729 1 | exp OP . exp 730 2 | . NUM 731 732 NUM shift, and go to state 1 733 734 exp go to state 5 735 736 737 State 5 738 739 1 exp: exp . OP exp 740 1 | exp OP exp . [$end, OP] 741 742 $default reduce using rule 1 (exp) 743 744 Conflict between rule 1 and token OP resolved as reduce (%left OP). 745 ]]) 746 747 AT_CLEANUP 748 749 750 ## -------------------------------- ## 751 ## Defaulted Conflicted Reduction. ## 752 ## -------------------------------- ## 753 754 # When there are RR conflicts, some rules are disabled. Usually it is 755 # simply displayed as: 756 # 757 # $end reduce using rule 3 (num) 758 # $end [reduce using rule 4 (id)] 759 # 760 # But when `reduce 3' is the default action, we'd produce: 761 # 762 # $end [reduce using rule 4 (id)] 763 # $default reduce using rule 3 (num) 764 # 765 # In this precise case (a reduction is masked by the default 766 # reduction), we make the `reduce 3' explicit: 767 # 768 # $end reduce using rule 3 (num) 769 # $end [reduce using rule 4 (id)] 770 # $default reduce using rule 3 (num) 771 # 772 # Maybe that's not the best display, but then, please propose something 773 # else. 774 775 AT_SETUP([Defaulted Conflicted Reduction]) 776 AT_KEYWORDS([report]) 777 778 AT_DATA([input.y], 779 [[%% 780 exp: num | id; 781 num: '0'; 782 id : '0'; 783 %% 784 ]]) 785 786 AT_BISON_CHECK([-o input.c --report=all input.y], 0, [], 787 [[input.y: conflicts: 1 reduce/reduce 788 input.y:4.6-8: warning: rule useless in parser due to conflicts: id: '0' 789 ]]) 790 791 # Check the contents of the report. 792 AT_CHECK([cat input.output], [], 793 [[Rules useless in parser due to conflicts 794 795 4 id: '0' 796 797 798 State 1 conflicts: 1 reduce/reduce 799 800 801 Grammar 802 803 0 $accept: exp $end 804 805 1 exp: num 806 2 | id 807 808 3 num: '0' 809 810 4 id: '0' 811 812 813 Terminals, with rules where they appear 814 815 $end (0) 0 816 '0' (48) 3 4 817 error (256) 818 819 820 Nonterminals, with rules where they appear 821 822 $accept (4) 823 on left: 0 824 exp (5) 825 on left: 1 2, on right: 0 826 num (6) 827 on left: 3, on right: 1 828 id (7) 829 on left: 4, on right: 2 830 831 832 State 0 833 834 0 $accept: . exp $end 835 1 exp: . num 836 2 | . id 837 3 num: . '0' 838 4 id: . '0' 839 840 '0' shift, and go to state 1 841 842 exp go to state 2 843 num go to state 3 844 id go to state 4 845 846 847 State 1 848 849 3 num: '0' . [$end] 850 4 id: '0' . [$end] 851 852 $end reduce using rule 3 (num) 853 $end [reduce using rule 4 (id)] 854 $default reduce using rule 3 (num) 855 856 857 State 2 858 859 0 $accept: exp . $end 860 861 $end shift, and go to state 5 862 863 864 State 3 865 866 1 exp: num . 867 868 $default reduce using rule 1 (exp) 869 870 871 State 4 872 873 2 exp: id . 874 875 $default reduce using rule 2 (exp) 876 877 878 State 5 879 880 0 $accept: exp $end . 881 882 $default accept 883 ]]) 884 885 AT_CLEANUP 886 887 888 889 890 ## -------------------- ## 891 ## %expect not enough. ## 892 ## -------------------- ## 893 894 AT_SETUP([%expect not enough]) 895 896 AT_DATA([input.y], 897 [[%token NUM OP 898 %expect 0 899 %% 900 exp: exp OP exp | NUM; 901 ]]) 902 903 AT_BISON_CHECK([-o input.c input.y], 1, [], 904 [input.y: conflicts: 1 shift/reduce 905 input.y: error: expected 0 shift/reduce conflicts 906 ]) 907 AT_CLEANUP 908 909 910 ## --------------- ## 911 ## %expect right. ## 912 ## --------------- ## 913 914 AT_SETUP([%expect right]) 915 916 AT_DATA([input.y], 917 [[%token NUM OP 918 %expect 1 919 %% 920 exp: exp OP exp | NUM; 921 ]]) 922 923 AT_BISON_CHECK([-o input.c input.y]) 924 AT_CLEANUP 925 926 927 ## ------------------ ## 928 ## %expect too much. ## 929 ## ------------------ ## 930 931 AT_SETUP([%expect too much]) 932 933 AT_DATA([input.y], 934 [[%token NUM OP 935 %expect 2 936 %% 937 exp: exp OP exp | NUM; 938 ]]) 939 940 AT_BISON_CHECK([-o input.c input.y], 1, [], 941 [input.y: conflicts: 1 shift/reduce 942 input.y: error: expected 2 shift/reduce conflicts 943 ]) 944 AT_CLEANUP 945 946 947 ## ------------------------------- ## 948 ## %expect with reduce conflicts. ## 949 ## ------------------------------- ## 950 951 AT_SETUP([%expect with reduce conflicts]) 952 953 AT_DATA([input.y], 954 [[%expect 0 955 %% 956 program: a 'a' | a a; 957 a: 'a'; 958 ]]) 959 960 AT_BISON_CHECK([-o input.c input.y], 1, [], 961 [input.y: conflicts: 1 reduce/reduce 962 input.y: error: expected 0 reduce/reduce conflicts 963 ]) 964 AT_CLEANUP 965 966 967 ## ------------------------- ## 968 ## %prec with user strings. ## 969 ## ------------------------- ## 970 971 AT_SETUP([%prec with user string]) 972 973 AT_DATA([[input.y]], 974 [[%% 975 exp: 976 "foo" %prec "foo" 977 ; 978 ]]) 979 980 AT_BISON_CHECK([-o input.c input.y]) 981 AT_CLEANUP 982 983 984 ## -------------------------------- ## 985 ## %no-default-prec without %prec. ## 986 ## -------------------------------- ## 987 988 AT_SETUP([%no-default-prec without %prec]) 989 990 AT_DATA([[input.y]], 991 [[%left '+' 992 %left '*' 993 994 %% 995 996 %no-default-prec; 997 998 e: e '+' e 999 | e '*' e 1000 | '0' 1001 ; 1002 ]]) 1003 1004 AT_BISON_CHECK([-o input.c input.y], 0, [], 1005 [[input.y: conflicts: 4 shift/reduce 1006 ]]) 1007 AT_CLEANUP 1008 1009 1010 ## ----------------------------- ## 1011 ## %no-default-prec with %prec. ## 1012 ## ----------------------------- ## 1013 1014 AT_SETUP([%no-default-prec with %prec]) 1015 1016 AT_DATA([[input.y]], 1017 [[%left '+' 1018 %left '*' 1019 1020 %% 1021 1022 %no-default-prec; 1023 1024 e: e '+' e %prec '+' 1025 | e '*' e %prec '*' 1026 | '0' 1027 ; 1028 ]]) 1029 1030 AT_BISON_CHECK([-o input.c input.y]) 1031 AT_CLEANUP 1032 1033 1034 ## --------------- ## 1035 ## %default-prec. ## 1036 ## --------------- ## 1037 1038 AT_SETUP([%default-prec]) 1039 1040 AT_DATA([[input.y]], 1041 [[%left '+' 1042 %left '*' 1043 1044 %% 1045 1046 %default-prec; 1047 1048 e: e '+' e 1049 | e '*' e 1050 | '0' 1051 ; 1052 ]]) 1053 1054 AT_BISON_CHECK([-o input.c input.y]) 1055 AT_CLEANUP 1056 1057 1058 ## ---------------------------------------------- ## 1059 ## Unreachable States After Conflict Resolution. ## 1060 ## ---------------------------------------------- ## 1061 1062 AT_SETUP([[Unreachable States After Conflict Resolution]]) 1063 1064 # If conflict resolution makes states unreachable, remove those states, report 1065 # rules that are then unused, and don't report conflicts in those states. Test 1066 # what happens when a nonterminal becomes useless as a result of state removal 1067 # since that causes lalr.o's goto map to be rewritten. 1068 1069 AT_DATA([[input.y]], 1070 [[%output "input.c" 1071 %left 'a' 1072 1073 %% 1074 1075 start: resolved_conflict 'a' reported_conflicts 'a' ; 1076 1077 /* S/R conflict resolved as reduce, so the state with item 1078 * (resolved_conflict: 'a' . unreachable1) and all it transition successors are 1079 * unreachable, and the associated production is useless. */ 1080 resolved_conflict: 1081 'a' unreachable1 1082 | %prec 'a' 1083 ; 1084 1085 /* S/R conflict that need not be reported since it is unreachable because of 1086 * the previous conflict resolution. Nonterminal unreachable1 and all its 1087 * productions are useless. */ 1088 unreachable1: 1089 'a' unreachable2 1090 | 1091 ; 1092 1093 /* Likewise for a R/R conflict and nonterminal unreachable2. */ 1094 unreachable2: | ; 1095 1096 /* Make sure remaining S/R and R/R conflicts are still reported correctly even 1097 * when their states are renumbered due to state removal. */ 1098 reported_conflicts: 1099 'a' 1100 | 'a' 1101 | 1102 ; 1103 1104 ]]) 1105 1106 AT_BISON_CHECK([[--report=all input.y]], 0, [], 1107 [[input.y: conflicts: 1 shift/reduce, 1 reduce/reduce 1108 input.y:12.5-20: warning: rule useless in parser due to conflicts: resolved_conflict: 'a' unreachable1 1109 input.y:20.5-20: warning: rule useless in parser due to conflicts: unreachable1: 'a' unreachable2 1110 input.y:21.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */ 1111 input.y:25.13: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1112 input.y:25.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1113 input.y:31.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a' 1114 input.y:32.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */ 1115 ]]) 1116 1117 AT_CHECK([[cat input.output]], 0, 1118 [[Rules useless in parser due to conflicts 1119 1120 2 resolved_conflict: 'a' unreachable1 1121 1122 4 unreachable1: 'a' unreachable2 1123 5 | /* empty */ 1124 1125 6 unreachable2: /* empty */ 1126 7 | /* empty */ 1127 1128 9 reported_conflicts: 'a' 1129 10 | /* empty */ 1130 1131 1132 State 4 conflicts: 1 shift/reduce 1133 State 5 conflicts: 1 reduce/reduce 1134 1135 1136 Grammar 1137 1138 0 $accept: start $end 1139 1140 1 start: resolved_conflict 'a' reported_conflicts 'a' 1141 1142 2 resolved_conflict: 'a' unreachable1 1143 3 | /* empty */ 1144 1145 4 unreachable1: 'a' unreachable2 1146 5 | /* empty */ 1147 1148 6 unreachable2: /* empty */ 1149 7 | /* empty */ 1150 1151 8 reported_conflicts: 'a' 1152 9 | 'a' 1153 10 | /* empty */ 1154 1155 1156 Terminals, with rules where they appear 1157 1158 $end (0) 0 1159 'a' (97) 1 2 4 8 9 1160 error (256) 1161 1162 1163 Nonterminals, with rules where they appear 1164 1165 $accept (4) 1166 on left: 0 1167 start (5) 1168 on left: 1, on right: 0 1169 resolved_conflict (6) 1170 on left: 2 3, on right: 1 1171 unreachable1 (7) 1172 on left: 4 5, on right: 2 1173 unreachable2 (8) 1174 on left: 6 7, on right: 4 1175 reported_conflicts (9) 1176 on left: 8 9 10, on right: 1 1177 1178 1179 State 0 1180 1181 0 $accept: . start $end 1182 1 start: . resolved_conflict 'a' reported_conflicts 'a' 1183 2 resolved_conflict: . 'a' unreachable1 1184 3 | . ['a'] 1185 1186 $default reduce using rule 3 (resolved_conflict) 1187 1188 start go to state 1 1189 resolved_conflict go to state 2 1190 1191 Conflict between rule 3 and token 'a' resolved as reduce (%left 'a'). 1192 1193 1194 State 1 1195 1196 0 $accept: start . $end 1197 1198 $end shift, and go to state 3 1199 1200 1201 State 2 1202 1203 1 start: resolved_conflict . 'a' reported_conflicts 'a' 1204 1205 'a' shift, and go to state 4 1206 1207 1208 State 3 1209 1210 0 $accept: start $end . 1211 1212 $default accept 1213 1214 1215 State 4 1216 1217 1 start: resolved_conflict 'a' . reported_conflicts 'a' 1218 8 reported_conflicts: . 'a' 1219 9 | . 'a' 1220 10 | . ['a'] 1221 1222 'a' shift, and go to state 5 1223 1224 'a' [reduce using rule 10 (reported_conflicts)] 1225 1226 reported_conflicts go to state 6 1227 1228 1229 State 5 1230 1231 8 reported_conflicts: 'a' . ['a'] 1232 9 | 'a' . ['a'] 1233 1234 'a' reduce using rule 8 (reported_conflicts) 1235 'a' [reduce using rule 9 (reported_conflicts)] 1236 $default reduce using rule 8 (reported_conflicts) 1237 1238 1239 State 6 1240 1241 1 start: resolved_conflict 'a' reported_conflicts . 'a' 1242 1243 'a' shift, and go to state 7 1244 1245 1246 State 7 1247 1248 1 start: resolved_conflict 'a' reported_conflicts 'a' . 1249 1250 $default reduce using rule 1 (start) 1251 ]]) 1252 1253 AT_DATA([[input-keep.y]], 1254 [[%define lr.keep-unreachable-states 1255 ]]) 1256 AT_CHECK([[cat input.y >> input-keep.y]]) 1257 1258 AT_BISON_CHECK([[input-keep.y]], 0, [], 1259 [[input-keep.y: conflicts: 2 shift/reduce, 2 reduce/reduce 1260 input-keep.y:22.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */ 1261 input-keep.y:26.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1262 input-keep.y:32.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a' 1263 input-keep.y:33.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */ 1264 ]]) 1265 1266 AT_CLEANUP 1267 1268 1269 ## ------------------------------------------------------------ ## 1270 ## Solved conflicts report for multiple reductions in a state. ## 1271 ## ------------------------------------------------------------ ## 1272 1273 AT_SETUP([[Solved conflicts report for multiple reductions in a state]]) 1274 1275 # Used to lose earlier solved conflict messages even within a single S/R/R. 1276 1277 AT_DATA([[input.y]], 1278 [[%left 'a' 1279 %right 'b' 1280 %right 'c' 1281 %right 'd' 1282 %% 1283 start: 1284 'a' 1285 | empty_a 'a' 1286 | 'b' 1287 | empty_b 'b' 1288 | 'c' 1289 | empty_c1 'c' 1290 | empty_c2 'c' 1291 | empty_c3 'c' 1292 ; 1293 empty_a: %prec 'a' ; 1294 empty_b: %prec 'b' ; 1295 empty_c1: %prec 'c' ; 1296 empty_c2: %prec 'c' ; 1297 empty_c3: %prec 'd' ; 1298 ]]) 1299 AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore]) 1300 AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0, 1301 [[State 0 1302 1303 0 $accept: . start $end 1304 1 start: . 'a' 1305 2 | . empty_a 'a' 1306 3 | . 'b' 1307 4 | . empty_b 'b' 1308 5 | . 'c' 1309 6 | . empty_c1 'c' 1310 7 | . empty_c2 'c' 1311 8 | . empty_c3 'c' 1312 9 empty_a: . ['a'] 1313 10 empty_b: . [] 1314 11 empty_c1: . [] 1315 12 empty_c2: . [] 1316 13 empty_c3: . ['c'] 1317 1318 'b' shift, and go to state 1 1319 1320 'c' reduce using rule 13 (empty_c3) 1321 $default reduce using rule 9 (empty_a) 1322 1323 start go to state 2 1324 empty_a go to state 3 1325 empty_b go to state 4 1326 empty_c1 go to state 5 1327 empty_c2 go to state 6 1328 empty_c3 go to state 7 1329 1330 Conflict between rule 9 and token 'a' resolved as reduce (%left 'a'). 1331 Conflict between rule 10 and token 'b' resolved as shift (%right 'b'). 1332 Conflict between rule 11 and token 'c' resolved as shift (%right 'c'). 1333 Conflict between rule 12 and token 'c' resolved as shift (%right 'c'). 1334 Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd'). 1335 1336 1337 State 1 1338 ]]) 1339 1340 AT_CLEANUP 1341 1342 1343 ## ------------------------------------------------------------ ## 1344 ## %nonassoc error actions for multiple reductions in a state. ## 1345 ## ------------------------------------------------------------ ## 1346 1347 # Used to abort when trying to resolve conflicts as %nonassoc error actions for 1348 # multiple reductions in a state. 1349 1350 # For a %nonassoc error action token, used to print the first remaining 1351 # reduction on that token without brackets. 1352 1353 AT_SETUP([[%nonassoc error actions for multiple reductions in a state]]) 1354 1355 AT_DATA([[input.y]], 1356 [[%nonassoc 'a' 'b' 'c' 1357 %% 1358 start: 1359 'a' 1360 | empty_a 'a' 1361 | 'b' 1362 | empty_b 'b' 1363 | 'c' 1364 | empty_c1 'c' 1365 | empty_c2 'c' 1366 | empty_c3 'c' 1367 ; 1368 empty_a: %prec 'a' ; 1369 empty_b: %prec 'b' ; 1370 empty_c1: %prec 'c' ; 1371 empty_c2: %prec 'c' ; 1372 empty_c3: %prec 'c' ; 1373 ]]) 1374 1375 AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore]) 1376 AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0, 1377 [[State 0 1378 1379 0 $accept: . start $end 1380 1 start: . 'a' 1381 2 | . empty_a 'a' 1382 3 | . 'b' 1383 4 | . empty_b 'b' 1384 5 | . 'c' 1385 6 | . empty_c1 'c' 1386 7 | . empty_c2 'c' 1387 8 | . empty_c3 'c' 1388 9 empty_a: . [] 1389 10 empty_b: . [] 1390 11 empty_c1: . [] 1391 12 empty_c2: . ['c'] 1392 13 empty_c3: . ['c'] 1393 1394 'a' error (nonassociative) 1395 'b' error (nonassociative) 1396 'c' error (nonassociative) 1397 1398 'c' [reduce using rule 12 (empty_c2)] 1399 'c' [reduce using rule 13 (empty_c3)] 1400 1401 start go to state 1 1402 empty_a go to state 2 1403 empty_b go to state 3 1404 empty_c1 go to state 4 1405 empty_c2 go to state 5 1406 empty_c3 go to state 6 1407 1408 Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a'). 1409 Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 'b'). 1410 Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 'c'). 1411 1412 1413 State 1 1414 ]]) 1415 AT_CLEANUP 1416 1417 1418 ## --------------------------------- ## 1419 ## -W versus %expect and %expect-rr ## 1420 ## --------------------------------- ## 1421 1422 AT_SETUP([[-W versus %expect and %expect-rr]]) 1423 1424 AT_DATA([[sr-rr.y]], 1425 [[%glr-parser 1426 %% 1427 start: 'a' | A 'a' | B 'a' ; 1428 A: ; 1429 B: ; 1430 ]]) 1431 AT_DATA([[sr.y]], 1432 [[%glr-parser 1433 %% 1434 start: 'a' | A 'a' ; 1435 A: ; 1436 ]]) 1437 AT_DATA([[rr.y]], 1438 [[%glr-parser 1439 %% 1440 start: A | B ; 1441 A: ; 1442 B: ; 1443 ]]) 1444 1445 AT_BISON_CHECK([[sr-rr.y]], [[0]], [[]], 1446 [[sr-rr.y: conflicts: 1 shift/reduce, 1 reduce/reduce 1447 ]]) 1448 AT_BISON_CHECK([[-Wno-conflicts-sr sr-rr.y]], [[0]], [[]], 1449 [[sr-rr.y: conflicts: 1 reduce/reduce 1450 ]]) 1451 AT_BISON_CHECK([[-Wno-conflicts-rr sr-rr.y]], [[0]], [[]], 1452 [[sr-rr.y: conflicts: 1 shift/reduce 1453 ]]) 1454 1455 [for gram in sr-rr sr rr; do 1456 for sr_exp_i in '' 0 1 2; do 1457 for rr_exp_i in '' 0 1 2; do 1458 test -z "$sr_exp_i" && test -z "$rr_exp_i" && continue 1459 1460 # Build grammar file. 1461 sr_exp=0 1462 rr_exp=0 1463 file=$gram 1464 directives= 1465 if test -n "$sr_exp_i"; then 1466 sr_exp=$sr_exp_i 1467 file=$file-expect-$sr_exp 1468 directives="%expect $sr_exp" 1469 fi 1470 if test -n "$rr_exp_i"; then 1471 rr_exp=$rr_exp_i 1472 file=$file-expect-rr-$rr_exp 1473 directives="$directives %expect-rr $rr_exp" 1474 fi 1475 file=$file.y 1476 echo "$directives" > $file 1477 cat $gram.y >> $file 1478 1479 # Count actual conflicts. 1480 conflicts= 1481 sr_count=0 1482 rr_count=0 1483 if test $gram = sr || test $gram = sr-rr; then 1484 conflicts="1 shift/reduce" 1485 sr_count=1 1486 fi 1487 if test $gram = rr || test $gram = sr-rr; then 1488 if test -n "$conflicts"; then 1489 conflicts="$conflicts, " 1490 fi 1491 conflicts="${conflicts}1 reduce/reduce" 1492 rr_count=1 1493 fi 1494 1495 # Run tests. 1496 if test $sr_count -eq $sr_exp && test $rr_count -eq $rr_exp; then 1497 ]AT_BISON_CHECK([[-Wnone $file]])[ 1498 ]AT_BISON_CHECK([[-Werror $file]])[ 1499 else 1500 echo "$file: conflicts: $conflicts" > experr 1501 if test $sr_count -ne $sr_exp; then 1502 if test $sr_exp -ne 1; then s=s; else s= ; fi 1503 echo "$file: error: expected $sr_exp shift/reduce conflict$s" >> experr 1504 fi 1505 if test $rr_count -ne $rr_exp; then 1506 if test $rr_exp -ne 1; then s=s; else s= ; fi 1507 echo "$file: error: expected $rr_exp reduce/reduce conflict$s" >> experr 1508 fi 1509 ]AT_BISON_CHECK([[-Wnone $file]], [[1]], [[]], [[experr]])[ 1510 ]AT_BISON_CHECK([[-Werror $file]], [[1]], [[]], [[experr]])[ 1511 fi 1512 done 1513 done 1514 done] 1515 1516 AT_CLEANUP 1517
