tests/reduce.at

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