tests/reduce.at

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