tests/reduce.at

   1 # Exercising Bison Grammar Reduction.                      -*- Autotest -*-
   2
   3 # Copyright (C) 2001-2002, 2007-2015, 2018-2020 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([[Grammar Reduction.]])
  20
  21
  22 ## ------------------- ##
  23 ## Useless Terminals.  ##
  24 ## ------------------- ##
  25
  26 AT_SETUP([Useless Terminals])
  27
  28 AT_DATA([[input.y]],
  29 [[%verbose
  30 %output "input.c"
  31
  32 %token useless1
  33 %token useless2
  34 %token useless3
  35 %token useless4
  36 %token useless5
  37 %token useless6
  38 %token useless7
  39 %token useless8
  40 %token useless9
  41
  42 %token useful
  43 %%
  44 exp: useful;
  45 ]])
  46
  47 AT_BISON_CHECK([[input.y]])
  48
  49 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
  50 [[Terminals unused in grammar
  51     useless1
  52     useless2
  53     useless3
  54     useless4
  55     useless5
  56     useless6
  57     useless7
  58     useless8
  59     useless9
  60 ]])
  61
  62 AT_CLEANUP
  63
  64
  65
  66 ## ---------------------- ##
  67 ## Useless Nonterminals.  ##
  68 ## ---------------------- ##
  69
  70 AT_SETUP([Useless Nonterminals])
  71 AT_BISON_OPTION_PUSHDEFS
  72
  73 AT_DATA([[input.y]],
  74 [[%code {
  75   ]AT_YYERROR_DECLARE_EXTERN[
  76   ]AT_YYLEX_DECLARE_EXTERN[
  77 }
  78 %verbose
  79 %output "input.c"
  80
  81 %token useful
  82 %%
  83 exp: useful;
  84 useless1:
  85 useless2:
  86 useless3:
  87 ]])
  88
  89 AT_BISON_CHECK([[input.y]], 0, [],
  90 [[input.y: warning: 3 nonterminals useless in grammar [-Wother]
  91 input.y: warning: 3 rules useless in grammar [-Wother]
  92 input.y:11.1-8: warning: nonterminal useless in grammar: useless1 [-Wother]
  93 input.y:12.1-8: warning: nonterminal useless in grammar: useless2 [-Wother]
  94 input.y:13.1-8: warning: nonterminal useless in grammar: useless3 [-Wother]
  95 ]])
  96
  97 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
  98 [[Nonterminals useless in grammar
  99     useless1
 100     useless2
 101     useless3
 102 Rules useless in grammar
 103     2 useless1: %empty
 104     3 useless2: %empty
 105     4 useless3: %empty
 106 ]])
 107
 108 # Make sure the generated parser is correct.
 109 AT_COMPILE([input.o])
 110
 111 AT_BISON_OPTION_POPDEFS
 112 AT_CLEANUP
 113
 114
 115
 116 ## --------------- ##
 117 ## Useless Rules.  ##
 118 ## --------------- ##
 119
 120 AT_SETUP([Useless Rules])
 121
 122 AT_BISON_OPTION_PUSHDEFS
 123 AT_KEYWORDS([report])
 124
 125 AT_DATA([[input.y]],
 126 [[%code {
 127   ]AT_YYERROR_DECLARE_EXTERN[
 128   ]AT_YYLEX_DECLARE_EXTERN[
 129 }
 130 %verbose
 131 %output "input.c"
 132 %token useful
 133 %%
 134 exp: useful;
 135 useless1: '1';
 136 useless2: '2';
 137 useless3: '3';
 138 useless4: '4';
 139 useless5: '5';
 140 useless6: '6';
 141 useless7: '7';
 142 useless8: '8';
 143 useless9: '9';
 144 ]])
 145
 146 AT_BISON_CHECK([[-fcaret input.y]], 0, [],
 147 [[input.y: warning: 9 nonterminals useless in grammar [-Wother]
 148 input.y: warning: 9 rules useless in grammar [-Wother]
 149 input.y:10.1-8: warning: nonterminal useless in grammar: useless1 [-Wother]
 150    10 | useless1: '1';
 151       | ^~~~~~~~
 152 input.y:11.1-8: warning: nonterminal useless in grammar: useless2 [-Wother]
 153    11 | useless2: '2';
 154       | ^~~~~~~~
 155 input.y:12.1-8: warning: nonterminal useless in grammar: useless3 [-Wother]
 156    12 | useless3: '3';
 157       | ^~~~~~~~
 158 input.y:13.1-8: warning: nonterminal useless in grammar: useless4 [-Wother]
 159    13 | useless4: '4';
 160       | ^~~~~~~~
 161 input.y:14.1-8: warning: nonterminal useless in grammar: useless5 [-Wother]
 162    14 | useless5: '5';
 163       | ^~~~~~~~
 164 input.y:15.1-8: warning: nonterminal useless in grammar: useless6 [-Wother]
 165    15 | useless6: '6';
 166       | ^~~~~~~~
 167 input.y:16.1-8: warning: nonterminal useless in grammar: useless7 [-Wother]
 168    16 | useless7: '7';
 169       | ^~~~~~~~
 170 input.y:17.1-8: warning: nonterminal useless in grammar: useless8 [-Wother]
 171    17 | useless8: '8';
 172       | ^~~~~~~~
 173 input.y:18.1-8: warning: nonterminal useless in grammar: useless9 [-Wother]
 174    18 | useless9: '9';
 175       | ^~~~~~~~
 176 ]])
 177
 178
 179 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 180 [[Nonterminals useless in grammar
 181     useless1
 182     useless2
 183     useless3
 184     useless4
 185     useless5
 186     useless6
 187     useless7
 188     useless8
 189     useless9
 190 Terminals unused in grammar
 191     '1'
 192     '2'
 193     '3'
 194     '4'
 195     '5'
 196     '6'
 197     '7'
 198     '8'
 199     '9'
 200 Rules useless in grammar
 201     2 useless1: '1'
 202     3 useless2: '2'
 203     4 useless3: '3'
 204     5 useless4: '4'
 205     6 useless5: '5'
 206     7 useless6: '6'
 207     8 useless7: '7'
 208     9 useless8: '8'
 209    10 useless9: '9'
 210 ]])
 211
 212 # Make sure the generated parser is correct.
 213 AT_COMPILE([input.o])
 214
 215 AT_BISON_OPTION_POPDEFS
 216 AT_CLEANUP
 217
 218
 219
 220 ## --------------- ##
 221 ## Useless Parts.  ##
 222 ## --------------- ##
 223
 224 AT_SETUP([Useless Parts])
 225
 226 # We used to emit code that used symbol numbers before the useless
 227 # symbol elimination, hence before the renumbering of the useful
 228 # symbols.  As a result, the evaluation of the skeleton failed because
 229 # it used non existing symbol numbers.  Which is the happy scenario:
 230 # we could use numbers of other existing symbols...
 231 # http://lists.gnu.org/archive/html/bug-bison/2019-01/msg00044.html
 232
 233 AT_BISON_OPTION_PUSHDEFS
 234 AT_DATA([[input.y]],
 235 [[%code {
 236   ]AT_YYERROR_DECLARE_EXTERN[
 237   ]AT_YYLEX_DECLARE_EXTERN[
 238 }
 239 %union { void* ptr; }
 240 %type <ptr> used1
 241 %type <ptr> used2
 242
 243 %%
 244 start
 245  : used1
 246  ;
 247
 248 used1
 249  : used2 { $$ = $1; }
 250  ;
 251
 252 unused
 253  : used2
 254  ;
 255
 256 used2
 257  : { $$ = YY_NULLPTR; }
 258  ;
 259 ]])
 260
 261 AT_BISON_CHECK([[-fcaret -rall -o input.c input.y]], 0, [],
 262 [[input.y: warning: 1 nonterminal useless in grammar [-Wother]
 263 input.y: warning: 1 rule useless in grammar [-Wother]
 264 input.y:18.1-6: warning: nonterminal useless in grammar: unused [-Wother]
 265    18 | unused
 266       | ^~~~~~
 267 ]])
 268
 269
 270 AT_CHECK([[sed -n '/^State 0/q;/^$/!p' input.output]], 0,
 271 [[Nonterminals useless in grammar
 272     unused
 273 Rules useless in grammar
 274     4 unused: used2
 275 Grammar
 276     0 $accept: start $end
 277     1 start: used1
 278     2 used1: used2
 279     3 used2: %empty
 280 Terminals, with rules where they appear
 281     $end (0) 0
 282     error (256)
 283 Nonterminals, with rules where they appear
 284     $accept (3)
 285         on left: 0
 286     start (4)
 287         on left: 1
 288         on right: 0
 289     used1 <ptr> (5)
 290         on left: 2
 291         on right: 1
 292     used2 <ptr> (6)
 293         on left: 3
 294         on right: 2
 295 ]])
 296
 297 # Make sure the generated parser is correct.
 298 AT_COMPILE([input.o])
 299
 300 AT_BISON_OPTION_POPDEFS
 301 AT_CLEANUP
 302
 303
 304
 305 ## ------------------- ##
 306 ## Reduced Automaton.  ##
 307 ## ------------------- ##
 308
 309 # Check that the automaton is that as the for the grammar reduced by
 310 # hand.
 311
 312 AT_SETUP([Reduced Automaton])
 313
 314 AT_KEYWORDS([report])
 315
 316 # The non reduced grammar.
 317 # ------------------------
 318 AT_DATA([[not-reduced.y]],
 319 [[/* A useless token. */
 320 %token useless_token
 321 /* A useful one. */
 322 %token useful
 323 %verbose
 324 %output "not-reduced.c"
 325
 326 %%
 327
 328 exp: useful            { /* A useful action. */ }
 329    | non_productive    { /* A non productive action. */ }
 330    ;
 331
 332 not_reachable: useful  { /* A not reachable action. */ }
 333              ;
 334
 335 non_productive: non_productive useless_token
 336                        { /* Another non productive action. */ }
 337               ;
 338 %%
 339 ]])
 340
 341 AT_BISON_CHECK([[-fcaret not-reduced.y]], 0, [],
 342 [[not-reduced.y: warning: 2 nonterminals useless in grammar [-Wother]
 343 not-reduced.y: warning: 3 rules useless in grammar [-Wother]
 344 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable [-Wother]
 345    14 | not_reachable: useful  { /* A not reachable action. */ }
 346       | ^~~~~~~~~~~~~
 347 not-reduced.y:17.1-14: warning: nonterminal useless in grammar: non_productive [-Wother]
 348    17 | non_productive: non_productive useless_token
 349       | ^~~~~~~~~~~~~~
 350 not-reduced.y:11.6-57: warning: rule useless in grammar [-Wother]
 351    11 |    | non_productive    { /* A non productive action. */ }
 352       |      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 353 ]])
 354
 355 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0,
 356 [[Nonterminals useless in grammar
 357     not_reachable
 358     non_productive
 359 Terminals unused in grammar
 360     useless_token
 361 Rules useless in grammar
 362     2 exp: non_productive
 363     3 not_reachable: useful
 364     4 non_productive: non_productive useless_token
 365 ]])
 366
 367 # The reduced grammar.
 368 # --------------------
 369 AT_DATA([[reduced.y]],
 370 [[/* A useless token. */
 371 %token useless_token
 372 /* A useful one. */
 373 %token useful
 374 %verbose
 375 %output "reduced.c"
 376
 377 %%
 378
 379 exp: useful            { /* A useful action. */ }
 380 //   | non_productive    { /* A non productive action. */ } */
 381    ;
 382
 383 //not_reachable: useful  { /* A not reachable action. */ }
 384 //             ;
 385
 386 //non_productive: non_productive useless_token
 387 //                       { /* Another non productive action. */ }
 388 //              ;
 389 %%
 390 ]])
 391
 392 AT_BISON_CHECK([[reduced.y]])
 393
 394 # Comparing the parsers.
 395 cp reduced.c expout
 396 AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout])
 397
 398 AT_CLEANUP
 399
 400
 401
 402 ## ------------------- ##
 403 ## Underivable Rules.  ##
 404 ## ------------------- ##
 405
 406 AT_SETUP([Underivable Rules])
 407
 408 AT_KEYWORDS([report])
 409
 410 AT_DATA([[input.y]],
 411 [[%verbose
 412 %output "input.c"
 413 %token useful
 414 %%
 415 exp: useful | underivable;
 416 underivable: indirection;
 417 indirection: underivable;
 418 ]])
 419
 420 AT_BISON_CHECK([[-fcaret input.y]], 0, [],
 421 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
 422 input.y: warning: 3 rules useless in grammar [-Wother]
 423 input.y:6.1-11: warning: nonterminal useless in grammar: underivable [-Wother]
 424     6 | underivable: indirection;
 425       | ^~~~~~~~~~~
 426 input.y:7.1-11: warning: nonterminal useless in grammar: indirection [-Wother]
 427     7 | indirection: underivable;
 428       | ^~~~~~~~~~~
 429 input.y:5.15-25: warning: rule useless in grammar [-Wother]
 430     5 | exp: useful | underivable;
 431       |               ^~~~~~~~~~~
 432 ]])
 433
 434 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0,
 435 [[Nonterminals useless in grammar
 436     underivable
 437     indirection
 438 Rules useless in grammar
 439     2 exp: underivable
 440     3 underivable: indirection
 441     4 indirection: underivable
 442 ]])
 443
 444 AT_CLEANUP
 445
 446
 447
 448 ## ---------------- ##
 449 ## Empty Language.  ##
 450 ## ---------------- ##
 451
 452 AT_SETUP([Empty Language])
 453
 454 AT_DATA([[input.y]],
 455 [[%output "input.c"
 456 %%
 457 exp: exp;
 458 ]])
 459
 460 AT_BISON_CHECK([[input.y]], 1, [],
 461 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
 462 input.y: warning: 2 rules useless in grammar [-Wother]
 463 input.y:3.1-3: fatal error: start symbol exp does not derive any sentence
 464 ]])
 465
 466 AT_CLEANUP
 467
 468
 469
 470 ## ----------------- ##
 471 ## %define lr.type.  ##
 472 ## ----------------- ##
 473
 474 # AT_TEST_LR_TYPE(DESCRIPTION,
 475 #                 DECLS, GRAMMAR, INPUT,
 476 #                 BISON-STDERR, TABLES,
 477 #                 [OTHER-CHECKS],
 478 #                 [PARSER-EXIT-VALUE],
 479 #                 [PARSER-STDOUT], [PARSER-STDERR])
 480 # -------------------------------------------------
 481 m4_define([AT_TEST_LR_TYPE],
 482 [
 483 AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1],
 484                          [[LALR]], [[]],
 485                          [$2], m4_shiftn(2, $@))
 486 AT_TEST_TABLES_AND_PARSE([[%define lr.type lalr: ]$1],
 487                          [[LALR]], [[]],
 488                          [[%define lr.type lalr
 489 ]$2],
 490                          m4_shiftn(2, $@))
 491 AT_TEST_TABLES_AND_PARSE([[%define lr.type ielr: ]$1],
 492                          [[IELR]], [[]],
 493                          [[%define lr.type ielr
 494 ]$2],
 495                          m4_shiftn(2, $@))
 496 AT_TEST_TABLES_AND_PARSE([[%define lr.type canonical-lr: ]$1],
 497                          [[canonical LR]], [[]],
 498                          [[%define lr.type canonical-lr
 499 ]$2],
 500                          m4_shiftn(2, $@))
 501 ])
 502
 503 AT_TEST_LR_TYPE([[Single State Split]],
 504 [[%left 'a'
 505 // Conflict resolution renders state 12 unreachable for canonical LR(1).  We
 506 // keep it so that the parser table diff is easier to code.
 507 %define lr.keep-unreachable-state]],
 508 [[
 509 S: 'a' A 'a' /* rule 1 */
 510  | 'b' A 'b' /* rule 2 */
 511  | 'c' c     /* rule 3 */
 512  ;
 513
 514 /* A conflict should appear after the first 'a' in rules 4 and 5 but only after
 515    having shifted the first 'a' in rule 1.  However, when LALR(1) merging is
 516    chosen, the state containing that conflict is reused after having seen the
 517    first 'b' in rule 2 and then the first 'a' in rules 4 and 5.  In both cases,
 518    because of the merged state, if the next token is an 'a', the %left forces a
 519    reduction action with rule 5.  In the latter case, only a shift is actually
 520    grammatically correct.  Thus, the parser would report a syntax error for the
 521    grammatically correct sentence "baab" because it would encounter a syntax
 522    error after that incorrect reduction.
 523
 524    Despite not being LALR(1), Menhir version 20070322 suffers from this problem
 525    as well.  It uses David Pager's weak compatibility test for merging states.
 526    Bison and Menhir accept non-LR(1) grammars with conflict resolution.  Pager
 527    designed his algorithm only for LR(1) grammars.  */
 528 A: 'a' 'a' /* rule 4 */
 529  | 'a'     /* rule 5 */
 530  ;
 531
 532 /* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as
 533    useless after conflict resolution.  This proves that, even though LALR(1)
 534    generates incorrect parser tables sometimes, Bison will not necessarily
 535    produce any warning to help the user realize it.  */
 536 c: 'a' 'b' /* rule 6 */
 537  | A       /* rule 7 */
 538  ;
 539 ]],
 540
 541 dnl INPUT
 542 [['b', 'a', 'a', 'b']],
 543
 544 dnl BISON-STDERR
 545 [],
 546
 547 dnl TABLES
 548 [[State 0
 549
 550     0 $accept: . S $end
 551     1 S: . 'a' A 'a'
 552     2  | . 'b' A 'b'
 553     3  | . 'c' c
 554
 555     'a'  shift, and go to state 1
 556     'b'  shift, and go to state 2
 557     'c'  shift, and go to state 3
 558
 559     S  go to state 4
 560
 561
 562 State 1
 563
 564     1 S: 'a' . A 'a'
 565     4 A: . 'a' 'a'
 566     5  | . 'a'
 567
 568     'a'  shift, and go to state 5
 569
 570     A  go to state 6
 571
 572
 573 State 2
 574
 575     2 S: 'b' . A 'b'
 576     4 A: . 'a' 'a'
 577     5  | . 'a'
 578
 579     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[
 580
 581     A  go to state 7
 582
 583
 584 State 3
 585
 586     3 S: 'c' . c
 587     4 A: . 'a' 'a'
 588     5  | . 'a'
 589     6 c: . 'a' 'b'
 590     7  | . A
 591
 592     'a'  shift, and go to state 8
 593
 594     A  go to state 9
 595     c  go to state 10
 596
 597
 598 State 4
 599
 600     0 $accept: S . $end
 601
 602     $end  shift, and go to state 11
 603
 604
 605 State 5
 606
 607     4 A: 'a' . 'a'
 608     5  | 'a' .  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
 609
 610     ]AT_COND_CASE([[canonical LR]], [['a']],
 611                   [[$default]])[  reduce using rule 5 (A)
 612
 613     Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
 614
 615
 616 State 6
 617
 618     1 S: 'a' A . 'a'
 619
 620     'a'  shift, and go to state 13
 621
 622
 623 State 7
 624
 625     2 S: 'b' A . 'b'
 626
 627     'b'  shift, and go to state 14
 628
 629
 630 State 8
 631
 632     4 A: 'a' . 'a'
 633     5  | 'a' .  [$end]
 634     6 c: 'a' . 'b'
 635
 636     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]],
 637                                               [[12]])[
 638     'b'  shift, and go to state 15
 639
 640     ]AT_COND_CASE([[canonical LR]], [[$end]],
 641                   [[$default]])[  reduce using rule 5 (A)
 642
 643
 644 State 9
 645
 646     7 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 647
 648     ]AT_COND_CASE([[canonical LR]], [[$end]],
 649                   [[$default]])[  reduce using rule 7 (c)
 650
 651
 652 State 10
 653
 654     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 655
 656     ]AT_COND_CASE([[canonical LR]], [[$end]],
 657                   [[$default]])[  reduce using rule 3 (S)
 658
 659
 660 State 11
 661
 662     0 $accept: S $end .
 663
 664     $default  accept
 665
 666
 667 State 12
 668
 669     4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
 670
 671     ]AT_COND_CASE([[canonical LR]], [['a']],
 672                   [[$default]])[  reduce using rule 4 (A)
 673
 674
 675 State 13
 676
 677     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 678
 679     ]AT_COND_CASE([[canonical LR]], [[$end]],
 680                   [[$default]])[  reduce using rule 1 (S)
 681
 682
 683 State 14
 684
 685     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 686
 687     ]AT_COND_CASE([[canonical LR]], [[$end]],
 688                   [[$default]])[  reduce using rule 2 (S)
 689
 690
 691 State 15
 692
 693     6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 694
 695     ]AT_COND_CASE([[canonical LR]], [[$end]],
 696                   [[$default]])[  reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
 697                                                                        [[]], [[
 698
 699
 700 State 16
 701
 702     4 A: 'a' . 'a'
 703     5  | 'a' .  ['b']
 704
 705     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]],
 706                                               [[12]])[
 707
 708     ]AT_COND_CASE([[canonical LR]], [['b']],
 709                   [[$default]])[  reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
 710
 711
 712 State 17
 713
 714     4 A: 'a' 'a' .  [$end]
 715
 716     $end  reduce using rule 4 (A)
 717
 718
 719 State 18
 720
 721     4 A: 'a' 'a' .  ['b']
 722
 723     'b'  reduce using rule 4 (A)]])])[
 724 ]],
 725
 726 dnl OTHER-CHECKS
 727 [],
 728
 729 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
 730 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
 731 [],
 732 [AT_COND_CASE([[LALR]],
 733 [[syntax error
 734 ]])])
 735
 736 AT_TEST_LR_TYPE([[Lane Split]],
 737 [[%left 'a'
 738 // Conflict resolution renders state 16 unreachable for canonical LR(1).  We
 739 // keep it so that the parser table diff is easier to code.
 740 %define lr.keep-unreachable-state]],
 741 [[
 742 /* Similar to the last test case set but two states must be split.  */
 743 S: 'a' A 'a' /* rule 1 */
 744  | 'b' A 'b' /* rule 2 */
 745  | 'c' c     /* rule 3 */
 746  ;
 747
 748 A: 'a' 'a' 'a' /* rule 4 */
 749  | 'a' 'a'     /* rule 5 */
 750  ;
 751
 752 c: 'a' 'a' 'b' /* rule 6 */
 753  | A           /* rule 7 */
 754  ;
 755 ]],
 756
 757 dnl INPUT
 758 [['b', 'a', 'a', 'a', 'b']],
 759
 760 dnl BISON-STDERR
 761 [],
 762
 763 dnl TABLES
 764 [[State 0
 765
 766     0 $accept: . S $end
 767     1 S: . 'a' A 'a'
 768     2  | . 'b' A 'b'
 769     3  | . 'c' c
 770
 771     'a'  shift, and go to state 1
 772     'b'  shift, and go to state 2
 773     'c'  shift, and go to state 3
 774
 775     S  go to state 4
 776
 777
 778 State 1
 779
 780     1 S: 'a' . A 'a'
 781     4 A: . 'a' 'a' 'a'
 782     5  | . 'a' 'a'
 783
 784     'a'  shift, and go to state 5
 785
 786     A  go to state 6
 787
 788
 789 State 2
 790
 791     2 S: 'b' . A 'b'
 792     4 A: . 'a' 'a' 'a'
 793     5  | . 'a' 'a'
 794
 795     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[
 796
 797     A  go to state 7
 798
 799
 800 State 3
 801
 802     3 S: 'c' . c
 803     4 A: . 'a' 'a' 'a'
 804     5  | . 'a' 'a'
 805     6 c: . 'a' 'a' 'b'
 806     7  | . A
 807
 808     'a'  shift, and go to state 8
 809
 810     A  go to state 9
 811     c  go to state 10
 812
 813
 814 State 4
 815
 816     0 $accept: S . $end
 817
 818     $end  shift, and go to state 11
 819
 820
 821 State 5
 822
 823     4 A: 'a' . 'a' 'a'
 824     5  | 'a' . 'a'
 825
 826     'a'  shift, and go to state 12
 827
 828
 829 State 6
 830
 831     1 S: 'a' A . 'a'
 832
 833     'a'  shift, and go to state 13
 834
 835
 836 State 7
 837
 838     2 S: 'b' A . 'b'
 839
 840     'b'  shift, and go to state 14
 841
 842
 843 State 8
 844
 845     4 A: 'a' . 'a' 'a'
 846     5  | 'a' . 'a'
 847     6 c: 'a' . 'a' 'b'
 848
 849     'a'  shift, and go to state 15
 850
 851
 852 State 9
 853
 854     7 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 855
 856     ]AT_COND_CASE([[canonical LR]], [[$end]],
 857                   [[$default]])[  reduce using rule 7 (c)
 858
 859
 860 State 10
 861
 862     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 863
 864     ]AT_COND_CASE([[canonical LR]], [[$end]],
 865                   [[$default]])[  reduce using rule 3 (S)
 866
 867
 868 State 11
 869
 870     0 $accept: S $end .
 871
 872     $default  accept
 873
 874
 875 State 12
 876
 877     4 A: 'a' 'a' . 'a'
 878     5  | 'a' 'a' .  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
 879
 880     ]AT_COND_CASE([[canonical LR]], [['a']],
 881                   [[$default]])[  reduce using rule 5 (A)
 882
 883     Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
 884
 885
 886 State 13
 887
 888     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 889
 890     ]AT_COND_CASE([[canonical LR]], [[$end]],
 891                   [[$default]])[  reduce using rule 1 (S)
 892
 893
 894 State 14
 895
 896     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 897
 898     ]AT_COND_CASE([[canonical LR]], [[$end]],
 899                   [[$default]])[  reduce using rule 2 (S)
 900
 901
 902 State 15
 903
 904     4 A: 'a' 'a' . 'a'
 905     5  | 'a' 'a' .  [$end]
 906     6 c: 'a' 'a' . 'b'
 907
 908     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]],
 909                                               [[16]])[
 910     'b'  shift, and go to state 17
 911
 912     ]AT_COND_CASE([[canonical LR]], [[$end]],
 913                   [[$default]])[  reduce using rule 5 (A)
 914
 915
 916 State 16
 917
 918     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
 919
 920     ]AT_COND_CASE([[canonical LR]], [['a']],
 921                   [[$default]])[  reduce using rule 4 (A)
 922
 923
 924 State 17
 925
 926     6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 927
 928     ]AT_COND_CASE([[canonical LR]], [[$end]],
 929                   [[$default]])[  reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
 930                                                                        [[]], [[
 931
 932
 933 State 18
 934
 935     4 A: 'a' . 'a' 'a'
 936     5  | 'a' . 'a'
 937
 938     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
 939                                               [[19]])[
 940
 941
 942 State 19]AT_COND_CASE([[canonical LR]], [[
 943
 944     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 945
 946     ]AT_COND_CASE([[canonical LR]], [[$end]],
 947                   [[$default]])[  reduce using rule 4 (A)
 948
 949
 950 State 20]])[
 951
 952     4 A: 'a' 'a' . 'a'
 953     5  | 'a' 'a' .  ['b']
 954
 955     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
 956                                               [[16]])[
 957
 958     ]AT_COND_CASE([[canonical LR]], [['b']],
 959                   [[$default]])[  reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
 960
 961
 962 State 21
 963
 964     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['b']]])[
 965
 966     ]AT_COND_CASE([[canonical LR]], [['b']],
 967                   [[$default]])[  reduce using rule 4 (A)]])])[
 968 ]],
 969
 970 dnl OTHER-CHECKS
 971 [],
 972
 973 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
 974 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
 975 [],
 976 [AT_COND_CASE([[LALR]],
 977 [[syntax error
 978 ]])])
 979
 980 AT_TEST_LR_TYPE([[Complex Lane Split]],
 981 [[%left 'a'
 982 // Conflict resolution renders state 16 unreachable for canonical LR(1).  We
 983 // keep it so that the parser table diff is easier to code.
 984 %define lr.keep-unreachable-state]],
 985 [[
 986 /* Similar to the last test case set but forseeing the S/R conflict from the
 987    first state that must be split is becoming difficult.  Imagine if B were
 988    even more complex.  Imagine if A had other RHS's ending in other
 989    nonterminals.  */
 990 S: 'a' A 'a'
 991  | 'b' A 'b'
 992  | 'c' c
 993  ;
 994 A: 'a' 'a' B
 995  ;
 996 B: 'a'
 997  | %empty %prec 'a'
 998  ;
 999 c: 'a' 'a' 'b'
1000  | A
1001  ;
1002 ]],
1003
1004 dnl INPUT
1005 [['b', 'a', 'a', 'a', 'b']],
1006
1007 dnl BISON-STDERR
1008 [],
1009
1010 dnl TABLES
1011 [[State 0
1012
1013     0 $accept: . S $end
1014     1 S: . 'a' A 'a'
1015     2  | . 'b' A 'b'
1016     3  | . 'c' c
1017
1018     'a'  shift, and go to state 1
1019     'b'  shift, and go to state 2
1020     'c'  shift, and go to state 3
1021
1022     S  go to state 4
1023
1024
1025 State 1
1026
1027     1 S: 'a' . A 'a'
1028     4 A: . 'a' 'a' B
1029
1030     'a'  shift, and go to state 5
1031
1032     A  go to state 6
1033
1034
1035 State 2
1036
1037     2 S: 'b' . A 'b'
1038     4 A: . 'a' 'a' B
1039
1040     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[
1041
1042     A  go to state 7
1043
1044
1045 State 3
1046
1047     3 S: 'c' . c
1048     4 A: . 'a' 'a' B
1049     7 c: . 'a' 'a' 'b'
1050     8  | . A
1051
1052     'a'  shift, and go to state 8
1053
1054     A  go to state 9
1055     c  go to state 10
1056
1057
1058 State 4
1059
1060     0 $accept: S . $end
1061
1062     $end  shift, and go to state 11
1063
1064
1065 State 5
1066
1067     4 A: 'a' . 'a' B
1068
1069     'a'  shift, and go to state 12
1070
1071
1072 State 6
1073
1074     1 S: 'a' A . 'a'
1075
1076     'a'  shift, and go to state 13
1077
1078
1079 State 7
1080
1081     2 S: 'b' A . 'b'
1082
1083     'b'  shift, and go to state 14
1084
1085
1086 State 8
1087
1088     4 A: 'a' . 'a' B
1089     7 c: 'a' . 'a' 'b'
1090
1091     'a'  shift, and go to state 15
1092
1093
1094 State 9
1095
1096     8 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1097
1098     ]AT_COND_CASE([[canonical LR]], [[$end]],
1099                   [[$default]])[  reduce using rule 8 (c)
1100
1101
1102 State 10
1103
1104     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1105
1106     ]AT_COND_CASE([[canonical LR]], [[$end]],
1107                   [[$default]])[  reduce using rule 3 (S)
1108
1109
1110 State 11
1111
1112     0 $accept: S $end .
1113
1114     $default  accept
1115
1116
1117 State 12
1118
1119     4 A: 'a' 'a' . B
1120     5 B: . 'a'
1121     6  | . %empty  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
1122
1123     ]AT_COND_CASE([[canonical LR]], [['a']],
1124                   [[$default]])[  reduce using rule 6 (B)
1125
1126     B  go to state 17
1127
1128     Conflict between rule 6 and token 'a' resolved as reduce (%left 'a').
1129
1130
1131 State 13
1132
1133     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1134
1135     ]AT_COND_CASE([[canonical LR]], [[$end]],
1136                   [[$default]])[  reduce using rule 1 (S)
1137
1138
1139 State 14
1140
1141     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1142
1143     ]AT_COND_CASE([[canonical LR]], [[$end]],
1144                   [[$default]])[  reduce using rule 2 (S)
1145
1146
1147 State 15
1148
1149     4 A: 'a' 'a' . B
1150     5 B: . 'a'
1151     6  | . %empty  [$end]
1152     7 c: 'a' 'a' . 'b'
1153
1154     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1155                                               [[16]])[
1156     'b'  shift, and go to state 18
1157
1158     ]AT_COND_CASE([[canonical LR]], [[$end]],
1159                   [[$default]])[  reduce using rule 6 (B)
1160
1161     B  go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[
1162
1163
1164 State 16
1165
1166     5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
1167
1168     ]AT_COND_CASE([[canonical LR]], [['a']],
1169                   [[$default]])[  reduce using rule 5 (B)
1170
1171
1172 State 17
1173
1174     4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
1175
1176     ]AT_COND_CASE([[canonical LR]], [['a']],
1177                   [[$default]])[  reduce using rule 4 (A)
1178
1179
1180 State 18
1181
1182     7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1183
1184     ]AT_COND_CASE([[canonical LR]], [[$end]],
1185                   [[$default]])[  reduce using rule 7 (c)]AT_COND_CASE([[LALR]], [], [[
1186
1187
1188 State 19
1189
1190     4 A: 'a' . 'a' B
1191
1192     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]],
1193                                               [[20]])[
1194
1195
1196 State 20]AT_COND_CASE([[canonical LR]], [[
1197
1198     5 B: 'a' .  [$end]
1199
1200     $end  reduce using rule 5 (B)
1201
1202
1203 State 21
1204
1205     4 A: 'a' 'a' B .  [$end]
1206
1207     $end  reduce using rule 4 (A)
1208
1209
1210 State 22]])[
1211
1212     4 A: 'a' 'a' . B
1213     5 B: . 'a'
1214     6  | . %empty  ['b']
1215
1216     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]],
1217                                               [[16]])[
1218
1219     ]AT_COND_CASE([[canonical LR]], [['b']],
1220                   [[$default]])[  reduce using rule 6 (B)
1221
1222     B  go to state ]AT_COND_CASE([[canonical LR]], [[24
1223
1224
1225 State 23
1226
1227     5 B: 'a' .  ['b']
1228
1229     'b'  reduce using rule 5 (B)
1230
1231
1232 State 24
1233
1234     4 A: 'a' 'a' B .  ['b']
1235
1236     'b'  reduce using rule 4 (A)]], [[17]])])[
1237 ]],
1238
1239 dnl OTHER-CHECKS
1240 [],
1241
1242 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1243 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1244 [],
1245 [AT_COND_CASE([[LALR]],
1246 [[syntax error
1247 ]])])
1248
1249 AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]],
1250 [[%define lr.keep-unreachable-state]],
1251 [[
1252 /* The partial state chart diagram below is for LALR(1).  State 0 is the start
1253    state.  States are iterated for successor construction in numerical order.
1254    Transitions are downwards.
1255
1256    State 13 has a R/R conflict that cannot be predicted by Bison's LR(1)
1257    algorithm using annotations alone.  That is, when state 11's successor on
1258    'd' is merged with state 5 (which is originally just state 1's successor on
1259    'd'), state 5's successor on 'e' must then be changed because the resulting
1260    lookaheads that propagate to it now make it incompatible with state 8's
1261    successor on 'e'.  In other words, state 13 must be split to avoid the
1262    conflict.
1263
1264           0
1265         / | \
1266      a / c|  \ b
1267       1   3   2
1268       |   |   |
1269      d|   |c  | d
1270       |  11   |
1271       |   |   |
1272        \ /d   |
1273         5     8
1274          \    |
1275         e \  / e
1276            13
1277            R/R
1278
1279    This grammar is designed carefully to make sure that, despite Bison's LR(1)
1280    algorithm's bread-first iteration of transitions to reconstruct states,
1281    state 11's successors are constructed after state 5's and state 8's.
1282    Otherwise (for example, if you remove the first 'c' in each of rules 6 and
1283    7), state 5's successor on 'e' would never be merged with state 8's, so the
1284    split of the resulting state 13 would never need to be performed.  */
1285 S: 'a' A 'f'
1286  | 'a' B
1287  | 'b' A 'f'
1288  | 'b' B 'g'
1289  | 'b' 'd'
1290  | 'c' 'c' A 'g'
1291  | 'c' 'c' B
1292  ;
1293 A: 'd' 'e' ;
1294 B: 'd' 'e' ;
1295 ]],
1296
1297 dnl INPUT
1298 [['b', 'd', 'e', 'g']],
1299
1300 dnl BISON-STDERR
1301 [AT_COND_CASE([[LALR]],
1302 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1303 input.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
1304 ]], [])],
1305
1306 dnl TABLES
1307 [[State 0
1308
1309     0 $accept: . S $end
1310     1 S: . 'a' A 'f'
1311     2  | . 'a' B
1312     3  | . 'b' A 'f'
1313     4  | . 'b' B 'g'
1314     5  | . 'b' 'd'
1315     6  | . 'c' 'c' A 'g'
1316     7  | . 'c' 'c' B
1317
1318     'a'  shift, and go to state 1
1319     'b'  shift, and go to state 2
1320     'c'  shift, and go to state 3
1321
1322     S  go to state 4
1323
1324
1325 State 1
1326
1327     1 S: 'a' . A 'f'
1328     2  | 'a' . B
1329     8 A: . 'd' 'e'
1330     9 B: . 'd' 'e'
1331
1332     'd'  shift, and go to state 5
1333
1334     A  go to state 6
1335     B  go to state 7
1336
1337
1338 State 2
1339
1340     3 S: 'b' . A 'f'
1341     4  | 'b' . B 'g'
1342     5  | 'b' . 'd'
1343     8 A: . 'd' 'e'
1344     9 B: . 'd' 'e'
1345
1346     'd'  shift, and go to state 8
1347
1348     A  go to state 9
1349     B  go to state 10
1350
1351
1352 State 3
1353
1354     6 S: 'c' . 'c' A 'g'
1355     7  | 'c' . 'c' B
1356
1357     'c'  shift, and go to state 11
1358
1359
1360 State 4
1361
1362     0 $accept: S . $end
1363
1364     $end  shift, and go to state 12
1365
1366
1367 State 5
1368
1369     8 A: 'd' . 'e'
1370     9 B: 'd' . 'e'
1371
1372     'e'  shift, and go to state ]AT_COND_CASE([[LALR]], [[13]],
1373                                                [[canonical LR]], [[13]],
1374                                                [[20]])[
1375
1376
1377 State 6
1378
1379     1 S: 'a' A . 'f'
1380
1381     'f'  shift, and go to state 14
1382
1383
1384 State 7
1385
1386     2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1387
1388     ]AT_COND_CASE([[canonical LR]], [[$end]],
1389                   [[$default]])[  reduce using rule 2 (S)
1390
1391
1392 State 8
1393
1394     5 S: 'b' 'd' .  [$end]
1395     8 A: 'd' . 'e'
1396     9 B: 'd' . 'e'
1397
1398     'e'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1399                                               [[13]])[
1400
1401     ]AT_COND_CASE([[canonical LR]], [[$end]],
1402                   [[$default]])[  reduce using rule 5 (S)
1403
1404
1405 State 9
1406
1407     3 S: 'b' A . 'f'
1408
1409     'f'  shift, and go to state 15
1410
1411
1412 State 10
1413
1414     4 S: 'b' B . 'g'
1415
1416     'g'  shift, and go to state 16
1417
1418
1419 State 11
1420
1421     6 S: 'c' 'c' . A 'g'
1422     7  | 'c' 'c' . B
1423     8 A: . 'd' 'e'
1424     9 B: . 'd' 'e'
1425
1426     'd'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1427                                               [[5]])[
1428
1429     A  go to state 17
1430     B  go to state 18
1431
1432
1433 State 12
1434
1435     0 $accept: S $end .
1436
1437     $default  accept]AT_COND_CASE([[LALR]], [[
1438
1439
1440 State 13
1441
1442     8 A: 'd' 'e' .  ['f', 'g']
1443     9 B: 'd' 'e' .  [$end, 'g']
1444
1445     $end      reduce using rule 9 (B)
1446     'g'       reduce using rule 8 (A)
1447     'g'       [reduce using rule 9 (B)]
1448     $default  reduce using rule 8 (A)]], [[
1449
1450
1451 State 13
1452
1453     8 A: 'd' 'e' .  ['f']
1454     9 B: 'd' 'e' .  ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[
1455
1456     ]AT_COND_CASE([[canonical LR]], [[$end]],
1457                   [['g'     ]])[  reduce using rule 9 (B)
1458     ]AT_COND_CASE([[canonical LR]], [['f' ]],
1459                   [[$default]])[  reduce using rule 8 (A)]])[
1460
1461
1462 State 14
1463
1464     1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1465
1466     ]AT_COND_CASE([[canonical LR]], [[$end]],
1467                   [[$default]])[  reduce using rule 1 (S)
1468
1469
1470 State 15
1471
1472     3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1473
1474     ]AT_COND_CASE([[canonical LR]], [[$end]],
1475                   [[$default]])[  reduce using rule 3 (S)
1476
1477
1478 State 16
1479
1480     4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1481
1482     ]AT_COND_CASE([[canonical LR]], [[$end]],
1483                   [[$default]])[  reduce using rule 4 (S)
1484
1485
1486 State 17
1487
1488     6 S: 'c' 'c' A . 'g'
1489
1490     'g'  shift, and go to state 19
1491
1492
1493 State 18
1494
1495     7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1496
1497     ]AT_COND_CASE([[canonical LR]], [[$end]],
1498                   [[$default]])[  reduce using rule 7 (S)
1499
1500
1501 State 19
1502
1503     6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1504
1505     ]AT_COND_CASE([[canonical LR]], [[$end]],
1506                   [[$default]])[  reduce using rule 6 (S)]AT_COND_CASE([[LALR]],
1507                                                                        [[]], [[
1508
1509
1510 State 20]AT_COND_CASE([[canonical LR]], [[
1511
1512     8 A: 'd' 'e' .  ['f']
1513     9 B: 'd' 'e' .  ['g']
1514
1515     'f'  reduce using rule 8 (A)
1516     'g'  reduce using rule 9 (B)
1517
1518
1519 State 21
1520
1521     8 A: 'd' . 'e'
1522     9 B: 'd' . 'e'
1523
1524     'e'  shift, and go to state 22
1525
1526
1527 State 22
1528
1529     8 A: 'd' 'e' .  ['g']
1530     9 B: 'd' 'e' .  [$end]
1531
1532     $end  reduce using rule 9 (B)
1533     'g'   reduce using rule 8 (A)]], [[
1534
1535     8 A: 'd' 'e' .  ['f', 'g']
1536     9 B: 'd' 'e' .  [$end]
1537
1538     $end      reduce using rule 9 (B)
1539     $default  reduce using rule 8 (A)]])])[
1540 ]],
1541
1542 dnl OTHER-CHECKS
1543 [],
1544
1545 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1546 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1547 [],
1548 [AT_COND_CASE([[LALR]],
1549 [[syntax error
1550 ]])])
1551
1552
1553
1554 ## ------------------------------ ##
1555 ## %define lr.default-reduction.  ##
1556 ## ------------------------------ ##
1557
1558 # AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES)
1559 # -----------------------------------------------------
1560 m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS],
1561 [
1562 AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reduction]],
1563                          [[most]], [[]],
1564                          [[]],
1565                          [$1], [$2], [[]], [$3])
1566 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction most]],
1567                          [[most]], [[]],
1568                          [[%define lr.default-reduction most]],
1569                          [$1], [$2], [[]], [$3])
1570 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction consistent]],
1571                          [[consistent]], [[]],
1572                          [[%define lr.default-reduction consistent]],
1573                          [$1], [$2], [[]], [$3])
1574 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction accepting]],
1575                          [[accepting]], [[]],
1576                          [[%define lr.default-reduction accepting]],
1577                          [$1], [$2], [[]], [$3])
1578 ])
1579
1580 AT_TEST_LR_DEFAULT_REDUCTIONS([[
1581 /* The start state is consistent and has a shift on 'a' and no reductions.
1582    After pushing the b below, enter an inconsistent state that has a shift and
1583    one reduction with one lookahead.  */
1584 start:
1585     a b
1586   | a b 'a'
1587   | a c 'b'
1588   ;
1589
1590 /* After shifting this 'a', enter a consistent state that has no shift and 1
1591    reduction with multiple lookaheads.  */
1592 a: 'a' ;
1593
1594 /* After the previous reduction, enter an inconsistent state that has no shift
1595    and multiple reductions.  The first reduction has more lookaheads than the
1596    second, so the first should always be preferred as the default reduction if
1597    enabled.  The second reduction has one lookahead.  */
1598 b: %empty;
1599 c: %empty;
1600 ]],
1601 dnl Visit each state mentioned above.
1602 [['a', 'a']],
1603 [[State 0
1604
1605     0 $accept: . start $end
1606     1 start: . a b
1607     2      | . a b 'a'
1608     3      | . a c 'b'
1609     4 a: . 'a'
1610
1611     'a'  shift, and go to state 1
1612
1613     start  go to state 2
1614     a      go to state 3
1615
1616
1617 State 1
1618
1619     4 a: 'a' .]AT_COND_CASE([[accepting]], [[  [$end, 'a', 'b']
1620
1621     $end  reduce using rule 4 (a)
1622     'a'   reduce using rule 4 (a)
1623     'b'   reduce using rule 4 (a)]], [[
1624
1625     $default  reduce using rule 4 (a)]])[
1626
1627
1628 State 2
1629
1630     0 $accept: start . $end
1631
1632     $end  shift, and go to state 4
1633
1634
1635 State 3
1636
1637     1 start: a . b
1638     2      | a . b 'a'
1639     3      | a . c 'b'
1640     5 b: . %empty  [$end, 'a']
1641     6 c: . %empty  ['b']]AT_COND_CASE([[most]], [[
1642
1643     'b'       reduce using rule 6 (c)
1644     $default  reduce using rule 5 (b)]], [[
1645
1646     $end  reduce using rule 5 (b)
1647     'a'   reduce using rule 5 (b)
1648     'b'   reduce using rule 6 (c)]])[
1649
1650     b  go to state 5
1651     c  go to state 6
1652
1653
1654 State 4
1655
1656     0 $accept: start $end .
1657
1658     $default  accept
1659
1660
1661 State 5
1662
1663     1 start: a b .  [$end]
1664     2      | a b . 'a'
1665
1666     'a'  shift, and go to state 7
1667
1668     ]AT_COND_CASE([[most]], [[$default]],
1669                   [[$end]])[  reduce using rule 1 (start)
1670
1671
1672 State 6
1673
1674     3 start: a c . 'b'
1675
1676     'b'  shift, and go to state 8
1677
1678
1679 State 7
1680
1681     2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[  [$end]
1682
1683     $end  reduce using rule 2 (start)]], [[
1684
1685     $default  reduce using rule 2 (start)]])[
1686
1687
1688 State 8
1689
1690     3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[  [$end]
1691
1692     $end  reduce using rule 3 (start)]], [[
1693
1694     $default  reduce using rule 3 (start)]])[
1695 ]])