tests/reduce.at

   1 # Exercising Bison Grammar Reduction.                      -*- Autotest -*-
   2
   3 # Copyright (C) 2001-2002, 2007-2015, 2018-2021 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 <https://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 # https://lists.gnu.org/r/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 ## Bad start symbols.  ##
 450 ## ------------------- ##
 451
 452 AT_SETUP([Bad start symbols])
 453
 454 m4_pushdef([AT_TEST],
 455 [AT_BISON_OPTION_PUSHDEFS([$1])
 456 AT_DATA([[input.y]],
 457 [%%
 458 $1
 459 ])
 460
 461 AT_BISON_CHECK([[input.y]], 1, [],
 462 [$2
 463 ])
 464 AT_BISON_OPTION_POPDEFS([$1])
 465 ])
 466
 467 AT_TEST(
 468 [[exp: exp;]],
 469 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
 470 input.y: warning: 2 rules useless in grammar [-Wother]
 471 input.y:2.1-3: error: start symbol exp does not derive any sentence]])
 472
 473 AT_TEST(
 474 [[%start exp;
 475 exp: exp;]],
 476 [[input.y: warning: 2 nonterminals useless in grammar [-Wother]
 477 input.y: warning: 2 rules useless in grammar [-Wother]
 478 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
 479
 480 AT_TEST(
 481 [[%start exp stmt;
 482 exp: exp;
 483 stmt: "stmt"]],
 484 [[input.y: warning: 1 nonterminal useless in grammar [-Wother]
 485 input.y: warning: 2 rules useless in grammar [-Wother]
 486 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
 487
 488 AT_TEST(
 489 [[%start exp stmt;
 490 exp: exp;
 491 stmt: stmt]],
 492 [[input.y: warning: 3 nonterminals useless in grammar [-Wother]
 493 input.y: warning: 4 rules useless in grammar [-Wother]
 494 input.y:2.8-10: error: start symbol exp does not derive any sentence
 495 input.y:2.12-15: error: start symbol stmt does not derive any sentence]])
 496
 497 AT_TEST(
 498 [[%start exp;
 499 stmt: stmt]],
 500 [[input.y:2.8-10: warning: symbol 'exp' is used, but is not defined as a token and has no rules [-Wother]
 501 input.y: warning: 3 nonterminals useless in grammar [-Wother]
 502 input.y: warning: 2 rules useless in grammar [-Wother]
 503 input.y:2.8-10: error: start symbol exp does not derive any sentence]])
 504
 505 AT_TEST(
 506 [[%token FOO;
 507 %start FOO;
 508 stmt: FOO]],
 509 [[input.y:2.8-10: error: the start symbol FOO is a token]])
 510
 511 m4_popdef([AT_TEST])
 512
 513 AT_CLEANUP
 514
 515
 516
 517 ## ----------------- ##
 518 ## %define lr.type.  ##
 519 ## ----------------- ##
 520
 521 # AT_TEST_LR_TYPE(DESCRIPTION,
 522 #                 DECLS, GRAMMAR, INPUT,
 523 #                 BISON-STDERR, TABLES,
 524 #                 [OTHER-CHECKS],
 525 #                 [PARSER-EXIT-VALUE],
 526 #                 [PARSER-STDOUT], [PARSER-STDERR])
 527 # -------------------------------------------------
 528 m4_define([AT_TEST_LR_TYPE],
 529 [
 530 AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1],
 531                          [[LALR]], [[]],
 532                          [$2], m4_shiftn(2, $@))
 533 AT_TEST_TABLES_AND_PARSE([[%define lr.type lalr: ]$1],
 534                          [[LALR]], [[]],
 535                          [[%define lr.type lalr
 536 ]$2],
 537                          m4_shiftn(2, $@))
 538 AT_TEST_TABLES_AND_PARSE([[%define lr.type ielr: ]$1],
 539                          [[IELR]], [[]],
 540                          [[%define lr.type ielr
 541 ]$2],
 542                          m4_shiftn(2, $@))
 543 AT_TEST_TABLES_AND_PARSE([[%define lr.type canonical-lr: ]$1],
 544                          [[canonical LR]], [[]],
 545                          [[%define lr.type canonical-lr
 546 ]$2],
 547                          m4_shiftn(2, $@))
 548 ])
 549
 550 AT_TEST_LR_TYPE([[Single State Split]],
 551 [[%left 'a'
 552 // Conflict resolution renders state 12 unreachable for canonical LR(1).  We
 553 // keep it so that the parser table diff is easier to code.
 554 %define lr.keep-unreachable-state]],
 555 [[
 556 S: 'a' A 'a' /* rule 1 */
 557  | 'b' A 'b' /* rule 2 */
 558  | 'c' c     /* rule 3 */
 559  ;
 560
 561 /* A conflict should appear after the first 'a' in rules 4 and 5 but only after
 562    having shifted the first 'a' in rule 1.  However, when LALR(1) merging is
 563    chosen, the state containing that conflict is reused after having seen the
 564    first 'b' in rule 2 and then the first 'a' in rules 4 and 5.  In both cases,
 565    because of the merged state, if the next token is an 'a', the %left forces a
 566    reduction action with rule 5.  In the latter case, only a shift is actually
 567    grammatically correct.  Thus, the parser would report a syntax error for the
 568    grammatically correct sentence "baab" because it would encounter a syntax
 569    error after that incorrect reduction.
 570
 571    Despite not being LALR(1), Menhir version 20070322 suffers from this problem
 572    as well.  It uses David Pager's weak compatibility test for merging states.
 573    Bison and Menhir accept non-LR(1) grammars with conflict resolution.  Pager
 574    designed his algorithm only for LR(1) grammars.  */
 575 A: 'a' 'a' /* rule 4 */
 576  | 'a'     /* rule 5 */
 577  ;
 578
 579 /* Rule 3, rule 6, and rule 7 ensure that Bison does not report rule 4 as
 580    useless after conflict resolution.  This proves that, even though LALR(1)
 581    generates incorrect parser tables sometimes, Bison will not necessarily
 582    produce any warning to help the user realize it.  */
 583 c: 'a' 'b' /* rule 6 */
 584  | A       /* rule 7 */
 585  ;
 586 ]],
 587
 588 dnl INPUT
 589 [['b', 'a', 'a', 'b']],
 590
 591 dnl BISON-STDERR
 592 [],
 593
 594 dnl TABLES
 595 [[State 0
 596
 597     0 $accept: . S $end
 598     1 S: . 'a' A 'a'
 599     2  | . 'b' A 'b'
 600     3  | . 'c' c
 601
 602     'a'  shift, and go to state 1
 603     'b'  shift, and go to state 2
 604     'c'  shift, and go to state 3
 605
 606     S  go to state 4
 607
 608
 609 State 1
 610
 611     1 S: 'a' . A 'a'
 612     4 A: . 'a' 'a'
 613     5  | . 'a'
 614
 615     'a'  shift, and go to state 5
 616
 617     A  go to state 6
 618
 619
 620 State 2
 621
 622     2 S: 'b' . A 'b'
 623     4 A: . 'a' 'a'
 624     5  | . 'a'
 625
 626     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[16]])[
 627
 628     A  go to state 7
 629
 630
 631 State 3
 632
 633     3 S: 'c' . c
 634     4 A: . 'a' 'a'
 635     5  | . 'a'
 636     6 c: . 'a' 'b'
 637     7  | . A
 638
 639     'a'  shift, and go to state 8
 640
 641     A  go to state 9
 642     c  go to state 10
 643
 644
 645 State 4
 646
 647     0 $accept: S . $end
 648
 649     $end  shift, and go to state 11
 650
 651
 652 State 5
 653
 654     4 A: 'a' . 'a'
 655     5  | 'a' .  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
 656
 657     ]AT_COND_CASE([[canonical LR]], [['a']],
 658                   [[$default]])[  reduce using rule 5 (A)
 659
 660     Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
 661
 662
 663 State 6
 664
 665     1 S: 'a' A . 'a'
 666
 667     'a'  shift, and go to state 13
 668
 669
 670 State 7
 671
 672     2 S: 'b' A . 'b'
 673
 674     'b'  shift, and go to state 14
 675
 676
 677 State 8
 678
 679     4 A: 'a' . 'a'
 680     5  | 'a' .  [$end]
 681     6 c: 'a' . 'b'
 682
 683     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[17]],
 684                                               [[12]])[
 685     'b'  shift, and go to state 15
 686
 687     ]AT_COND_CASE([[canonical LR]], [[$end]],
 688                   [[$default]])[  reduce using rule 5 (A)
 689
 690
 691 State 9
 692
 693     7 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 694
 695     ]AT_COND_CASE([[canonical LR]], [[$end]],
 696                   [[$default]])[  reduce using rule 7 (c)
 697
 698
 699 State 10
 700
 701     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 702
 703     ]AT_COND_CASE([[canonical LR]], [[$end]],
 704                   [[$default]])[  reduce using rule 3 (S)
 705
 706
 707 State 11
 708
 709     0 $accept: S $end .
 710
 711     $default  accept
 712
 713
 714 State 12
 715
 716     4 A: 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
 717
 718     ]AT_COND_CASE([[canonical LR]], [['a']],
 719                   [[$default]])[  reduce using rule 4 (A)
 720
 721
 722 State 13
 723
 724     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 725
 726     ]AT_COND_CASE([[canonical LR]], [[$end]],
 727                   [[$default]])[  reduce using rule 1 (S)
 728
 729
 730 State 14
 731
 732     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 733
 734     ]AT_COND_CASE([[canonical LR]], [[$end]],
 735                   [[$default]])[  reduce using rule 2 (S)
 736
 737
 738 State 15
 739
 740     6 c: 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 741
 742     ]AT_COND_CASE([[canonical LR]], [[$end]],
 743                   [[$default]])[  reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
 744                                                                        [[]], [[
 745
 746
 747 State 16
 748
 749     4 A: 'a' . 'a'
 750     5  | 'a' .  ['b']
 751
 752     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[18]],
 753                                               [[12]])[
 754
 755     ]AT_COND_CASE([[canonical LR]], [['b']],
 756                   [[$default]])[  reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
 757
 758
 759 State 17
 760
 761     4 A: 'a' 'a' .  [$end]
 762
 763     $end  reduce using rule 4 (A)
 764
 765
 766 State 18
 767
 768     4 A: 'a' 'a' .  ['b']
 769
 770     'b'  reduce using rule 4 (A)]])])[
 771 ]],
 772
 773 dnl OTHER-CHECKS
 774 [],
 775
 776 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
 777 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
 778 [],
 779 [AT_COND_CASE([[LALR]],
 780 [[syntax error
 781 ]])])
 782
 783 AT_TEST_LR_TYPE([[Lane Split]],
 784 [[%left 'a'
 785 // Conflict resolution renders state 16 unreachable for canonical LR(1).  We
 786 // keep it so that the parser table diff is easier to code.
 787 %define lr.keep-unreachable-state]],
 788 [[
 789 /* Similar to the last test case set but two states must be split.  */
 790 S: 'a' A 'a' /* rule 1 */
 791  | 'b' A 'b' /* rule 2 */
 792  | 'c' c     /* rule 3 */
 793  ;
 794
 795 A: 'a' 'a' 'a' /* rule 4 */
 796  | 'a' 'a'     /* rule 5 */
 797  ;
 798
 799 c: 'a' 'a' 'b' /* rule 6 */
 800  | A           /* rule 7 */
 801  ;
 802 ]],
 803
 804 dnl INPUT
 805 [['b', 'a', 'a', 'a', 'b']],
 806
 807 dnl BISON-STDERR
 808 [],
 809
 810 dnl TABLES
 811 [[State 0
 812
 813     0 $accept: . S $end
 814     1 S: . 'a' A 'a'
 815     2  | . 'b' A 'b'
 816     3  | . 'c' c
 817
 818     'a'  shift, and go to state 1
 819     'b'  shift, and go to state 2
 820     'c'  shift, and go to state 3
 821
 822     S  go to state 4
 823
 824
 825 State 1
 826
 827     1 S: 'a' . A 'a'
 828     4 A: . 'a' 'a' 'a'
 829     5  | . 'a' 'a'
 830
 831     'a'  shift, and go to state 5
 832
 833     A  go to state 6
 834
 835
 836 State 2
 837
 838     2 S: 'b' . A 'b'
 839     4 A: . 'a' 'a' 'a'
 840     5  | . 'a' 'a'
 841
 842     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[18]])[
 843
 844     A  go to state 7
 845
 846
 847 State 3
 848
 849     3 S: 'c' . c
 850     4 A: . 'a' 'a' 'a'
 851     5  | . 'a' 'a'
 852     6 c: . 'a' 'a' 'b'
 853     7  | . A
 854
 855     'a'  shift, and go to state 8
 856
 857     A  go to state 9
 858     c  go to state 10
 859
 860
 861 State 4
 862
 863     0 $accept: S . $end
 864
 865     $end  shift, and go to state 11
 866
 867
 868 State 5
 869
 870     4 A: 'a' . 'a' 'a'
 871     5  | 'a' . 'a'
 872
 873     'a'  shift, and go to state 12
 874
 875
 876 State 6
 877
 878     1 S: 'a' A . 'a'
 879
 880     'a'  shift, and go to state 13
 881
 882
 883 State 7
 884
 885     2 S: 'b' A . 'b'
 886
 887     'b'  shift, and go to state 14
 888
 889
 890 State 8
 891
 892     4 A: 'a' . 'a' 'a'
 893     5  | 'a' . 'a'
 894     6 c: 'a' . 'a' 'b'
 895
 896     'a'  shift, and go to state 15
 897
 898
 899 State 9
 900
 901     7 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 902
 903     ]AT_COND_CASE([[canonical LR]], [[$end]],
 904                   [[$default]])[  reduce using rule 7 (c)
 905
 906
 907 State 10
 908
 909     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 910
 911     ]AT_COND_CASE([[canonical LR]], [[$end]],
 912                   [[$default]])[  reduce using rule 3 (S)
 913
 914
 915 State 11
 916
 917     0 $accept: S $end .
 918
 919     $default  accept
 920
 921
 922 State 12
 923
 924     4 A: 'a' 'a' . 'a'
 925     5  | 'a' 'a' .  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
 926
 927     ]AT_COND_CASE([[canonical LR]], [['a']],
 928                   [[$default]])[  reduce using rule 5 (A)
 929
 930     Conflict between rule 5 and token 'a' resolved as reduce (%left 'a').
 931
 932
 933 State 13
 934
 935     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 936
 937     ]AT_COND_CASE([[canonical LR]], [[$end]],
 938                   [[$default]])[  reduce using rule 1 (S)
 939
 940
 941 State 14
 942
 943     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 944
 945     ]AT_COND_CASE([[canonical LR]], [[$end]],
 946                   [[$default]])[  reduce using rule 2 (S)
 947
 948
 949 State 15
 950
 951     4 A: 'a' 'a' . 'a'
 952     5  | 'a' 'a' .  [$end]
 953     6 c: 'a' 'a' . 'b'
 954
 955     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[19]],
 956                                               [[16]])[
 957     'b'  shift, and go to state 17
 958
 959     ]AT_COND_CASE([[canonical LR]], [[$end]],
 960                   [[$default]])[  reduce using rule 5 (A)
 961
 962
 963 State 16
 964
 965     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
 966
 967     ]AT_COND_CASE([[canonical LR]], [['a']],
 968                   [[$default]])[  reduce using rule 4 (A)
 969
 970
 971 State 17
 972
 973     6 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 974
 975     ]AT_COND_CASE([[canonical LR]], [[$end]],
 976                   [[$default]])[  reduce using rule 6 (c)]AT_COND_CASE([[LALR]],
 977                                                                        [[]], [[
 978
 979
 980 State 18
 981
 982     4 A: 'a' . 'a' 'a'
 983     5  | 'a' . 'a'
 984
 985     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
 986                                               [[19]])[
 987
 988
 989 State 19]AT_COND_CASE([[canonical LR]], [[
 990
 991     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
 992
 993     ]AT_COND_CASE([[canonical LR]], [[$end]],
 994                   [[$default]])[  reduce using rule 4 (A)
 995
 996
 997 State 20]])[
 998
 999     4 A: 'a' 'a' . 'a'
1000     5  | 'a' 'a' .  ['b']
1001
1002     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1003                                               [[16]])[
1004
1005     ]AT_COND_CASE([[canonical LR]], [['b']],
1006                   [[$default]])[  reduce using rule 5 (A)]AT_COND_CASE([[canonical LR]], [[
1007
1008
1009 State 21
1010
1011     4 A: 'a' 'a' 'a' .]AT_COND_CASE([[canonical LR]], [[  ['b']]])[
1012
1013     ]AT_COND_CASE([[canonical LR]], [['b']],
1014                   [[$default]])[  reduce using rule 4 (A)]])])[
1015 ]],
1016
1017 dnl OTHER-CHECKS
1018 [],
1019
1020 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1021 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1022 [],
1023 [AT_COND_CASE([[LALR]],
1024 [[syntax error
1025 ]])])
1026
1027 AT_TEST_LR_TYPE([[Complex Lane Split]],
1028 [[%left 'a'
1029 // Conflict resolution renders state 16 unreachable for canonical LR(1).  We
1030 // keep it so that the parser table diff is easier to code.
1031 %define lr.keep-unreachable-state]],
1032 [[
1033 /* Similar to the last test case set but forseeing the S/R conflict from the
1034    first state that must be split is becoming difficult.  Imagine if B were
1035    even more complex.  Imagine if A had other RHS's ending in other
1036    nonterminals.  */
1037 S: 'a' A 'a'
1038  | 'b' A 'b'
1039  | 'c' c
1040  ;
1041 A: 'a' 'a' B
1042  ;
1043 B: 'a'
1044  | %empty %prec 'a'
1045  ;
1046 c: 'a' 'a' 'b'
1047  | A
1048  ;
1049 ]],
1050
1051 dnl INPUT
1052 [['b', 'a', 'a', 'a', 'b']],
1053
1054 dnl BISON-STDERR
1055 [],
1056
1057 dnl TABLES
1058 [[State 0
1059
1060     0 $accept: . S $end
1061     1 S: . 'a' A 'a'
1062     2  | . 'b' A 'b'
1063     3  | . 'c' c
1064
1065     'a'  shift, and go to state 1
1066     'b'  shift, and go to state 2
1067     'c'  shift, and go to state 3
1068
1069     S  go to state 4
1070
1071
1072 State 1
1073
1074     1 S: 'a' . A 'a'
1075     4 A: . 'a' 'a' B
1076
1077     'a'  shift, and go to state 5
1078
1079     A  go to state 6
1080
1081
1082 State 2
1083
1084     2 S: 'b' . A 'b'
1085     4 A: . 'a' 'a' B
1086
1087     'a'  shift, and go to state ]AT_COND_CASE([[LALR]], [[5]], [[19]])[
1088
1089     A  go to state 7
1090
1091
1092 State 3
1093
1094     3 S: 'c' . c
1095     4 A: . 'a' 'a' B
1096     7 c: . 'a' 'a' 'b'
1097     8  | . A
1098
1099     'a'  shift, and go to state 8
1100
1101     A  go to state 9
1102     c  go to state 10
1103
1104
1105 State 4
1106
1107     0 $accept: S . $end
1108
1109     $end  shift, and go to state 11
1110
1111
1112 State 5
1113
1114     4 A: 'a' . 'a' B
1115
1116     'a'  shift, and go to state 12
1117
1118
1119 State 6
1120
1121     1 S: 'a' A . 'a'
1122
1123     'a'  shift, and go to state 13
1124
1125
1126 State 7
1127
1128     2 S: 'b' A . 'b'
1129
1130     'b'  shift, and go to state 14
1131
1132
1133 State 8
1134
1135     4 A: 'a' . 'a' B
1136     7 c: 'a' . 'a' 'b'
1137
1138     'a'  shift, and go to state 15
1139
1140
1141 State 9
1142
1143     8 c: A .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1144
1145     ]AT_COND_CASE([[canonical LR]], [[$end]],
1146                   [[$default]])[  reduce using rule 8 (c)
1147
1148
1149 State 10
1150
1151     3 S: 'c' c .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1152
1153     ]AT_COND_CASE([[canonical LR]], [[$end]],
1154                   [[$default]])[  reduce using rule 3 (S)
1155
1156
1157 State 11
1158
1159     0 $accept: S $end .
1160
1161     $default  accept
1162
1163
1164 State 12
1165
1166     4 A: 'a' 'a' . B
1167     5 B: . 'a'
1168     6  | %empty .  ]AT_COND_CASE([[LALR]], [[['a', 'b']]], [[['a']]])[
1169
1170     ]AT_COND_CASE([[canonical LR]], [['a']],
1171                   [[$default]])[  reduce using rule 6 (B)
1172
1173     B  go to state 17
1174
1175     Conflict between rule 6 and token 'a' resolved as reduce (%left 'a').
1176
1177
1178 State 13
1179
1180     1 S: 'a' A 'a' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1181
1182     ]AT_COND_CASE([[canonical LR]], [[$end]],
1183                   [[$default]])[  reduce using rule 1 (S)
1184
1185
1186 State 14
1187
1188     2 S: 'b' A 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1189
1190     ]AT_COND_CASE([[canonical LR]], [[$end]],
1191                   [[$default]])[  reduce using rule 2 (S)
1192
1193
1194 State 15
1195
1196     4 A: 'a' 'a' . B
1197     5 B: . 'a'
1198     6  | %empty .  [$end]
1199     7 c: 'a' 'a' . 'b'
1200
1201     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1202                                               [[16]])[
1203     'b'  shift, and go to state 18
1204
1205     ]AT_COND_CASE([[canonical LR]], [[$end]],
1206                   [[$default]])[  reduce using rule 6 (B)
1207
1208     B  go to state ]AT_COND_CASE([[canonical LR]], [[21]], [[17]])[
1209
1210
1211 State 16
1212
1213     5 B: 'a' .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
1214
1215     ]AT_COND_CASE([[canonical LR]], [['a']],
1216                   [[$default]])[  reduce using rule 5 (B)
1217
1218
1219 State 17
1220
1221     4 A: 'a' 'a' B .]AT_COND_CASE([[canonical LR]], [[  ['a']]])[
1222
1223     ]AT_COND_CASE([[canonical LR]], [['a']],
1224                   [[$default]])[  reduce using rule 4 (A)
1225
1226
1227 State 18
1228
1229     7 c: 'a' 'a' 'b' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1230
1231     ]AT_COND_CASE([[canonical LR]], [[$end]],
1232                   [[$default]])[  reduce using rule 7 (c)]AT_COND_CASE([[LALR]], [], [[
1233
1234
1235 State 19
1236
1237     4 A: 'a' . 'a' B
1238
1239     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[22]],
1240                                               [[20]])[
1241
1242
1243 State 20]AT_COND_CASE([[canonical LR]], [[
1244
1245     5 B: 'a' .  [$end]
1246
1247     $end  reduce using rule 5 (B)
1248
1249
1250 State 21
1251
1252     4 A: 'a' 'a' B .  [$end]
1253
1254     $end  reduce using rule 4 (A)
1255
1256
1257 State 22]])[
1258
1259     4 A: 'a' 'a' . B
1260     5 B: . 'a'
1261     6  | %empty .  ['b']
1262
1263     'a'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[23]],
1264                                               [[16]])[
1265
1266     ]AT_COND_CASE([[canonical LR]], [['b']],
1267                   [[$default]])[  reduce using rule 6 (B)
1268
1269     B  go to state ]AT_COND_CASE([[canonical LR]], [[24
1270
1271
1272 State 23
1273
1274     5 B: 'a' .  ['b']
1275
1276     'b'  reduce using rule 5 (B)
1277
1278
1279 State 24
1280
1281     4 A: 'a' 'a' B .  ['b']
1282
1283     'b'  reduce using rule 4 (A)]], [[17]])])[
1284 ]],
1285
1286 dnl OTHER-CHECKS
1287 [],
1288
1289 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1290 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1291 [],
1292 [AT_COND_CASE([[LALR]],
1293 [[syntax error
1294 ]])])
1295
1296 AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]],
1297 [[%define lr.keep-unreachable-state]],
1298 [[
1299 /* The partial state chart diagram below is for LALR(1).  State 0 is the start
1300    state.  States are iterated for successor construction in numerical order.
1301    Transitions are downwards.
1302
1303    State 13 has a R/R conflict that cannot be predicted by Bison's LR(1)
1304    algorithm using annotations alone.  That is, when state 11's successor on
1305    'd' is merged with state 5 (which is originally just state 1's successor on
1306    'd'), state 5's successor on 'e' must then be changed because the resulting
1307    lookaheads that propagate to it now make it incompatible with state 8's
1308    successor on 'e'.  In other words, state 13 must be split to avoid the
1309    conflict.
1310
1311           0
1312         / | \
1313      a / c|  \ b
1314       1   3   2
1315       |   |   |
1316      d|   |c  | d
1317       |  11   |
1318       |   |   |
1319        \ /d   |
1320         5     8
1321          \    |
1322         e \  / e
1323            13
1324            R/R
1325
1326    This grammar is designed carefully to make sure that, despite Bison's LR(1)
1327    algorithm's bread-first iteration of transitions to reconstruct states,
1328    state 11's successors are constructed after state 5's and state 8's.
1329    Otherwise (for example, if you remove the first 'c' in each of rules 6 and
1330    7), state 5's successor on 'e' would never be merged with state 8's, so the
1331    split of the resulting state 13 would never need to be performed.  */
1332 S: 'a' A 'f'
1333  | 'a' B
1334  | 'b' A 'f'
1335  | 'b' B 'g'
1336  | 'b' 'd'
1337  | 'c' 'c' A 'g'
1338  | 'c' 'c' B
1339  ;
1340 A: 'd' 'e' ;
1341 B: 'd' 'e' ;
1342 ]],
1343
1344 dnl INPUT
1345 [['b', 'd', 'e', 'g']],
1346
1347 dnl BISON-STDERR
1348 [AT_COND_CASE([[LALR]],
1349 [[input.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
1350 input.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
1351 ]], [])],
1352
1353 dnl TABLES
1354 [[State 0
1355
1356     0 $accept: . S $end
1357     1 S: . 'a' A 'f'
1358     2  | . 'a' B
1359     3  | . 'b' A 'f'
1360     4  | . 'b' B 'g'
1361     5  | . 'b' 'd'
1362     6  | . 'c' 'c' A 'g'
1363     7  | . 'c' 'c' B
1364
1365     'a'  shift, and go to state 1
1366     'b'  shift, and go to state 2
1367     'c'  shift, and go to state 3
1368
1369     S  go to state 4
1370
1371
1372 State 1
1373
1374     1 S: 'a' . A 'f'
1375     2  | 'a' . B
1376     8 A: . 'd' 'e'
1377     9 B: . 'd' 'e'
1378
1379     'd'  shift, and go to state 5
1380
1381     A  go to state 6
1382     B  go to state 7
1383
1384
1385 State 2
1386
1387     3 S: 'b' . A 'f'
1388     4  | 'b' . B 'g'
1389     5  | 'b' . 'd'
1390     8 A: . 'd' 'e'
1391     9 B: . 'd' 'e'
1392
1393     'd'  shift, and go to state 8
1394
1395     A  go to state 9
1396     B  go to state 10
1397
1398
1399 State 3
1400
1401     6 S: 'c' . 'c' A 'g'
1402     7  | 'c' . 'c' B
1403
1404     'c'  shift, and go to state 11
1405
1406
1407 State 4
1408
1409     0 $accept: S . $end
1410
1411     $end  shift, and go to state 12
1412
1413
1414 State 5
1415
1416     8 A: 'd' . 'e'
1417     9 B: 'd' . 'e'
1418
1419     'e'  shift, and go to state ]AT_COND_CASE([[LALR]], [[13]],
1420                                                [[canonical LR]], [[13]],
1421                                                [[20]])[
1422
1423
1424 State 6
1425
1426     1 S: 'a' A . 'f'
1427
1428     'f'  shift, and go to state 14
1429
1430
1431 State 7
1432
1433     2 S: 'a' B .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1434
1435     ]AT_COND_CASE([[canonical LR]], [[$end]],
1436                   [[$default]])[  reduce using rule 2 (S)
1437
1438
1439 State 8
1440
1441     5 S: 'b' 'd' .  [$end]
1442     8 A: 'd' . 'e'
1443     9 B: 'd' . 'e'
1444
1445     'e'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[20]],
1446                                               [[13]])[
1447
1448     ]AT_COND_CASE([[canonical LR]], [[$end]],
1449                   [[$default]])[  reduce using rule 5 (S)
1450
1451
1452 State 9
1453
1454     3 S: 'b' A . 'f'
1455
1456     'f'  shift, and go to state 15
1457
1458
1459 State 10
1460
1461     4 S: 'b' B . 'g'
1462
1463     'g'  shift, and go to state 16
1464
1465
1466 State 11
1467
1468     6 S: 'c' 'c' . A 'g'
1469     7  | 'c' 'c' . B
1470     8 A: . 'd' 'e'
1471     9 B: . 'd' 'e'
1472
1473     'd'  shift, and go to state ]AT_COND_CASE([[canonical LR]], [[21]],
1474                                               [[5]])[
1475
1476     A  go to state 17
1477     B  go to state 18
1478
1479
1480 State 12
1481
1482     0 $accept: S $end .
1483
1484     $default  accept]AT_COND_CASE([[LALR]], [[
1485
1486
1487 State 13
1488
1489     8 A: 'd' 'e' .  ['f', 'g']
1490     9 B: 'd' 'e' .  [$end, 'g']
1491
1492     $end      reduce using rule 9 (B)
1493     'g'       reduce using rule 8 (A)
1494     'g'       [reduce using rule 9 (B)]
1495     $default  reduce using rule 8 (A)]], [[
1496
1497
1498 State 13
1499
1500     8 A: 'd' 'e' .  ['f']
1501     9 B: 'd' 'e' .  ]AT_COND_CASE([[canonical LR]], [[[$end]]], [[['g']]])[
1502
1503     ]AT_COND_CASE([[canonical LR]], [[$end]],
1504                   [['g'     ]])[  reduce using rule 9 (B)
1505     ]AT_COND_CASE([[canonical LR]], [['f' ]],
1506                   [[$default]])[  reduce using rule 8 (A)]])[
1507
1508
1509 State 14
1510
1511     1 S: 'a' A 'f' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1512
1513     ]AT_COND_CASE([[canonical LR]], [[$end]],
1514                   [[$default]])[  reduce using rule 1 (S)
1515
1516
1517 State 15
1518
1519     3 S: 'b' A 'f' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1520
1521     ]AT_COND_CASE([[canonical LR]], [[$end]],
1522                   [[$default]])[  reduce using rule 3 (S)
1523
1524
1525 State 16
1526
1527     4 S: 'b' B 'g' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1528
1529     ]AT_COND_CASE([[canonical LR]], [[$end]],
1530                   [[$default]])[  reduce using rule 4 (S)
1531
1532
1533 State 17
1534
1535     6 S: 'c' 'c' A . 'g'
1536
1537     'g'  shift, and go to state 19
1538
1539
1540 State 18
1541
1542     7 S: 'c' 'c' B .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1543
1544     ]AT_COND_CASE([[canonical LR]], [[$end]],
1545                   [[$default]])[  reduce using rule 7 (S)
1546
1547
1548 State 19
1549
1550     6 S: 'c' 'c' A 'g' .]AT_COND_CASE([[canonical LR]], [[  [$end]]])[
1551
1552     ]AT_COND_CASE([[canonical LR]], [[$end]],
1553                   [[$default]])[  reduce using rule 6 (S)]AT_COND_CASE([[LALR]],
1554                                                                        [[]], [[
1555
1556
1557 State 20]AT_COND_CASE([[canonical LR]], [[
1558
1559     8 A: 'd' 'e' .  ['f']
1560     9 B: 'd' 'e' .  ['g']
1561
1562     'f'  reduce using rule 8 (A)
1563     'g'  reduce using rule 9 (B)
1564
1565
1566 State 21
1567
1568     8 A: 'd' . 'e'
1569     9 B: 'd' . 'e'
1570
1571     'e'  shift, and go to state 22
1572
1573
1574 State 22
1575
1576     8 A: 'd' 'e' .  ['g']
1577     9 B: 'd' 'e' .  [$end]
1578
1579     $end  reduce using rule 9 (B)
1580     'g'   reduce using rule 8 (A)]], [[
1581
1582     8 A: 'd' 'e' .  ['f', 'g']
1583     9 B: 'd' 'e' .  [$end]
1584
1585     $end      reduce using rule 9 (B)
1586     $default  reduce using rule 8 (A)]])])[
1587 ]],
1588
1589 dnl OTHER-CHECKS
1590 [],
1591
1592 dnl PARSER-EXIT-VALUE, PARSER-STDOUT, PARSER-STDERR
1593 [AT_COND_CASE([[LALR]], [[1]], [[0]])],
1594 [],
1595 [AT_COND_CASE([[LALR]],
1596 [[syntax error
1597 ]])])
1598
1599
1600
1601 ## ------------------------------ ##
1602 ## %define lr.default-reduction.  ##
1603 ## ------------------------------ ##
1604
1605 # AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES)
1606 # -----------------------------------------------------
1607 m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS],
1608 [
1609 AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reduction]],
1610                          [[most]], [[]],
1611                          [[]],
1612                          [$1], [$2], [[]], [$3])
1613 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction most]],
1614                          [[most]], [[]],
1615                          [[%define lr.default-reduction most]],
1616                          [$1], [$2], [[]], [$3])
1617 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction consistent]],
1618                          [[consistent]], [[]],
1619                          [[%define lr.default-reduction consistent]],
1620                          [$1], [$2], [[]], [$3])
1621 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reduction accepting]],
1622                          [[accepting]], [[]],
1623                          [[%define lr.default-reduction accepting]],
1624                          [$1], [$2], [[]], [$3])
1625 ])
1626
1627 AT_TEST_LR_DEFAULT_REDUCTIONS([[
1628 /* The start state is consistent and has a shift on 'a' and no reductions.
1629    After pushing the b below, enter an inconsistent state that has a shift and
1630    one reduction with one lookahead.  */
1631 start:
1632     a b
1633   | a b 'a'
1634   | a c 'b'
1635   ;
1636
1637 /* After shifting this 'a', enter a consistent state that has no shift and 1
1638    reduction with multiple lookaheads.  */
1639 a: 'a' ;
1640
1641 /* After the previous reduction, enter an inconsistent state that has no shift
1642    and multiple reductions.  The first reduction has more lookaheads than the
1643    second, so the first should always be preferred as the default reduction if
1644    enabled.  The second reduction has one lookahead.  */
1645 b: %empty;
1646 c: %empty;
1647 ]],
1648 dnl Visit each state mentioned above.
1649 [['a', 'a']],
1650 [[State 0
1651
1652     0 $accept: . start $end
1653     1 start: . a b
1654     2      | . a b 'a'
1655     3      | . a c 'b'
1656     4 a: . 'a'
1657
1658     'a'  shift, and go to state 1
1659
1660     start  go to state 2
1661     a      go to state 3
1662
1663
1664 State 1
1665
1666     4 a: 'a' .]AT_COND_CASE([[accepting]], [[  [$end, 'a', 'b']
1667
1668     $end  reduce using rule 4 (a)
1669     'a'   reduce using rule 4 (a)
1670     'b'   reduce using rule 4 (a)]], [[
1671
1672     $default  reduce using rule 4 (a)]])[
1673
1674
1675 State 2
1676
1677     0 $accept: start . $end
1678
1679     $end  shift, and go to state 4
1680
1681
1682 State 3
1683
1684     1 start: a . b
1685     2      | a . b 'a'
1686     3      | a . c 'b'
1687     5 b: %empty .  [$end, 'a']
1688     6 c: %empty .  ['b']]AT_COND_CASE([[most]], [[
1689
1690     'b'       reduce using rule 6 (c)
1691     $default  reduce using rule 5 (b)]], [[
1692
1693     $end  reduce using rule 5 (b)
1694     'a'   reduce using rule 5 (b)
1695     'b'   reduce using rule 6 (c)]])[
1696
1697     b  go to state 5
1698     c  go to state 6
1699
1700
1701 State 4
1702
1703     0 $accept: start $end .
1704
1705     $default  accept
1706
1707
1708 State 5
1709
1710     1 start: a b .  [$end]
1711     2      | a b . 'a'
1712
1713     'a'  shift, and go to state 7
1714
1715     ]AT_COND_CASE([[most]], [[$default]],
1716                   [[$end]])[  reduce using rule 1 (start)
1717
1718
1719 State 6
1720
1721     3 start: a c . 'b'
1722
1723     'b'  shift, and go to state 8
1724
1725
1726 State 7
1727
1728     2 start: a b 'a' .]AT_COND_CASE([[accepting]], [[  [$end]
1729
1730     $end  reduce using rule 2 (start)]], [[
1731
1732     $default  reduce using rule 2 (start)]])[
1733
1734
1735 State 8
1736
1737     3 start: a c 'b' .]AT_COND_CASE([[accepting]], [[  [$end]
1738
1739     $end  reduce using rule 3 (start)]], [[
1740
1741     $default  reduce using rule 3 (start)]])[
1742 ]])