tests/reduce.at

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