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