tests/conflicts.at

   1 # Exercising Bison on conflicts.                         -*- Autotest -*-
   2
   3 # Copyright (C) 2002-2005, 2007-2015 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 m4_pushdef([AT_CONSISTENT_ERRORS_CHECK], [
 397
 398 AT_SETUP([[parse.error=verbose and consistent errors: $1]])
 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 AT_CLEANUP
 487 ]) dnl AT_CONSISTENT_ERRORS_CHECK
 488
 489
 490
 491
 492 m4_pushdef([AT_PREVIOUS_STATE_GRAMMAR],
 493 [[%nonassoc 'a';
 494
 495 start: consistent-error-on-a-a 'a' ;
 496
 497 consistent-error-on-a-a:
 498     'a' default-reduction
 499   | 'a' default-reduction 'a'
 500   | 'a' shift
 501   ;
 502
 503 default-reduction: /*empty*/ ;
 504 shift: 'b' ;
 505
 506 // Provide another context in which all rules are useful so that this
 507 // test case looks a little more realistic.
 508 start: 'b' consistent-error-on-a-a 'c' ;
 509 ]])
 510
 511 m4_pushdef([AT_PREVIOUS_STATE_INPUT], [[a]])
 512
 513 # Unfortunately, no expected tokens are reported even though 'b' can be
 514 # accepted.  Nevertheless, the main point of this test is to make sure
 515 # that at least the unexpected token is reported.  In a previous version
 516 # of Bison, it wasn't reported because the error is detected in a
 517 # consistent state with an error action, and that case always triggered
 518 # the simple "syntax error" message.
 519 #
 520 # The point isn't to test IELR here, but state merging happens to
 521 # complicate this example.
 522 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr]],
 523                            [AT_PREVIOUS_STATE_GRAMMAR],
 524                            [AT_PREVIOUS_STATE_INPUT],
 525                            [[$end]], [[none]])
 526 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 527                              %glr-parser]],
 528                            [AT_PREVIOUS_STATE_GRAMMAR],
 529                            [AT_PREVIOUS_STATE_INPUT],
 530                            [[$end]], [[none]])
 531 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 532                              %language "c++"]],
 533                            [AT_PREVIOUS_STATE_GRAMMAR],
 534                            [AT_PREVIOUS_STATE_INPUT],
 535                            [[$end]], [[none]])
 536 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 537                              %language "java"]],
 538                            [AT_PREVIOUS_STATE_GRAMMAR],
 539                            [AT_PREVIOUS_STATE_INPUT],
 540                            [[end of input]], [[none]])
 541
 542 # Even canonical LR doesn't foresee the error for 'a'!
 543 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 544                              %define lr.default-reduction consistent]],
 545                            [AT_PREVIOUS_STATE_GRAMMAR],
 546                            [AT_PREVIOUS_STATE_INPUT],
 547                            [[$end]], [[ab]])
 548 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 549                              %define lr.default-reduction accepting]],
 550                            [AT_PREVIOUS_STATE_GRAMMAR],
 551                            [AT_PREVIOUS_STATE_INPUT],
 552                            [[$end]], [[ab]])
 553 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]],
 554                            [AT_PREVIOUS_STATE_GRAMMAR],
 555                            [AT_PREVIOUS_STATE_INPUT],
 556                            [[$end]], [[ab]])
 557
 558 # Only LAC gets it right.
 559 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr
 560                              %define parse.lac full]],
 561                            [AT_PREVIOUS_STATE_GRAMMAR],
 562                            [AT_PREVIOUS_STATE_INPUT],
 563                            [[$end]], [[b]])
 564 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr
 565                              %define parse.lac full]],
 566                            [AT_PREVIOUS_STATE_GRAMMAR],
 567                            [AT_PREVIOUS_STATE_INPUT],
 568                            [[$end]], [[b]])
 569
 570 m4_popdef([AT_PREVIOUS_STATE_GRAMMAR])
 571 m4_popdef([AT_PREVIOUS_STATE_INPUT])
 572
 573 m4_pushdef([AT_USER_ACTION_GRAMMAR],
 574 [[%nonassoc 'a';
 575
 576 // If $$ = 0 here, then we know that the 'a' destructor is being invoked
 577 // incorrectly for the 'b' set in the semantic action below.  All 'a'
 578 // tokens are returned by yylex, which sets $$ = 1.
 579 %destructor {
 580   if (!$$)
 581     fprintf (stderr, "Wrong destructor.\n");
 582 } 'a';
 583
 584 // Rather than depend on an inconsistent state to induce reading a
 585 // lookahead as in the previous grammar, just assign the lookahead in a
 586 // semantic action.  That lookahead isn't needed before either error
 587 // action is encountered.  In a previous version of Bison, this was a
 588 // problem as it meant yychar was not translated into yytoken before
 589 // either error action.  The second error action thus invoked a
 590 // destructor that it selected according to the incorrect yytoken.  The
 591 // first error action would have reported an incorrect unexpected token
 592 // except that, due to the bug described in the previous grammar, the
 593 // unexpected token was not reported at all.
 594 start: error-reduce consistent-error 'a' { USE ($][3); } ;
 595
 596 error-reduce:
 597   'a' 'a' consistent-reduction consistent-error 'a'
 598   { USE (($][1, $][2, $][5)); }
 599 | 'a' error
 600   { USE ($][1); }
 601 ;
 602
 603 consistent-reduction: /*empty*/ {
 604   assert (yychar == YYEMPTY);
 605   yylval = 0;
 606   yychar = 'b';
 607 } ;
 608
 609 consistent-error:
 610   'a' { USE ($][1); }
 611 | /*empty*/ %prec 'a'
 612 ;
 613
 614 // Provide another context in which all rules are useful so that this
 615 // test case looks a little more realistic.
 616 start: 'b' consistent-error 'b' ;
 617 ]])
 618 m4_pushdef([AT_USER_ACTION_INPUT], [[aa]])
 619
 620 AT_CONSISTENT_ERRORS_CHECK([[]],
 621                            [AT_USER_ACTION_GRAMMAR],
 622                            [AT_USER_ACTION_INPUT],
 623                            [['b']], [[none]])
 624 AT_CONSISTENT_ERRORS_CHECK([[%glr-parser]],
 625                            [AT_USER_ACTION_GRAMMAR],
 626                            [AT_USER_ACTION_INPUT],
 627                            [['b']], [[none]])
 628 # No C++ or Java test because yychar cannot be manipulated by users.
 629
 630 AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reduction consistent]],
 631                            [AT_USER_ACTION_GRAMMAR],
 632                            [AT_USER_ACTION_INPUT],
 633                            [['b']], [[none]])
 634
 635 # Canonical LR doesn't foresee the error for 'a'!
 636 AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reduction accepting]],
 637                            [AT_USER_ACTION_GRAMMAR],
 638                            [AT_USER_ACTION_INPUT],
 639                            [[$end]], [[a]])
 640 AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]],
 641                            [AT_USER_ACTION_GRAMMAR],
 642                            [AT_USER_ACTION_INPUT],
 643                            [[$end]], [[a]])
 644
 645 AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full]],
 646                            [AT_USER_ACTION_GRAMMAR],
 647                            [AT_USER_ACTION_INPUT],
 648                            [['b']], [[none]])
 649 AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full
 650                              %define lr.default-reduction accepting]],
 651                            [AT_USER_ACTION_GRAMMAR],
 652                            [AT_USER_ACTION_INPUT],
 653                            [[$end]], [[none]])
 654
 655 m4_popdef([AT_USER_ACTION_GRAMMAR])
 656 m4_popdef([AT_USER_ACTION_INPUT])
 657
 658 m4_popdef([AT_CONSISTENT_ERRORS_CHECK])
 659
 660
 661
 662
 663 ## ------------------------------------------------------- ##
 664 ## LAC: %nonassoc requires splitting canonical LR states.  ##
 665 ## ------------------------------------------------------- ##
 666
 667 # This test case demonstrates that, when %nonassoc is used, canonical
 668 # LR(1) parser table construction followed by conflict resolution
 669 # without further state splitting is not always sufficient to produce a
 670 # parser that can detect all syntax errors as soon as possible on one
 671 # token of lookahead.  However, LAC solves the problem completely even
 672 # with minimal LR parser tables.
 673
 674 AT_SETUP([[LAC: %nonassoc requires splitting canonical LR states]])
 675 AT_BISON_OPTION_PUSHDEFS
 676 AT_DATA_GRAMMAR([[input.y]],
 677 [[%code {
 678   #include <stdio.h>
 679   ]AT_YYERROR_DECLARE[
 680   ]AT_YYLEX_DECLARE[
 681 }
 682
 683 %error-verbose
 684 %nonassoc 'a'
 685
 686 %%
 687
 688 start:
 689   'a' problem 'a' // First context.
 690 | 'b' problem 'b' // Second context.
 691 | 'c' reduce-nonassoc // Just makes reduce-nonassoc useful.
 692 ;
 693
 694 problem:
 695   look reduce-nonassoc
 696 | look 'a'
 697 | look 'b'
 698 ;
 699
 700 // For the state reached after shifting the 'a' in these productions,
 701 // lookahead sets are the same in both the first and second contexts.
 702 // Thus, canonical LR reuses the same state for both contexts.  However,
 703 // the lookahead 'a' for the reduction "look: 'a'" later becomes an
 704 // error action only in the first context.  In order to immediately
 705 // detect the syntax error on 'a' here for only the first context, this
 706 // canonical LR state would have to be split into two states, and the
 707 // 'a' lookahead would have to be removed from only one of the states.
 708 look:
 709   'a' // Reduction lookahead set is always ['a', 'b'].
 710 | 'a' 'b'
 711 | 'a' 'c' // 'c' is forgotten as an expected token.
 712 ;
 713
 714 reduce-nonassoc: %prec 'a';
 715
 716 %%
 717 ]AT_YYERROR_DEFINE[
 718 ]AT_YYLEX_DEFINE(["aaa"])[
 719 ]AT_MAIN_DEFINE
 720 ])
 721 AT_BISON_OPTION_POPDEFS
 722
 723 # Show canonical LR's failure.
 724 AT_BISON_CHECK([[-Dlr.type=canonical-lr -o input.c input.y]],
 725                [[0]], [[]],
 726 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 727 ]])
 728 AT_COMPILE([[input]])
 729 AT_PARSER_CHECK([[./input]], [[1]], [[]],
 730 [[syntax error, unexpected 'a', expecting 'b'
 731 ]])
 732
 733 # It's corrected by LAC.
 734 AT_BISON_CHECK([[-Dlr.type=canonical-lr -Dparse.lac=full \
 735                  -o input.c input.y]], [[0]], [[]],
 736 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 737 ]])
 738 AT_COMPILE([[input]])
 739 AT_PARSER_CHECK([[./input]], [[1]], [[]],
 740 [[syntax error, unexpected 'a', expecting 'b' or 'c'
 741 ]])
 742
 743 # IELR is sufficient when LAC is used.
 744 AT_BISON_CHECK([[-Dlr.type=ielr -Dparse.lac=full -o input.c input.y]],
 745                [[0]], [[]],
 746 [[input.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
 747 ]])
 748 AT_COMPILE([[input]])
 749 AT_PARSER_CHECK([[./input]], [[1]], [[]],
 750 [[syntax error, unexpected 'a', expecting 'b' or 'c'
 751 ]])
 752
 753 AT_CLEANUP
 754
 755 ## ------------------------- ##
 756 ## Unresolved SR Conflicts.  ##
 757 ## ------------------------- ##
 758
 759 AT_SETUP([Unresolved SR Conflicts])
 760
 761 AT_KEYWORDS([report])
 762
 763 AT_DATA([input.y],
 764 [[%token NUM OP
 765 %%
 766 exp: exp OP exp | NUM;
 767 ]])
 768
 769 AT_BISON_CHECK([-o input.c --report=all input.y], 0, [],
 770 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
 771 ]])
 772
 773 # Check the contents of the report.
 774 AT_CHECK([cat input.output], [],
 775 [[State 5 conflicts: 1 shift/reduce
 776
 777
 778 Grammar
 779
 780     0 $accept: exp $end
 781
 782     1 exp: exp OP exp
 783     2    | NUM
 784
 785
 786 Terminals, with rules where they appear
 787
 788 $end (0) 0
 789 error (256)
 790 NUM (258) 2
 791 OP (259) 1
 792
 793
 794 Nonterminals, with rules where they appear
 795
 796 $accept (5)
 797     on left: 0
 798 exp (6)
 799     on left: 1 2, on right: 0 1
 800
 801
 802 State 0
 803
 804     0 $accept: . exp $end
 805     1 exp: . exp OP exp
 806     2    | . NUM
 807
 808     NUM  shift, and go to state 1
 809
 810     exp  go to state 2
 811
 812
 813 State 1
 814
 815     2 exp: NUM .
 816
 817     $default  reduce using rule 2 (exp)
 818
 819
 820 State 2
 821
 822     0 $accept: exp . $end
 823     1 exp: exp . OP exp
 824
 825     $end  shift, and go to state 3
 826     OP    shift, and go to state 4
 827
 828
 829 State 3
 830
 831     0 $accept: exp $end .
 832
 833     $default  accept
 834
 835
 836 State 4
 837
 838     1 exp: . exp OP exp
 839     1    | exp OP . exp
 840     2    | . NUM
 841
 842     NUM  shift, and go to state 1
 843
 844     exp  go to state 5
 845
 846
 847 State 5
 848
 849     1 exp: exp . OP exp
 850     1    | exp OP exp .  [$end, OP]
 851
 852     OP  shift, and go to state 4
 853
 854     OP        [reduce using rule 1 (exp)]
 855     $default  reduce using rule 1 (exp)
 856 ]])
 857
 858 AT_CLEANUP
 859
 860
 861
 862 ## ----------------------- ##
 863 ## Resolved SR Conflicts.  ##
 864 ## ----------------------- ##
 865
 866 AT_SETUP([Resolved SR Conflicts])
 867
 868 AT_KEYWORDS([report])
 869
 870 AT_DATA([input.y],
 871 [[%token NUM OP
 872 %left OP
 873 %%
 874 exp: exp OP exp | NUM;
 875 ]])
 876
 877 AT_BISON_CHECK([-o input.c --report=all input.y])
 878
 879 # Check the contents of the report.
 880 AT_CHECK([cat input.output], [],
 881 [[Grammar
 882
 883     0 $accept: exp $end
 884
 885     1 exp: exp OP exp
 886     2    | NUM
 887
 888
 889 Terminals, with rules where they appear
 890
 891 $end (0) 0
 892 error (256)
 893 NUM (258) 2
 894 OP (259) 1
 895
 896
 897 Nonterminals, with rules where they appear
 898
 899 $accept (5)
 900     on left: 0
 901 exp (6)
 902     on left: 1 2, on right: 0 1
 903
 904
 905 State 0
 906
 907     0 $accept: . exp $end
 908     1 exp: . exp OP exp
 909     2    | . NUM
 910
 911     NUM  shift, and go to state 1
 912
 913     exp  go to state 2
 914
 915
 916 State 1
 917
 918     2 exp: NUM .
 919
 920     $default  reduce using rule 2 (exp)
 921
 922
 923 State 2
 924
 925     0 $accept: exp . $end
 926     1 exp: exp . OP exp
 927
 928     $end  shift, and go to state 3
 929     OP    shift, and go to state 4
 930
 931
 932 State 3
 933
 934     0 $accept: exp $end .
 935
 936     $default  accept
 937
 938
 939 State 4
 940
 941     1 exp: . exp OP exp
 942     1    | exp OP . exp
 943     2    | . NUM
 944
 945     NUM  shift, and go to state 1
 946
 947     exp  go to state 5
 948
 949
 950 State 5
 951
 952     1 exp: exp . OP exp
 953     1    | exp OP exp .  [$end, OP]
 954
 955     $default  reduce using rule 1 (exp)
 956
 957     Conflict between rule 1 and token OP resolved as reduce (%left OP).
 958 ]])
 959
 960 AT_CLEANUP
 961
 962
 963 ## ---------------------- ##
 964 ## %precedence suffices.  ##
 965 ## ---------------------- ##
 966
 967 AT_SETUP([%precedence suffices])
 968
 969 AT_DATA([input.y],
 970 [[%precedence "then"
 971 %precedence "else"
 972 %%
 973 stmt:
 974   "if" cond "then" stmt
 975 | "if" cond "then" stmt "else" stmt
 976 | "stmt"
 977 ;
 978
 979 cond:
 980   "exp"
 981 ;
 982 ]])
 983
 984 AT_BISON_CHECK([-o input.c input.y])
 985
 986 AT_CLEANUP
 987
 988
 989 ## ------------------------------ ##
 990 ## %precedence does not suffice.  ##
 991 ## ------------------------------ ##
 992
 993 AT_SETUP([%precedence does not suffice])
 994
 995 AT_DATA([input.y],
 996 [[%precedence "then"
 997 %precedence "else"
 998 %%
 999 stmt:
1000   "if" cond "then" stmt
1001 | "if" cond "then" stmt "else" stmt
1002 | "stmt"
1003 ;
1004
1005 cond:
1006   "exp"
1007 | cond "then" cond
1008 ;
1009 ]])
1010
1011 AT_BISON_CHECK([-o input.c input.y], 0, [],
1012 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
1013 input.y:12.3-18: warning: rule useless in parser due to conflicts [-Wother]
1014 ]])
1015
1016 AT_CLEANUP
1017
1018
1019 ## -------------------------------- ##
1020 ## Defaulted Conflicted Reduction.  ##
1021 ## -------------------------------- ##
1022
1023 # When there are RR conflicts, some rules are disabled.  Usually it is
1024 # simply displayed as:
1025 #
1026 #    $end           reduce using rule 3 (num)
1027 #    $end           [reduce using rule 4 (id)]
1028 #
1029 # But when 'reduce 3' is the default action, we'd produce:
1030 #
1031 #    $end           [reduce using rule 4 (id)]
1032 #    $default    reduce using rule 3 (num)
1033 #
1034 # In this precise case (a reduction is masked by the default
1035 # reduction), we make the 'reduce 3' explicit:
1036 #
1037 #    $end           reduce using rule 3 (num)
1038 #    $end           [reduce using rule 4 (id)]
1039 #    $default    reduce using rule 3 (num)
1040 #
1041 # Maybe that's not the best display, but then, please propose something
1042 # else.
1043
1044 AT_SETUP([Defaulted Conflicted Reduction])
1045 AT_KEYWORDS([report])
1046
1047 AT_DATA([input.y],
1048 [[%%
1049 exp: num | id;
1050 num: '0';
1051 id : '0';
1052 %%
1053 ]])
1054
1055 AT_BISON_CHECK([-o input.c --report=all input.y], 0, [],
1056 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1057 input.y:4.6-8: warning: rule useless in parser due to conflicts [-Wother]
1058 ]])
1059
1060 # Check the contents of the report.
1061 AT_CHECK([cat input.output], [],
1062 [[Rules useless in parser due to conflicts
1063
1064     4 id: '0'
1065
1066
1067 State 1 conflicts: 1 reduce/reduce
1068
1069
1070 Grammar
1071
1072     0 $accept: exp $end
1073
1074     1 exp: num
1075     2    | id
1076
1077     3 num: '0'
1078
1079     4 id: '0'
1080
1081
1082 Terminals, with rules where they appear
1083
1084 $end (0) 0
1085 '0' (48) 3 4
1086 error (256)
1087
1088
1089 Nonterminals, with rules where they appear
1090
1091 $accept (4)
1092     on left: 0
1093 exp (5)
1094     on left: 1 2, on right: 0
1095 num (6)
1096     on left: 3, on right: 1
1097 id (7)
1098     on left: 4, on right: 2
1099
1100
1101 State 0
1102
1103     0 $accept: . exp $end
1104     1 exp: . num
1105     2    | . id
1106     3 num: . '0'
1107     4 id: . '0'
1108
1109     '0'  shift, and go to state 1
1110
1111     exp  go to state 2
1112     num  go to state 3
1113     id   go to state 4
1114
1115
1116 State 1
1117
1118     3 num: '0' .  [$end]
1119     4 id: '0' .  [$end]
1120
1121     $end      reduce using rule 3 (num)
1122     $end      [reduce using rule 4 (id)]
1123     $default  reduce using rule 3 (num)
1124
1125
1126 State 2
1127
1128     0 $accept: exp . $end
1129
1130     $end  shift, and go to state 5
1131
1132
1133 State 3
1134
1135     1 exp: num .
1136
1137     $default  reduce using rule 1 (exp)
1138
1139
1140 State 4
1141
1142     2 exp: id .
1143
1144     $default  reduce using rule 2 (exp)
1145
1146
1147 State 5
1148
1149     0 $accept: exp $end .
1150
1151     $default  accept
1152 ]])
1153
1154 AT_CLEANUP
1155
1156
1157
1158
1159 ## -------------------- ##
1160 ## %expect not enough.  ##
1161 ## -------------------- ##
1162
1163 AT_SETUP([%expect not enough])
1164
1165 AT_DATA([input.y],
1166 [[%token NUM OP
1167 %expect 0
1168 %%
1169 exp: exp OP exp | NUM;
1170 ]])
1171
1172 AT_BISON_CHECK([-o input.c input.y], 1, [],
1173 [[input.y: error: shift/reduce conflicts: 1 found, 0 expected
1174 ]])
1175 AT_CLEANUP
1176
1177
1178 ## --------------- ##
1179 ## %expect right.  ##
1180 ## --------------- ##
1181
1182 AT_SETUP([%expect right])
1183
1184 AT_DATA([input.y],
1185 [[%token NUM OP
1186 %expect 1
1187 %%
1188 exp: exp OP exp | NUM;
1189 ]])
1190
1191 AT_BISON_CHECK([-o input.c input.y])
1192 AT_CLEANUP
1193
1194
1195 ## ------------------ ##
1196 ## %expect too much.  ##
1197 ## ------------------ ##
1198
1199 AT_SETUP([%expect too much])
1200
1201 AT_DATA([input.y],
1202 [[%token NUM OP
1203 %expect 2
1204 %%
1205 exp: exp OP exp | NUM;
1206 ]])
1207
1208 AT_BISON_CHECK([-o input.c input.y], 1, [],
1209 [[input.y: error: shift/reduce conflicts: 1 found, 2 expected
1210 ]])
1211 AT_CLEANUP
1212
1213
1214 ## ------------------------------- ##
1215 ## %expect with reduce conflicts.  ##
1216 ## ------------------------------- ##
1217
1218 AT_SETUP([%expect with reduce conflicts])
1219
1220 AT_DATA([input.y],
1221 [[%expect 0
1222 %%
1223 program: a 'a' | a a;
1224 a: 'a';
1225 ]])
1226
1227 AT_BISON_CHECK([-o input.c input.y], 1, [],
1228 [[input.y: error: reduce/reduce conflicts: 1 found, 0 expected
1229 ]])
1230 AT_CLEANUP
1231
1232
1233 ## ------------------------- ##
1234 ## %prec with user strings.  ##
1235 ## ------------------------- ##
1236
1237 AT_SETUP([%prec with user string])
1238
1239 AT_DATA([[input.y]],
1240 [[%%
1241 exp:
1242   "foo" %prec "foo"
1243 ;
1244 ]])
1245
1246 AT_BISON_CHECK([-o input.c input.y])
1247 AT_CLEANUP
1248
1249
1250 ## -------------------------------- ##
1251 ## %no-default-prec without %prec.  ##
1252 ## -------------------------------- ##
1253
1254 AT_SETUP([%no-default-prec without %prec])
1255
1256 AT_DATA([[input.y]],
1257 [[%left '+'
1258 %left '*'
1259
1260 %%
1261
1262 %no-default-prec;
1263
1264 e:   e '+' e
1265    | e '*' e
1266    | '0'
1267    ;
1268 ]])
1269
1270 AT_BISON_CHECK([-Wall -o input.c input.y], 0, [],
1271 [[input.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
1272 input.y:1.1-5: warning: useless precedence and associativity for '+' [-Wprecedence]
1273 input.y:2.1-5: warning: useless precedence and associativity for '*' [-Wprecedence]
1274 ]])
1275 AT_CLEANUP
1276
1277
1278 ## ----------------------------- ##
1279 ## %no-default-prec with %prec.  ##
1280 ## ----------------------------- ##
1281
1282 AT_SETUP([%no-default-prec with %prec])
1283
1284 AT_DATA([[input.y]],
1285 [[%left '+'
1286 %left '*'
1287
1288 %%
1289
1290 %no-default-prec;
1291
1292 e:   e '+' e %prec '+'
1293    | e '*' e %prec '*'
1294    | '0'
1295    ;
1296 ]])
1297
1298 AT_BISON_CHECK([-o input.c input.y])
1299 AT_CLEANUP
1300
1301
1302 ## --------------- ##
1303 ## %default-prec.  ##
1304 ## --------------- ##
1305
1306 AT_SETUP([%default-prec])
1307
1308 AT_DATA([[input.y]],
1309 [[%left '+'
1310 %left '*'
1311
1312 %%
1313
1314 %default-prec;
1315
1316 e:   e '+' e
1317    | e '*' e
1318    | '0'
1319    ;
1320 ]])
1321
1322 AT_BISON_CHECK([-o input.c input.y])
1323 AT_CLEANUP
1324
1325
1326 ## ---------------------------------------------- ##
1327 ## Unreachable States After Conflict Resolution.  ##
1328 ## ---------------------------------------------- ##
1329
1330 AT_SETUP([[Unreachable States After Conflict Resolution]])
1331
1332 # If conflict resolution makes states unreachable, remove those states, report
1333 # rules that are then unused, and don't report conflicts in those states.  Test
1334 # what happens when a nonterminal becomes useless as a result of state removal
1335 # since that causes lalr.o's goto map to be rewritten.
1336
1337 AT_DATA([[input.y]],
1338 [[%output "input.c"
1339 %left 'a'
1340
1341 %%
1342
1343 start: resolved_conflict 'a' reported_conflicts 'a' ;
1344
1345 /* S/R conflict resolved as reduce, so the state with item
1346  * (resolved_conflict: 'a' . unreachable1) and all it transition successors are
1347  * unreachable, and the associated production is useless.  */
1348 resolved_conflict:
1349     'a' unreachable1
1350   | %prec 'a'
1351   ;
1352
1353 /* S/R conflict that need not be reported since it is unreachable because of
1354  * the previous conflict resolution.  Nonterminal unreachable1 and all its
1355  * productions are useless.  */
1356 unreachable1:
1357     'a' unreachable2
1358   |
1359   ;
1360
1361 /* Likewise for a R/R conflict and nonterminal unreachable2.  */
1362 unreachable2: | ;
1363
1364 /* Make sure remaining S/R and R/R conflicts are still reported correctly even
1365  * when their states are renumbered due to state removal.  */
1366 reported_conflicts:
1367     'a'
1368   | 'a'
1369   |
1370   ;
1371
1372 ]])
1373
1374 AT_BISON_CHECK([[--report=all input.y]], 0, [],
1375 [[input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
1376 input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1377 input.y:12.5-20: warning: rule useless in parser due to conflicts [-Wother]
1378 input.y:20.5-20: warning: rule useless in parser due to conflicts [-Wother]
1379 input.y:21.4: warning: rule useless in parser due to conflicts [-Wother]
1380 input.y:25.13: warning: rule useless in parser due to conflicts [-Wother]
1381 input.y:25.16: warning: rule useless in parser due to conflicts [-Wother]
1382 input.y:31.5-7: warning: rule useless in parser due to conflicts [-Wother]
1383 input.y:32.4: warning: rule useless in parser due to conflicts [-Wother]
1384 ]])
1385
1386 AT_CHECK([[cat input.output]], 0,
1387 [[Rules useless in parser due to conflicts
1388
1389     2 resolved_conflict: 'a' unreachable1
1390
1391     4 unreachable1: 'a' unreachable2
1392     5             | %empty
1393
1394     6 unreachable2: %empty
1395     7             | %empty
1396
1397     9 reported_conflicts: 'a'
1398    10                   | %empty
1399
1400
1401 State 4 conflicts: 1 shift/reduce
1402 State 5 conflicts: 1 reduce/reduce
1403
1404
1405 Grammar
1406
1407     0 $accept: start $end
1408
1409     1 start: resolved_conflict 'a' reported_conflicts 'a'
1410
1411     2 resolved_conflict: 'a' unreachable1
1412     3                  | %empty
1413
1414     4 unreachable1: 'a' unreachable2
1415     5             | %empty
1416
1417     6 unreachable2: %empty
1418     7             | %empty
1419
1420     8 reported_conflicts: 'a'
1421     9                   | 'a'
1422    10                   | %empty
1423
1424
1425 Terminals, with rules where they appear
1426
1427 $end (0) 0
1428 'a' (97) 1 2 4 8 9
1429 error (256)
1430
1431
1432 Nonterminals, with rules where they appear
1433
1434 $accept (4)
1435     on left: 0
1436 start (5)
1437     on left: 1, on right: 0
1438 resolved_conflict (6)
1439     on left: 2 3, on right: 1
1440 unreachable1 (7)
1441     on left: 4 5, on right: 2
1442 unreachable2 (8)
1443     on left: 6 7, on right: 4
1444 reported_conflicts (9)
1445     on left: 8 9 10, on right: 1
1446
1447
1448 State 0
1449
1450     0 $accept: . start $end
1451     1 start: . resolved_conflict 'a' reported_conflicts 'a'
1452     2 resolved_conflict: . 'a' unreachable1
1453     3                  | . %empty  ['a']
1454
1455     $default  reduce using rule 3 (resolved_conflict)
1456
1457     start              go to state 1
1458     resolved_conflict  go to state 2
1459
1460     Conflict between rule 3 and token 'a' resolved as reduce (%left 'a').
1461
1462
1463 State 1
1464
1465     0 $accept: start . $end
1466
1467     $end  shift, and go to state 3
1468
1469
1470 State 2
1471
1472     1 start: resolved_conflict . 'a' reported_conflicts 'a'
1473
1474     'a'  shift, and go to state 4
1475
1476
1477 State 3
1478
1479     0 $accept: start $end .
1480
1481     $default  accept
1482
1483
1484 State 4
1485
1486     1 start: resolved_conflict 'a' . reported_conflicts 'a'
1487     8 reported_conflicts: . 'a'
1488     9                   | . 'a'
1489    10                   | . %empty  ['a']
1490
1491     'a'  shift, and go to state 5
1492
1493     'a'  [reduce using rule 10 (reported_conflicts)]
1494
1495     reported_conflicts  go to state 6
1496
1497
1498 State 5
1499
1500     8 reported_conflicts: 'a' .  ['a']
1501     9                   | 'a' .  ['a']
1502
1503     'a'       reduce using rule 8 (reported_conflicts)
1504     'a'       [reduce using rule 9 (reported_conflicts)]
1505     $default  reduce using rule 8 (reported_conflicts)
1506
1507
1508 State 6
1509
1510     1 start: resolved_conflict 'a' reported_conflicts . 'a'
1511
1512     'a'  shift, and go to state 7
1513
1514
1515 State 7
1516
1517     1 start: resolved_conflict 'a' reported_conflicts 'a' .
1518
1519     $default  reduce using rule 1 (start)
1520 ]])
1521
1522 AT_DATA([[input-keep.y]],
1523 [[%define lr.keep-unreachable-state
1524 ]])
1525 AT_CHECK([[cat input.y >> input-keep.y]])
1526
1527 AT_BISON_CHECK([[input-keep.y]], 0, [],
1528 [[input-keep.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]
1529 input-keep.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
1530 input-keep.y:22.4: warning: rule useless in parser due to conflicts [-Wother]
1531 input-keep.y:26.16: warning: rule useless in parser due to conflicts [-Wother]
1532 input-keep.y:32.5-7: warning: rule useless in parser due to conflicts [-Wother]
1533 input-keep.y:33.4: warning: rule useless in parser due to conflicts [-Wother]
1534 ]])
1535
1536 AT_CLEANUP
1537
1538
1539 ## ------------------------------------------------------------ ##
1540 ## Solved conflicts report for multiple reductions in a state.  ##
1541 ## ------------------------------------------------------------ ##
1542
1543 AT_SETUP([[Solved conflicts report for multiple reductions in a state]])
1544
1545 # Used to lose earlier solved conflict messages even within a single S/R/R.
1546
1547 AT_DATA([[input.y]],
1548 [[%left 'a'
1549 %right 'b'
1550 %right 'c'
1551 %right 'd'
1552 %%
1553 start:
1554     'a'
1555   | empty_a 'a'
1556   | 'b'
1557   | empty_b 'b'
1558   | 'c'
1559   | empty_c1 'c'
1560   | empty_c2 'c'
1561   | empty_c3 'c'
1562   ;
1563 empty_a: %prec 'a' ;
1564 empty_b: %prec 'b' ;
1565 empty_c1: %prec 'c' ;
1566 empty_c2: %prec 'c' ;
1567 empty_c3: %prec 'd' ;
1568 ]])
1569 AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore])
1570 AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0,
1571 [[State 0
1572
1573     0 $accept: . start $end
1574     1 start: . 'a'
1575     2      | . empty_a 'a'
1576     3      | . 'b'
1577     4      | . empty_b 'b'
1578     5      | . 'c'
1579     6      | . empty_c1 'c'
1580     7      | . empty_c2 'c'
1581     8      | . empty_c3 'c'
1582     9 empty_a: . %empty  ['a']
1583    10 empty_b: . %empty  []
1584    11 empty_c1: . %empty  []
1585    12 empty_c2: . %empty  []
1586    13 empty_c3: . %empty  ['c']
1587
1588     'b'  shift, and go to state 1
1589
1590     'c'       reduce using rule 13 (empty_c3)
1591     $default  reduce using rule 9 (empty_a)
1592
1593     start     go to state 2
1594     empty_a   go to state 3
1595     empty_b   go to state 4
1596     empty_c1  go to state 5
1597     empty_c2  go to state 6
1598     empty_c3  go to state 7
1599
1600     Conflict between rule 9 and token 'a' resolved as reduce (%left 'a').
1601     Conflict between rule 10 and token 'b' resolved as shift (%right 'b').
1602     Conflict between rule 11 and token 'c' resolved as shift (%right 'c').
1603     Conflict between rule 12 and token 'c' resolved as shift (%right 'c').
1604     Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd').
1605
1606
1607 State 1
1608 ]])
1609
1610 AT_CLEANUP
1611
1612
1613 ## ------------------------------------------------------------ ##
1614 ## %nonassoc error actions for multiple reductions in a state.  ##
1615 ## ------------------------------------------------------------ ##
1616
1617 # Used to abort when trying to resolve conflicts as %nonassoc error actions for
1618 # multiple reductions in a state.
1619
1620 # For a %nonassoc error action token, used to print the first remaining
1621 # reduction on that token without brackets.
1622
1623 AT_SETUP([[%nonassoc error actions for multiple reductions in a state]])
1624
1625 AT_DATA([[input.y]],
1626 [[%nonassoc 'a' 'b' 'c'
1627 %%
1628 start:
1629     'a'
1630   | empty_a 'a'
1631   | 'b'
1632   | empty_b 'b'
1633   | 'c'
1634   | empty_c1 'c'
1635   | empty_c2 'c'
1636   | empty_c3 'c'
1637   ;
1638 empty_a: %prec 'a' ;
1639 empty_b: %prec 'b' ;
1640 empty_c1: %prec 'c' ;
1641 empty_c2: %prec 'c' ;
1642 empty_c3: %prec 'c' ;
1643 ]])
1644
1645 AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore])
1646 AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0,
1647 [[State 0
1648
1649     0 $accept: . start $end
1650     1 start: . 'a'
1651     2      | . empty_a 'a'
1652     3      | . 'b'
1653     4      | . empty_b 'b'
1654     5      | . 'c'
1655     6      | . empty_c1 'c'
1656     7      | . empty_c2 'c'
1657     8      | . empty_c3 'c'
1658     9 empty_a: . %empty  []
1659    10 empty_b: . %empty  []
1660    11 empty_c1: . %empty  []
1661    12 empty_c2: . %empty  ['c']
1662    13 empty_c3: . %empty  ['c']
1663
1664     'a'  error (nonassociative)
1665     'b'  error (nonassociative)
1666     'c'  error (nonassociative)
1667
1668     'c'  [reduce using rule 12 (empty_c2)]
1669     'c'  [reduce using rule 13 (empty_c3)]
1670
1671     start     go to state 1
1672     empty_a   go to state 2
1673     empty_b   go to state 3
1674     empty_c1  go to state 4
1675     empty_c2  go to state 5
1676     empty_c3  go to state 6
1677
1678     Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a').
1679     Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 'b').
1680     Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 'c').
1681
1682
1683 State 1
1684 ]])
1685 AT_CLEANUP
1686
1687
1688 ## -------------------- ##
1689 ## %expect-rr non GLR.  ##
1690 ## -------------------- ##
1691
1692 AT_SETUP([[%expect-rr non GLR]])
1693
1694 AT_DATA([[1.y]],
1695 [[%expect-rr 0
1696 %%
1697 exp: 'a'
1698 ]])
1699
1700 AT_BISON_CHECK([[1.y]], [[0]], [],
1701 [[1.y: warning: %expect-rr applies only to GLR parsers [-Wother]
1702 ]])
1703
1704 AT_DATA([[2.y]],
1705 [[%expect-rr 1
1706 %%
1707 exp: 'a' | 'a';
1708 ]])
1709
1710 AT_BISON_CHECK([[2.y]], [[0]], [],
1711 [[2.y: warning: %expect-rr applies only to GLR parsers [-Wother]
1712 2.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1713 2.y:3.12-14: warning: rule useless in parser due to conflicts [-Wother]
1714 ]])
1715
1716 AT_CLEANUP
1717
1718
1719 ## ---------------------------------- ##
1720 ## -W versus %expect and %expect-rr.  ##
1721 ## ---------------------------------- ##
1722
1723 AT_SETUP([[-W versus %expect and %expect-rr]])
1724
1725 AT_DATA([[sr-rr.y]],
1726 [[%glr-parser
1727 %%
1728 start: 'a' | A 'a' | B 'a' ;
1729 A: ;
1730 B: ;
1731 ]])
1732 AT_DATA([[sr.y]],
1733 [[%glr-parser
1734 %%
1735 start: 'a' | A 'a' ;
1736 A: ;
1737 ]])
1738 AT_DATA([[rr.y]],
1739 [[%glr-parser
1740 %%
1741 start: A | B ;
1742 A: ;
1743 B: ;
1744 ]])
1745
1746 AT_BISON_CHECK([[sr-rr.y]], [[0]], [[]],
1747 [[sr-rr.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
1748 sr-rr.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1749 ]])
1750 AT_BISON_CHECK([[-Wno-conflicts-sr sr-rr.y]], [[0]], [[]],
1751 [[sr-rr.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1752 ]])
1753 AT_BISON_CHECK([[-Wno-conflicts-rr sr-rr.y]], [[0]], [[]],
1754 [[sr-rr.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
1755 ]])
1756
1757 [
1758 # This is piece of code is rather complex for a simple task: try every
1759 # combinaison of (0 or 1 real SR) x (0 or 1 real RR) x (don't %expect
1760 # or %expect 0, 1, or 2 SR) x (don't %expect-rr or %expect-rr 0, 1, or 2
1761 # RR).
1762
1763 # Number and types of genuine conflicts in the grammar.
1764 for gram in sr-rr sr rr; do
1765   # Number of expected s/r conflicts.
1766   for sr_exp_i in '' 0 1 2; do
1767     # Number of expected r/r conflicts.
1768     for rr_exp_i in '' 0 1 2; do
1769       test -z "$sr_exp_i" && test -z "$rr_exp_i" && continue
1770
1771       # Build grammar file.
1772       sr_exp=0
1773       rr_exp=0
1774       file=$gram
1775       directives=
1776       if test -n "$sr_exp_i"; then
1777         sr_exp=$sr_exp_i
1778         file=$file-expect-$sr_exp
1779         directives="%expect $sr_exp"
1780       fi
1781       if test -n "$rr_exp_i"; then
1782         rr_exp=$rr_exp_i
1783         file=$file-expect-rr-$rr_exp
1784         directives="$directives %expect-rr $rr_exp"
1785       fi
1786       file=$file.y
1787       echo "$directives" > $file
1788       cat $gram.y >> $file
1789
1790       # Number of found conflicts.
1791       case $gram in
1792         (sr)    sr_count=1; rr_count=0;;
1793         (rr)    sr_count=0; rr_count=1;;
1794         (sr-rr) sr_count=1; rr_count=1;;
1795       esac
1796
1797       # Update number of expected conflicts: if %expect is given then
1798       # %expect-rr defaults to 0, and vice-versa.  Leave empty if
1799       # nothing expected.
1800       case $sr_exp_i:$rr_exp_i in
1801         ?:) rr_exp_i=0;;
1802         :?) sr_exp_i=0;;
1803       esac
1804
1805       # Run tests.
1806       if test $sr_count -eq $sr_exp && test $rr_count -eq $rr_exp; then
1807         ]AT_BISON_CHECK([[-Wnone $file]])[
1808         ]AT_BISON_CHECK([[-Werror $file]])[
1809       else
1810         {
1811           if test -z "$sr_exp_i" && test "$sr_count" -ne 0; then
1812             echo "warning: $sr_count shift/reduce conflicts"
1813           elif test "$sr_exp_i" -ne "$sr_count"; then
1814             echo "error: shift/reduce conflicts: $sr_count found, $sr_exp_i expected"
1815           fi
1816           if test -z "$rr_exp_i" && test "$rr_count" -ne 0; then
1817             echo "warning: $rr_count reduce/reduce conflicts"
1818           elif test "$rr_exp_i" -ne "$rr_count"; then
1819             echo "error: reduce/reduce conflicts: $rr_count found, $rr_exp_i expected"
1820           fi
1821         } | sed -e "s/^/$file: /" > experr
1822         ]AT_BISON_CHECK([[-Wnone $file]], [[1]], [[]], [[experr]])[
1823         ]AT_BISON_CHECK([[-Werror $file]], [[1]], [[]], [[experr]])[
1824       fi
1825     done
1826   done
1827 done]
1828
1829 AT_CLEANUP