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 92 input.y:4.8-15: warning: nonterminal useless in grammar: useless1 93 input.y:5.8-15: warning: nonterminal useless in grammar: useless2 94 input.y:6.8-15: warning: nonterminal useless in grammar: useless3 95 input.y:7.8-15: warning: nonterminal useless in grammar: useless4 96 input.y:8.8-15: warning: nonterminal useless in grammar: useless5 97 input.y:9.8-15: warning: nonterminal useless in grammar: useless6 98 input.y:10.8-15: warning: nonterminal useless in grammar: useless7 99 input.y:11.8-15: warning: nonterminal useless in grammar: useless8 100 input.y:12.8-15: warning: nonterminal useless in grammar: useless9 101 ]]) 102 103 AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, 104 [[Nonterminals useless in grammar 105 useless1 106 useless2 107 useless3 108 useless4 109 useless5 110 useless6 111 useless7 112 useless8 113 useless9 114 ]]) 115 116 AT_CLEANUP 117 118 119 120 ## --------------- ## 121 ## Useless Rules. ## 122 ## --------------- ## 123 124 AT_SETUP([Useless Rules]) 125 126 AT_KEYWORDS([report]) 127 128 AT_DATA([[input.y]], 129 [[%verbose 130 %output "input.c" 131 %token useful 132 %% 133 exp: useful; 134 useless1: '1'; 135 useless2: '2'; 136 useless3: '3'; 137 useless4: '4'; 138 useless5: '5'; 139 useless6: '6'; 140 useless7: '7'; 141 useless8: '8'; 142 useless9: '9'; 143 ]]) 144 145 AT_BISON_CHECK([[-fcaret input.y]], 0, [], 146 [[input.y: warning: 9 nonterminals useless in grammar 147 input.y: warning: 9 rules useless in grammar 148 input.y:6.1-8: warning: nonterminal useless in grammar: useless1 149 useless1: '1'; 150 ^^^^^^^^ 151 input.y:7.1-8: warning: nonterminal useless in grammar: useless2 152 useless2: '2'; 153 ^^^^^^^^ 154 input.y:8.1-8: warning: nonterminal useless in grammar: useless3 155 useless3: '3'; 156 ^^^^^^^^ 157 input.y:9.1-8: warning: nonterminal useless in grammar: useless4 158 useless4: '4'; 159 ^^^^^^^^ 160 input.y:10.1-8: warning: nonterminal useless in grammar: useless5 161 useless5: '5'; 162 ^^^^^^^^ 163 input.y:11.1-8: warning: nonterminal useless in grammar: useless6 164 useless6: '6'; 165 ^^^^^^^^ 166 input.y:12.1-8: warning: nonterminal useless in grammar: useless7 167 useless7: '7'; 168 ^^^^^^^^ 169 input.y:13.1-8: warning: nonterminal useless in grammar: useless8 170 useless8: '8'; 171 ^^^^^^^^ 172 input.y:14.1-8: warning: nonterminal useless in grammar: useless9 173 useless9: '9'; 174 ^^^^^^^^ 175 input.y:6.11-13: warning: rule useless in grammar 176 useless1: '1'; 177 ^^^ 178 input.y:7.11-13: warning: rule useless in grammar 179 useless2: '2'; 180 ^^^ 181 input.y:8.11-13: warning: rule useless in grammar 182 useless3: '3'; 183 ^^^ 184 input.y:9.11-13: warning: rule useless in grammar 185 useless4: '4'; 186 ^^^ 187 input.y:10.11-13: warning: rule useless in grammar 188 useless5: '5'; 189 ^^^ 190 input.y:11.11-13: warning: rule useless in grammar 191 useless6: '6'; 192 ^^^ 193 input.y:12.11-13: warning: rule useless in grammar 194 useless7: '7'; 195 ^^^ 196 input.y:13.11-13: warning: rule useless in grammar 197 useless8: '8'; 198 ^^^ 199 input.y:14.11-13: warning: rule useless in grammar 200 useless9: '9'; 201 ^^^ 202 ]]) 203 204 AT_BISON_CHECK([[input.y]], 0, [], 205 [[input.y: warning: 9 nonterminals useless in grammar 206 input.y: warning: 9 rules useless in grammar 207 input.y:6.1-8: warning: nonterminal useless in grammar: useless1 208 input.y:7.1-8: warning: nonterminal useless in grammar: useless2 209 input.y:8.1-8: warning: nonterminal useless in grammar: useless3 210 input.y:9.1-8: warning: nonterminal useless in grammar: useless4 211 input.y:10.1-8: warning: nonterminal useless in grammar: useless5 212 input.y:11.1-8: warning: nonterminal useless in grammar: useless6 213 input.y:12.1-8: warning: nonterminal useless in grammar: useless7 214 input.y:13.1-8: warning: nonterminal useless in grammar: useless8 215 input.y:14.1-8: warning: nonterminal useless in grammar: useless9 216 input.y:6.11-13: warning: rule useless in grammar: useless1: '1' 217 input.y:7.11-13: warning: rule useless in grammar: useless2: '2' 218 input.y:8.11-13: warning: rule useless in grammar: useless3: '3' 219 input.y:9.11-13: warning: rule useless in grammar: useless4: '4' 220 input.y:10.11-13: warning: rule useless in grammar: useless5: '5' 221 input.y:11.11-13: warning: rule useless in grammar: useless6: '6' 222 input.y:12.11-13: warning: rule useless in grammar: useless7: '7' 223 input.y:13.11-13: warning: rule useless in grammar: useless8: '8' 224 input.y:14.11-13: warning: rule useless in grammar: useless9: '9' 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 302 not-reduced.y: warning: 3 rules useless in grammar 303 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable 304 not_reachable: useful { /* A not reachable action. */ } 305 ^^^^^^^^^^^^^ 306 not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive 307 | non_productive { /* A non productive action. */ } 308 ^^^^^^^^^^^^^^ 309 not-reduced.y:11.6-57: warning: rule useless in grammar 310 | non_productive { /* A non productive action. */ } 311 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 312 not-reduced.y:14.16-56: warning: rule useless in grammar 313 not_reachable: useful { /* A not reachable action. */ } 314 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 315 not-reduced.y:17.17-18.63: warning: rule useless in grammar 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 322 not-reduced.y: warning: 3 rules useless in grammar 323 not-reduced.y:14.1-13: warning: nonterminal useless in grammar: not_reachable 324 not-reduced.y:11.6-19: warning: nonterminal useless in grammar: non_productive 325 not-reduced.y:11.6-57: warning: rule useless in grammar: exp: non_productive 326 not-reduced.y:14.16-56: warning: rule useless in grammar: not_reachable: useful 327 not-reduced.y:17.17-18.63: warning: rule useless in grammar: non_productive: non_productive useless_token 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 397 input.y: warning: 3 rules useless in grammar 398 input.y:5.15-25: warning: nonterminal useless in grammar: underivable 399 input.y:6.14-24: warning: nonterminal useless in grammar: indirection 400 input.y:5.15-25: warning: rule useless in grammar: exp: underivable 401 input.y:6.14-24: warning: rule useless in grammar: underivable: indirection 402 input.y:7.14-24: warning: rule useless in grammar: indirection: underivable 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 433 input.y: warning: 2 rules useless in grammar 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-states]], 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-states]], 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-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. */ 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-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. */ 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: conflicts: 1 reduce/reduce 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-reductions. ## 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-reductions]], 1533 [[most]], [[]], 1534 [[]], 1535 [$1], [$2], [[]], [$3]) 1536 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions most]], 1537 [[most]], [[]], 1538 [[%define lr.default-reductions most]], 1539 [$1], [$2], [[]], [$3]) 1540 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions consistent]], 1541 [[consistent]], [[]], 1542 [[%define lr.default-reductions consistent]], 1543 [$1], [$2], [[]], [$3]) 1544 AT_TEST_TABLES_AND_PARSE([[%define lr.default-reductions accepting]], 1545 [[accepting]], [[]], 1546 [[%define lr.default-reductions 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 ]]) 1666
