tests/conflicts.at

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