tests/reduce.at

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