tests/conflicts.at

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