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 18AT_BANNER([[Grammar Reduction.]]) 19 20 21## ------------------- ## 22## Useless Terminals. ## 23## ------------------- ## 24 25AT_SETUP([Useless Terminals]) 26 27AT_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%% 43exp: useful; 44]]) 45 46AT_BISON_CHECK([[input.y]]) 47 48AT_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 61AT_CLEANUP 62 63 64 65## ---------------------- ## 66## Useless Nonterminals. ## 67## ---------------------- ## 68 69AT_SETUP([Useless Nonterminals]) 70 71AT_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%% 87exp: useful; 88]]) 89 90AT_BISON_CHECK([[input.y]], 0, [], 91[[input.y: warning: 9 nonterminals useless in grammar 92input.y:4.8-15: warning: nonterminal useless in grammar: useless1 93input.y:5.8-15: warning: nonterminal useless in grammar: useless2 94input.y:6.8-15: warning: nonterminal useless in grammar: useless3 95input.y:7.8-15: warning: nonterminal useless in grammar: useless4 96input.y:8.8-15: warning: nonterminal useless in grammar: useless5 97input.y:9.8-15: warning: nonterminal useless in grammar: useless6 98input.y:10.8-15: warning: nonterminal useless in grammar: useless7 99input.y:11.8-15: warning: nonterminal useless in grammar: useless8 100input.y:12.8-15: warning: nonterminal useless in grammar: useless9 101]]) 102 103AT_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 116AT_CLEANUP 117 118 119 120## --------------- ## 121## Useless Rules. ## 122## --------------- ## 123 124AT_SETUP([Useless Rules]) 125 126AT_KEYWORDS([report]) 127 128AT_DATA([[input.y]], 129[[%verbose 130%output "input.c" 131%token useful 132%% 133exp: useful; 134useless1: '1'; 135useless2: '2'; 136useless3: '3'; 137useless4: '4'; 138useless5: '5'; 139useless6: '6'; 140useless7: '7'; 141useless8: '8'; 142useless9: '9'; 143]]) 144 145AT_BISON_CHECK([[-fcaret input.y]], 0, [], 146[[input.y: warning: 9 nonterminals useless in grammar 147input.y: warning: 9 rules useless in grammar 148input.y:6.1-8: warning: nonterminal useless in grammar: useless1 149 useless1: '1'; 150 ^^^^^^^^ 151input.y:7.1-8: warning: nonterminal useless in grammar: useless2 152 useless2: '2'; 153 ^^^^^^^^ 154input.y:8.1-8: warning: nonterminal useless in grammar: useless3 155 useless3: '3'; 156 ^^^^^^^^ 157input.y:9.1-8: warning: nonterminal useless in grammar: useless4 158 useless4: '4'; 159 ^^^^^^^^ 160input.y:10.1-8: warning: nonterminal useless in grammar: useless5 161 useless5: '5'; 162 ^^^^^^^^ 163input.y:11.1-8: warning: nonterminal useless in grammar: useless6 164 useless6: '6'; 165 ^^^^^^^^ 166input.y:12.1-8: warning: nonterminal useless in grammar: useless7 167 useless7: '7'; 168 ^^^^^^^^ 169input.y:13.1-8: warning: nonterminal useless in grammar: useless8 170 useless8: '8'; 171 ^^^^^^^^ 172input.y:14.1-8: warning: nonterminal useless in grammar: useless9 173 useless9: '9'; 174 ^^^^^^^^ 175input.y:6.11-13: warning: rule useless in grammar 176 useless1: '1'; 177 ^^^ 178input.y:7.11-13: warning: rule useless in grammar 179 useless2: '2'; 180 ^^^ 181input.y:8.11-13: warning: rule useless in grammar 182 useless3: '3'; 183 ^^^ 184input.y:9.11-13: warning: rule useless in grammar 185 useless4: '4'; 186 ^^^ 187input.y:10.11-13: warning: rule useless in grammar 188 useless5: '5'; 189 ^^^ 190input.y:11.11-13: warning: rule useless in grammar 191 useless6: '6'; 192 ^^^ 193input.y:12.11-13: warning: rule useless in grammar 194 useless7: '7'; 195 ^^^ 196input.y:13.11-13: warning: rule useless in grammar 197 useless8: '8'; 198 ^^^ 199input.y:14.11-13: warning: rule useless in grammar 200 useless9: '9'; 201 ^^^ 202]]) 203 204AT_BISON_CHECK([[input.y]], 0, [], 205[[input.y: warning: 9 nonterminals useless in grammar 206input.y: warning: 9 rules useless in grammar 207input.y:6.1-8: warning: nonterminal useless in grammar: useless1 208input.y:7.1-8: warning: nonterminal useless in grammar: useless2 209input.y:8.1-8: warning: nonterminal useless in grammar: useless3 210input.y:9.1-8: warning: nonterminal useless in grammar: useless4 211input.y:10.1-8: warning: nonterminal useless in grammar: useless5 212input.y:11.1-8: warning: nonterminal useless in grammar: useless6 213input.y:12.1-8: warning: nonterminal useless in grammar: useless7 214input.y:13.1-8: warning: nonterminal useless in grammar: useless8 215input.y:14.1-8: warning: nonterminal useless in grammar: useless9 216input.y:6.11-13: warning: rule useless in grammar: useless1: '1' 217input.y:7.11-13: warning: rule useless in grammar: useless2: '2' 218input.y:8.11-13: warning: rule useless in grammar: useless3: '3' 219input.y:9.11-13: warning: rule useless in grammar: useless4: '4' 220input.y:10.11-13: warning: rule useless in grammar: useless5: '5' 221input.y:11.11-13: warning: rule useless in grammar: useless6: '6' 222input.y:12.11-13: warning: rule useless in grammar: useless7: '7' 223input.y:13.11-13: warning: rule useless in grammar: useless8: '8' 224input.y:14.11-13: warning: rule useless in grammar: useless9: '9' 225]]) 226 227AT_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 238Terminals unused in grammar 239 '1' 240 '2' 241 '3' 242 '4' 243 '5' 244 '6' 245 '7' 246 '8' 247 '9' 248Rules 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 260AT_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 271AT_SETUP([Reduced Automaton]) 272 273AT_KEYWORDS([report]) 274 275# The non reduced grammar. 276# ------------------------ 277AT_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 287exp: useful { /* A useful action. */ } 288 | non_productive { /* A non productive action. */ } 289 ; 290 291not_reachable: useful { /* A not reachable action. */ } 292 ; 293 294non_productive: non_productive useless_token 295 { /* Another non productive action. */ } 296 ; 297%% 298]]) 299 300AT_BISON_CHECK([[-fcaret not-reduced.y]], 0, [], 301[[not-reduced.y: warning: 2 nonterminals useless in grammar 302not-reduced.y: warning: 3 rules useless in grammar 303not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable 304 not_reachable: useful { /* A not reachable action. */ } 305 ^^^^^^^^^^^^^ 306not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive 307 | non_productive { /* A non productive action. */ } 308 ^^^^^^^^^^^^^^ 309not-reduced.y:11.6-57: warning: rule useless in grammar 310 | non_productive { /* A non productive action. */ } 311 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 312not-reduced.y:14.16-56: warning: rule useless in grammar 313 not_reachable: useful { /* A not reachable action. */ } 314 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 315not-reduced.y:17.17-18.63: warning: rule useless in grammar 316 non_productive: non_productive useless_token 317 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 318]]) 319 320AT_BISON_CHECK([[not-reduced.y]], 0, [], 321[[not-reduced.y: warning: 2 nonterminals useless in grammar 322not-reduced.y: warning: 3 rules useless in grammar 323not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable 324not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive 325not-reduced.y:11.6-57: warning: rule useless in grammar: exp: non_productive 326not-reduced.y:14.16-56: warning: rule useless in grammar: not_reachable: useful 327not-reduced.y:17.17-18.63: warning: rule useless in grammar: non_productive: non_productive useless_token 328]]) 329 330AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0, 331[[Nonterminals useless in grammar 332 not_reachable 333 non_productive 334Terminals unused in grammar 335 useless_token 336Rules 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# -------------------- 344AT_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 354exp: 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 367AT_BISON_CHECK([[reduced.y]]) 368 369# Comparing the parsers. 370cp reduced.c expout 371AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout]) 372 373AT_CLEANUP 374 375 376 377## ------------------- ## 378## Underivable Rules. ## 379## ------------------- ## 380 381AT_SETUP([Underivable Rules]) 382 383AT_KEYWORDS([report]) 384 385AT_DATA([[input.y]], 386[[%verbose 387%output "input.c" 388%token useful 389%% 390exp: useful | underivable; 391underivable: indirection; 392indirection: underivable; 393]]) 394 395AT_BISON_CHECK([[input.y]], 0, [], 396[[input.y: warning: 2 nonterminals useless in grammar 397input.y: warning: 3 rules useless in grammar 398input.y:5.15-25: warning: nonterminal useless in grammar: underivable 399input.y:6.14-24: warning: nonterminal useless in grammar: indirection 400input.y:5.15-25: warning: rule useless in grammar: exp: underivable 401input.y:6.14-24: warning: rule useless in grammar: underivable: indirection 402input.y:7.14-24: warning: rule useless in grammar: indirection: underivable 403]]) 404 405AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, 406[[Nonterminals useless in grammar 407 underivable 408 indirection 409Rules useless in grammar 410 2 exp: underivable 411 3 underivable: indirection 412 4 indirection: underivable 413]]) 414 415AT_CLEANUP 416 417 418 419## ---------------- ## 420## Empty Language. ## 421## ---------------- ## 422 423AT_SETUP([Empty Language]) 424 425AT_DATA([[input.y]], 426[[%output "input.c" 427%% 428exp: exp; 429]]) 430 431AT_BISON_CHECK([[input.y]], 1, [], 432[[input.y: warning: 2 nonterminals useless in grammar 433input.y: warning: 2 rules useless in grammar 434input.y:3.1-3: fatal error: start symbol exp does not derive any sentence 435]]) 436 437AT_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# ------------------------------------------------- 452m4_define([AT_TEST_LR_TYPE], 453[ 454AT_TEST_TABLES_AND_PARSE([[no %define lr.type: ]$1], 455 [[LALR]], [[]], 456 [$2], m4_shiftn(2, $@)) 457AT_TEST_TABLES_AND_PARSE([[%define lr.type lalr: ]$1], 458 [[LALR]], [[]], 459 [[%define lr.type lalr 460]$2], 461 m4_shiftn(2, $@)) 462AT_TEST_TABLES_AND_PARSE([[%define lr.type ielr: ]$1], 463 [[IELR]], [[]], 464 [[%define lr.type ielr 465]$2], 466 m4_shiftn(2, $@)) 467AT_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 474AT_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-states]], 479[[ 480S: '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. */ 499A: '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. */ 507c: 'a' 'b' /* rule 6 */ 508 | A /* rule 7 */ 509 ; 510]], 511 512dnl INPUT 513[['b', 'a', 'a', 'b']], 514 515dnl BISON-STDERR 516[], 517 518dnl 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 533State 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 544State 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 555State 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 569State 4 570 571 0 $accept: S . $end 572 573 $end shift, and go to state 11 574 575 576State 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 587State 6 588 589 1 S: 'a' A . 'a' 590 591 'a' shift, and go to state 13 592 593 594State 7 595 596 2 S: 'b' A . 'b' 597 598 'b' shift, and go to state 14 599 600 601State 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 615State 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 623State 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 631State 11 632 633 0 $accept: S $end . 634 635 $default accept 636 637 638State 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 646State 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 654State 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 662State 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 671State 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 683State 17 684 685 4 A: 'a' 'a' . [$end] 686 687 $end reduce using rule 4 (A) 688 689 690State 18 691 692 4 A: 'a' 'a' . ['b'] 693 694 'b' reduce using rule 4 (A)]])])[ 695]], 696 697dnl OTHER-CHECKS 698[], 699 700dnl 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 707AT_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-states]], 712[[ 713/* Similar to the last test case set but two states must be split. */ 714S: 'a' A 'a' /* rule 1 */ 715 | 'b' A 'b' /* rule 2 */ 716 | 'c' c /* rule 3 */ 717 ; 718 719A: 'a' 'a' 'a' /* rule 4 */ 720 | 'a' 'a' /* rule 5 */ 721 ; 722 723c: 'a' 'a' 'b' /* rule 6 */ 724 | A /* rule 7 */ 725 ; 726]], 727 728dnl INPUT 729[['b', 'a', 'a', 'a', 'b']], 730 731dnl BISON-STDERR 732[], 733 734dnl 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 749State 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 760State 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 771State 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 785State 4 786 787 0 $accept: S . $end 788 789 $end shift, and go to state 11 790 791 792State 5 793 794 4 A: 'a' . 'a' 'a' 795 5 | 'a' . 'a' 796 797 'a' shift, and go to state 12 798 799 800State 6 801 802 1 S: 'a' A . 'a' 803 804 'a' shift, and go to state 13 805 806 807State 7 808 809 2 S: 'b' A . 'b' 810 811 'b' shift, and go to state 14 812 813 814State 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 823State 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 831State 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 839State 11 840 841 0 $accept: S $end . 842 843 $default accept 844 845 846State 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 857State 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 865State 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 873State 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 887State 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 895State 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 904State 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 913State 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 921State 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 933State 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 941dnl OTHER-CHECKS 942[], 943 944dnl 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 951AT_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-states]], 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. */ 961S: 'a' A 'a' 962 | 'b' A 'b' 963 | 'c' c 964 ; 965A: 'a' 'a' B 966 ; 967B: 'a' 968 | %prec 'a' 969 ; 970c: 'a' 'a' 'b' 971 | A 972 ; 973]], 974 975dnl INPUT 976[['b', 'a', 'a', 'a', 'b']], 977 978dnl BISON-STDERR 979[], 980 981dnl 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 996State 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 1006State 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 1016State 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 1029State 4 1030 1031 0 $accept: S . $end 1032 1033 $end shift, and go to state 11 1034 1035 1036State 5 1037 1038 4 A: 'a' . 'a' B 1039 1040 'a' shift, and go to state 12 1041 1042 1043State 6 1044 1045 1 S: 'a' A . 'a' 1046 1047 'a' shift, and go to state 13 1048 1049 1050State 7 1051 1052 2 S: 'b' A . 'b' 1053 1054 'b' shift, and go to state 14 1055 1056 1057State 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 1065State 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 1073State 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 1081State 11 1082 1083 0 $accept: S $end . 1084 1085 $default accept 1086 1087 1088State 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 1102State 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 1110State 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 1118State 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 1135State 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 1143State 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 1151State 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 1159State 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 1167State 20]AT_COND_CASE([[canonical LR]], [[ 1168 1169 5 B: 'a' . [$end] 1170 1171 $end reduce using rule 5 (B) 1172 1173 1174State 21 1175 1176 4 A: 'a' 'a' B . [$end] 1177 1178 $end reduce using rule 4 (A) 1179 1180 1181State 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 1196State 23 1197 1198 5 B: 'a' . ['b'] 1199 1200 'b' reduce using rule 5 (B) 1201 1202 1203State 24 1204 1205 4 A: 'a' 'a' B . ['b'] 1206 1207 'b' reduce using rule 4 (A)]], [[17]])])[ 1208]], 1209 1210dnl OTHER-CHECKS 1211[], 1212 1213dnl 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 1220AT_TEST_LR_TYPE([[Split During Added Lookahead Propagation]], 1221[[%define lr.keep-unreachable-states]], 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. */ 1256S: '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 ; 1264A: 'd' 'e' ; 1265B: 'd' 'e' ; 1266]], 1267 1268dnl INPUT 1269[['b', 'd', 'e', 'g']], 1270 1271dnl BISON-STDERR 1272[AT_COND_CASE([[LALR]], 1273[[input.y: conflicts: 1 reduce/reduce 1274]], [])], 1275 1276dnl 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 1295State 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 1308State 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 1322State 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 1330State 4 1331 1332 0 $accept: S . $end 1333 1334 $end shift, and go to state 12 1335 1336 1337State 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 1347State 6 1348 1349 1 S: 'a' A . 'f' 1350 1351 'f' shift, and go to state 14 1352 1353 1354State 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 1362State 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 1375State 9 1376 1377 3 S: 'b' A . 'f' 1378 1379 'f' shift, and go to state 15 1380 1381 1382State 10 1383 1384 4 S: 'b' B . 'g' 1385 1386 'g' shift, and go to state 16 1387 1388 1389State 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 1403State 12 1404 1405 0 $accept: S $end . 1406 1407 $default accept]AT_COND_CASE([[LALR]], [[ 1408 1409 1410State 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 1421State 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 1432State 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 1440State 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 1448State 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 1456State 17 1457 1458 6 S: 'c' 'c' A . 'g' 1459 1460 'g' shift, and go to state 19 1461 1462 1463State 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 1471State 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 1480State 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 1489State 21 1490 1491 8 A: 'd' . 'e' 1492 9 B: 'd' . 'e' 1493 1494 'e' shift, and go to state 22 1495 1496 1497State 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 1512dnl OTHER-CHECKS 1513[], 1514 1515dnl 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-reductions. ## 1526## ------------------------------- ## 1527 1528# AT_TEST_LR_DEFAULT_REDUCTIONS(GRAMMAR, INPUT, TABLES) 1529# ----------------------------------------------------- 1530m4_define([AT_TEST_LR_DEFAULT_REDUCTIONS], 1531[ 1532AT_TEST_TABLES_AND_PARSE([[no %define lr.default-reductions]], 1533 [[most]], [[]], 1534 [[]], 1535 [$1], [$2], [[]], [$3]) 1536AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions most]], 1537 [[most]], [[]], 1538 [[%define lr.default-reductions most]], 1539 [$1], [$2], [[]], [$3]) 1540AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions consistent]], 1541 [[consistent]], [[]], 1542 [[%define lr.default-reductions consistent]], 1543 [$1], [$2], [[]], [$3]) 1544AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions accepting]], 1545 [[accepting]], [[]], 1546 [[%define lr.default-reductions accepting]], 1547 [$1], [$2], [[]], [$3]) 1548]) 1549 1550AT_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. */ 1554start: 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. */ 1562a: '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. */ 1568b: ; 1569c: ; 1570]], 1571dnl 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 1587State 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 1598State 2 1599 1600 0 $accept: start . $end 1601 1602 $end shift, and go to state 4 1603 1604 1605State 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 1624State 4 1625 1626 0 $accept: start $end . 1627 1628 $default accept 1629 1630 1631State 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 1642State 6 1643 1644 3 start: a c . 'b' 1645 1646 'b' shift, and go to state 8 1647 1648 1649State 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 1658State 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]]) 1666