tests/conflicts.at

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