tests/conflicts.at

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