tests/conflicts.at

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