tests/conflicts.at

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