tests/reduce.at

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