1# Exercising Bison on conflicts. -*- Autotest -*- 2 3# Copyright (C) 2002-2005, 2007, 2009-2012 Free Software Foundation, 4# Inc. 5 6# This program is free software: you can redistribute it and/or modify 7# it under the terms of the GNU General Public License as published by 8# the Free Software Foundation, either version 3 of the License, or 9# (at your option) any later version. 10# 11# This program is distributed in the hope that it will be useful, 12# but WITHOUT ANY WARRANTY; without even the implied warranty of 13# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14# GNU General Public License for more details. 15# 16# You should have received a copy of the GNU General Public License 17# along with this program. If not, see <http://www.gnu.org/licenses/>. 18 19AT_BANNER([[Conflicts.]]) 20 21 22## ---------------- ## 23## S/R in initial. ## 24## ---------------- ## 25 26# I once hacked Bison in such a way that it lost its reductions on the 27# initial state (because it was confusing it with the last state). It 28# took me a while to strip down my failures to this simple case. So 29# make sure it finds the s/r conflict below. 30 31AT_SETUP([S/R in initial]) 32 33AT_DATA([[input.y]], 34[[%expect 1 35%% 36exp: e 'e'; 37e: 'e' | /* Nothing. */; 38]]) 39 40AT_BISON_CHECK([-o input.c input.y], 0, [], 41[[input.y:4.9: warning: rule useless in parser due to conflicts: e: /* empty */ 42]]) 43 44AT_BISON_CHECK([-fcaret -o input.c input.y], 0, [], 45[[input.y:4.9: warning: rule useless in parser due to conflicts 46 e: 'e' | /* Nothing. */; 47 ^ 48]]) 49 50AT_CLEANUP 51 52 53## ------------------- ## 54## %nonassoc and eof. ## 55## ------------------- ## 56 57AT_SETUP([%nonassoc and eof]) 58 59AT_BISON_OPTION_PUSHDEFS 60AT_DATA_GRAMMAR([input.y], 61[[ 62%{ 63#include <stdio.h> 64#include <stdlib.h> 65#include <string.h> 66#include <assert.h> 67 68#define YYERROR_VERBOSE 1 69]AT_YYERROR_DEFINE[ 70/* The current argument. */ 71static const char *input; 72 73static int 74yylex (void) 75{ 76 static size_t toknum; 77 assert (toknum <= strlen (input)); 78 return input[toknum++]; 79} 80 81%} 82 83%nonassoc '<' '>' 84 85%% 86expr: expr '<' expr 87 | expr '>' expr 88 | '0' 89 ; 90%% 91int 92main (int argc, const char *argv[]) 93{ 94 input = argc <= 1 ? "" : argv[1]; 95 return yyparse (); 96} 97]]) 98AT_BISON_OPTION_POPDEFS 99 100m4_pushdef([AT_NONASSOC_AND_EOF_CHECK], 101[AT_BISON_CHECK([$1[ -o input.c input.y]]) 102AT_COMPILE([input]) 103 104m4_pushdef([AT_EXPECTING], [m4_if($2, [correct], [[, expecting $end]])]) 105 106AT_PARSER_CHECK([./input '0<0']) 107AT_PARSER_CHECK([./input '0<0<0'], [1], [], 108 [syntax error, unexpected '<'AT_EXPECTING 109]) 110 111AT_PARSER_CHECK([./input '0>0']) 112AT_PARSER_CHECK([./input '0>0>0'], [1], [], 113 [syntax error, unexpected '>'AT_EXPECTING 114]) 115 116AT_PARSER_CHECK([./input '0<0>0'], [1], [], 117 [syntax error, unexpected '>'AT_EXPECTING 118]) 119 120m4_popdef([AT_EXPECTING])]) 121 122# Expected token list is missing. 123AT_NONASSOC_AND_EOF_CHECK([], [[incorrect]]) 124 125# We must disable default reductions in inconsistent states in order to 126# have an explicit list of all expected tokens. 127AT_NONASSOC_AND_EOF_CHECK([[-Dlr.default-reductions=consistent]], 128 [[correct]]) 129 130# lr.default-reductions=consistent happens to work for this test case. 131# However, for other grammars, lookahead sets can be merged for 132# different left contexts, so it is still possible to have an incorrect 133# expected list. Canonical LR is almost a general solution (that is, it 134# can fail only when %nonassoc is used), so make sure it gives the same 135# result as above. 136AT_NONASSOC_AND_EOF_CHECK([[-Dlr.type=canonical-lr]], [[correct]]) 137 138# parse.lac=full is a completely general solution that does not require 139# any of the above sacrifices. Of course, it does not extend the 140# language-recognition power of LALR to (IE)LR, but it does ensure that 141# the reported list of expected tokens matches what the given parser 142# would have accepted in place of the unexpected token. 143AT_NONASSOC_AND_EOF_CHECK([[-Dparse.lac=full]], [[correct]]) 144 145m4_popdef([AT_NONASSOC_AND_EOF_CHECK]) 146 147AT_CLEANUP 148 149 150 151## -------------------------------------- ## 152## %error-verbose and consistent errors. ## 153## -------------------------------------- ## 154 155AT_SETUP([[%error-verbose and consistent errors]]) 156 157m4_pushdef([AT_CONSISTENT_ERRORS_CHECK], [ 158 159AT_BISON_OPTION_PUSHDEFS([$1]) 160 161m4_pushdef([AT_YYLEX_PROTOTYPE], 162[AT_SKEL_CC_IF([[int yylex (yy::parser::semantic_type *lvalp)]], 163 [[int yylex (YYSTYPE *lvalp)]])]) 164 165AT_SKEL_JAVA_IF([AT_DATA], [AT_DATA_GRAMMAR])([input.y], 166[AT_SKEL_JAVA_IF([[ 167 168%code imports { 169 import java.io.IOException; 170}]], [[ 171 172%code {]AT_SKEL_CC_IF([[ 173 #include <cassert> 174 #include <string>]], [[ 175 #include <assert.h> 176 #include <stdio.h> 177 ]AT_YYERROR_DECLARE])[ 178 ]AT_YYLEX_PROTOTYPE[; 179 #define USE(Var) 180} 181 182]AT_SKEL_CC_IF([[%defines]], [[%define api.pure]])])[ 183 184]$1[ 185 186%error-verbose 187 188%% 189 190]$2[ 191 192]AT_SKEL_JAVA_IF([[%code lexer {]], [[%%]])[ 193 194/*--------. 195| yylex. | 196`--------*/]AT_SKEL_JAVA_IF([[ 197 198public String input = "]$3["; 199public int index = 0; 200public int yylex () 201{ 202 if (index < input.length ()) 203 return input.charAt (index++); 204 else 205 return 0; 206} 207public Object getLVal () 208{ 209 return new Integer(1); 210}]], [[ 211 212]AT_YYLEX_PROTOTYPE[ 213{ 214 static char const *input = "]$3["; 215 *lvalp = 1; 216 return *input++; 217}]])[ 218]AT_YYERROR_DEFINE[ 219]AT_SKEL_JAVA_IF([[ 220}; 221 222%%]])[ 223 224/*-------. 225| main. | 226`-------*/]AT_SKEL_JAVA_IF([[ 227 228class input 229{ 230 public static void main (String args[]) throws IOException 231 { 232 YYParser p = new YYParser (); 233 p.parse (); 234 } 235}]], [AT_SKEL_CC_IF([[ 236 237int 238main (void) 239{ 240 yy::parser parser; 241 return parser.parse (); 242}]], [[ 243 244int 245main (void) 246{ 247 return yyparse (); 248}]])])[ 249]]) 250 251AT_FULL_COMPILE([[input]]) 252 253m4_pushdef([AT_EXPECTING], [m4_if($5, [ab], [[, expecting 'a' or 'b']], 254 $5, [a], [[, expecting 'a']], 255 $5, [b], [[, expecting 'b']])]) 256 257AT_SKEL_JAVA_IF([AT_JAVA_PARSER_CHECK([[input]], [[0]]], 258 [AT_PARSER_CHECK([[./input]], [[1]]]), 259[[]], 260[[syntax error, unexpected ]$4[]AT_EXPECTING[ 261]]) 262 263m4_popdef([AT_EXPECTING]) 264m4_popdef([AT_YYLEX_PROTOTYPE]) 265AT_BISON_OPTION_POPDEFS 266 267]) 268 269m4_pushdef([AT_PREVIOUS_STATE_GRAMMAR], 270[[%nonassoc 'a'; 271 272start: consistent-error-on-a-a 'a' ; 273 274consistent-error-on-a-a: 275 'a' default-reduction 276 | 'a' default-reduction 'a' 277 | 'a' shift 278 ; 279 280default-reduction: /*empty*/ ; 281shift: 'b' ; 282 283// Provide another context in which all rules are useful so that this 284// test case looks a little more realistic. 285start: 'b' consistent-error-on-a-a 'c' ; 286]]) 287 288m4_pushdef([AT_PREVIOUS_STATE_INPUT], [[a]]) 289 290# Unfortunately, no expected tokens are reported even though 'b' can be 291# accepted. Nevertheless, the main point of this test is to make sure 292# that at least the unexpected token is reported. In a previous version 293# of Bison, it wasn't reported because the error is detected in a 294# consistent state with an error action, and that case always triggered 295# the simple "syntax error" message. 296# 297# The point isn't to test IELR here, but state merging happens to 298# complicate this example. 299AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr]], 300 [AT_PREVIOUS_STATE_GRAMMAR], 301 [AT_PREVIOUS_STATE_INPUT], 302 [[$end]], [[none]]) 303AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 304 %glr-parser]], 305 [AT_PREVIOUS_STATE_GRAMMAR], 306 [AT_PREVIOUS_STATE_INPUT], 307 [[$end]], [[none]]) 308AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 309 %language "c++"]], 310 [AT_PREVIOUS_STATE_GRAMMAR], 311 [AT_PREVIOUS_STATE_INPUT], 312 [[$end]], [[none]]) 313AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 314 %language "java"]], 315 [AT_PREVIOUS_STATE_GRAMMAR], 316 [AT_PREVIOUS_STATE_INPUT], 317 [[end of input]], [[none]]) 318 319# Even canonical LR doesn't foresee the error for 'a'! 320AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 321 %define lr.default-reductions consistent]], 322 [AT_PREVIOUS_STATE_GRAMMAR], 323 [AT_PREVIOUS_STATE_INPUT], 324 [[$end]], [[ab]]) 325AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 326 %define lr.default-reductions accepting]], 327 [AT_PREVIOUS_STATE_GRAMMAR], 328 [AT_PREVIOUS_STATE_INPUT], 329 [[$end]], [[ab]]) 330AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]], 331 [AT_PREVIOUS_STATE_GRAMMAR], 332 [AT_PREVIOUS_STATE_INPUT], 333 [[$end]], [[ab]]) 334 335# Only LAC gets it right. 336AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr 337 %define parse.lac full]], 338 [AT_PREVIOUS_STATE_GRAMMAR], 339 [AT_PREVIOUS_STATE_INPUT], 340 [[$end]], [[b]]) 341AT_CONSISTENT_ERRORS_CHECK([[%define lr.type ielr 342 %define parse.lac full]], 343 [AT_PREVIOUS_STATE_GRAMMAR], 344 [AT_PREVIOUS_STATE_INPUT], 345 [[$end]], [[b]]) 346 347m4_popdef([AT_PREVIOUS_STATE_GRAMMAR]) 348m4_popdef([AT_PREVIOUS_STATE_INPUT]) 349 350m4_pushdef([AT_USER_ACTION_GRAMMAR], 351[[%nonassoc 'a'; 352 353// If $$ = 0 here, then we know that the 'a' destructor is being invoked 354// incorrectly for the 'b' set in the semantic action below. All 'a' 355// tokens are returned by yylex, which sets $$ = 1. 356%destructor { 357 if (!$$) 358 fprintf (stderr, "Wrong destructor.\n"); 359} 'a'; 360 361// Rather than depend on an inconsistent state to induce reading a 362// lookahead as in the previous grammar, just assign the lookahead in a 363// semantic action. That lookahead isn't needed before either error 364// action is encountered. In a previous version of Bison, this was a 365// problem as it meant yychar was not translated into yytoken before 366// either error action. The second error action thus invoked a 367// destructor that it selected according to the incorrect yytoken. The 368// first error action would have reported an incorrect unexpected token 369// except that, due to the bug described in the previous grammar, the 370// unexpected token was not reported at all. 371start: error-reduce consistent-error 'a' { USE ($][3); } ; 372 373error-reduce: 374 'a' 'a' consistent-reduction consistent-error 'a' 375 { USE (($][1, $][2, $][5)); } 376| 'a' error 377 { USE ($][1); } 378; 379 380consistent-reduction: /*empty*/ { 381 assert (yychar == ]AT_SKEL_CC_IF([[yyempty_]], [[YYEMPTY]])[); 382 yylval = 0; 383 yychar = 'b'; 384} ; 385 386consistent-error: 387 'a' { USE ($][1); } 388| /*empty*/ %prec 'a' 389; 390 391// Provide another context in which all rules are useful so that this 392// test case looks a little more realistic. 393start: 'b' consistent-error 'b' ; 394]]) 395m4_pushdef([AT_USER_ACTION_INPUT], [[aa]]) 396 397AT_CONSISTENT_ERRORS_CHECK([[]], 398 [AT_USER_ACTION_GRAMMAR], 399 [AT_USER_ACTION_INPUT], 400 [['b']], [[none]]) 401AT_CONSISTENT_ERRORS_CHECK([[%glr-parser]], 402 [AT_USER_ACTION_GRAMMAR], 403 [AT_USER_ACTION_INPUT], 404 [['b']], [[none]]) 405AT_CONSISTENT_ERRORS_CHECK([[%language "c++"]], 406 [AT_USER_ACTION_GRAMMAR], 407 [AT_USER_ACTION_INPUT], 408 [['b']], [[none]]) 409# No Java test because yychar cannot be manipulated by users. 410 411AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reductions consistent]], 412 [AT_USER_ACTION_GRAMMAR], 413 [AT_USER_ACTION_INPUT], 414 [['b']], [[none]]) 415 416# Canonical LR doesn't foresee the error for 'a'! 417AT_CONSISTENT_ERRORS_CHECK([[%define lr.default-reductions accepting]], 418 [AT_USER_ACTION_GRAMMAR], 419 [AT_USER_ACTION_INPUT], 420 [[$end]], [[a]]) 421AT_CONSISTENT_ERRORS_CHECK([[%define lr.type canonical-lr]], 422 [AT_USER_ACTION_GRAMMAR], 423 [AT_USER_ACTION_INPUT], 424 [[$end]], [[a]]) 425 426AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full]], 427 [AT_USER_ACTION_GRAMMAR], 428 [AT_USER_ACTION_INPUT], 429 [['b']], [[none]]) 430AT_CONSISTENT_ERRORS_CHECK([[%define parse.lac full 431 %define lr.default-reductions accepting]], 432 [AT_USER_ACTION_GRAMMAR], 433 [AT_USER_ACTION_INPUT], 434 [[$end]], [[none]]) 435 436m4_popdef([AT_USER_ACTION_GRAMMAR]) 437m4_popdef([AT_USER_ACTION_INPUT]) 438 439m4_popdef([AT_CONSISTENT_ERRORS_CHECK]) 440 441AT_CLEANUP 442 443 444 445## ------------------------------------------------------- ## 446## LAC: %nonassoc requires splitting canonical LR states. ## 447## ------------------------------------------------------- ## 448 449# This test case demonstrates that, when %nonassoc is used, canonical 450# LR(1) parser table construction followed by conflict resolution 451# without further state splitting is not always sufficient to produce a 452# parser that can detect all syntax errors as soon as possible on one 453# token of lookahead. However, LAC solves the problem completely even 454# with minimal LR parser tables. 455 456AT_SETUP([[LAC: %nonassoc requires splitting canonical LR states]]) 457AT_BISON_OPTION_PUSHDEFS 458AT_DATA_GRAMMAR([[input.y]], 459[[%code { 460 #include <stdio.h> 461 ]AT_YYERROR_DECLARE[ 462 ]AT_YYLEX_DECLARE[ 463} 464 465%error-verbose 466%nonassoc 'a' 467 468%% 469 470start: 471 'a' problem 'a' // First context. 472| 'b' problem 'b' // Second context. 473| 'c' reduce-nonassoc // Just makes reduce-nonassoc useful. 474; 475 476problem: 477 look reduce-nonassoc 478| look 'a' 479| look 'b' 480; 481 482// For the state reached after shifting the 'a' in these productions, 483// lookahead sets are the same in both the first and second contexts. 484// Thus, canonical LR reuses the same state for both contexts. However, 485// the lookahead 'a' for the reduction "look: 'a'" later becomes an 486// error action only in the first context. In order to immediately 487// detect the syntax error on 'a' here for only the first context, this 488// canonical LR state would have to be split into two states, and the 489// 'a' lookahead would have to be removed from only one of the states. 490look: 491 'a' // Reduction lookahead set is always ['a', 'b']. 492| 'a' 'b' 493| 'a' 'c' // 'c' is forgotten as an expected token. 494; 495 496reduce-nonassoc: %prec 'a'; 497 498%% 499]AT_YYERROR_DEFINE[ 500]AT_YYLEX_DEFINE(["aaa"])[ 501 502int 503main (void) 504{ 505 return yyparse (); 506} 507]]) 508AT_BISON_OPTION_POPDEFS 509 510# Show canonical LR's failure. 511AT_BISON_CHECK([[-Dlr.type=canonical-lr -o input.c input.y]], 512 [[0]], [[]], 513[[input.y: conflicts: 2 shift/reduce 514]]) 515AT_COMPILE([[input]]) 516AT_PARSER_CHECK([[./input]], [[1]], [[]], 517[[syntax error, unexpected 'a', expecting 'b' 518]]) 519 520# It's corrected by LAC. 521AT_BISON_CHECK([[-Dlr.type=canonical-lr -Dparse.lac=full \ 522 -o input.c input.y]], [[0]], [[]], 523[[input.y: conflicts: 2 shift/reduce 524]]) 525AT_COMPILE([[input]]) 526AT_PARSER_CHECK([[./input]], [[1]], [[]], 527[[syntax error, unexpected 'a', expecting 'b' or 'c' 528]]) 529 530# IELR is sufficient when LAC is used. 531AT_BISON_CHECK([[-Dlr.type=ielr -Dparse.lac=full -o input.c input.y]], 532 [[0]], [[]], 533[[input.y: conflicts: 2 shift/reduce 534]]) 535AT_COMPILE([[input]]) 536AT_PARSER_CHECK([[./input]], [[1]], [[]], 537[[syntax error, unexpected 'a', expecting 'b' or 'c' 538]]) 539 540AT_CLEANUP 541 542## ------------------------- ## 543## Unresolved SR Conflicts. ## 544## ------------------------- ## 545 546AT_SETUP([Unresolved SR Conflicts]) 547 548AT_KEYWORDS([report]) 549 550AT_DATA([input.y], 551[[%token NUM OP 552%% 553exp: exp OP exp | NUM; 554]]) 555 556AT_BISON_CHECK([-o input.c --report=all input.y], 0, [], 557[input.y: conflicts: 1 shift/reduce 558]) 559 560# Check the contents of the report. 561AT_CHECK([cat input.output], [], 562[[State 5 conflicts: 1 shift/reduce 563 564 565Grammar 566 567 0 $accept: exp $end 568 569 1 exp: exp OP exp 570 2 | NUM 571 572 573Terminals, with rules where they appear 574 575$end (0) 0 576error (256) 577NUM (258) 2 578OP (259) 1 579 580 581Nonterminals, with rules where they appear 582 583$accept (5) 584 on left: 0 585exp (6) 586 on left: 1 2, on right: 0 1 587 588 589State 0 590 591 0 $accept: . exp $end 592 1 exp: . exp OP exp 593 2 | . NUM 594 595 NUM shift, and go to state 1 596 597 exp go to state 2 598 599 600State 1 601 602 2 exp: NUM . 603 604 $default reduce using rule 2 (exp) 605 606 607State 2 608 609 0 $accept: exp . $end 610 1 exp: exp . OP exp 611 612 $end shift, and go to state 3 613 OP shift, and go to state 4 614 615 616State 3 617 618 0 $accept: exp $end . 619 620 $default accept 621 622 623State 4 624 625 1 exp: . exp OP exp 626 1 | exp OP . exp 627 2 | . NUM 628 629 NUM shift, and go to state 1 630 631 exp go to state 5 632 633 634State 5 635 636 1 exp: exp . OP exp 637 1 | exp OP exp . [$end, OP] 638 639 OP shift, and go to state 4 640 641 OP [reduce using rule 1 (exp)] 642 $default reduce using rule 1 (exp) 643]]) 644 645AT_CLEANUP 646 647 648 649## ----------------------- ## 650## Resolved SR Conflicts. ## 651## ----------------------- ## 652 653AT_SETUP([Resolved SR Conflicts]) 654 655AT_KEYWORDS([report]) 656 657AT_DATA([input.y], 658[[%token NUM OP 659%left OP 660%% 661exp: exp OP exp | NUM; 662]]) 663 664AT_BISON_CHECK([-o input.c --report=all input.y]) 665 666# Check the contents of the report. 667AT_CHECK([cat input.output], [], 668[[Grammar 669 670 0 $accept: exp $end 671 672 1 exp: exp OP exp 673 2 | NUM 674 675 676Terminals, with rules where they appear 677 678$end (0) 0 679error (256) 680NUM (258) 2 681OP (259) 1 682 683 684Nonterminals, with rules where they appear 685 686$accept (5) 687 on left: 0 688exp (6) 689 on left: 1 2, on right: 0 1 690 691 692State 0 693 694 0 $accept: . exp $end 695 1 exp: . exp OP exp 696 2 | . NUM 697 698 NUM shift, and go to state 1 699 700 exp go to state 2 701 702 703State 1 704 705 2 exp: NUM . 706 707 $default reduce using rule 2 (exp) 708 709 710State 2 711 712 0 $accept: exp . $end 713 1 exp: exp . OP exp 714 715 $end shift, and go to state 3 716 OP shift, and go to state 4 717 718 719State 3 720 721 0 $accept: exp $end . 722 723 $default accept 724 725 726State 4 727 728 1 exp: . exp OP exp 729 1 | exp OP . exp 730 2 | . NUM 731 732 NUM shift, and go to state 1 733 734 exp go to state 5 735 736 737State 5 738 739 1 exp: exp . OP exp 740 1 | exp OP exp . [$end, OP] 741 742 $default reduce using rule 1 (exp) 743 744 Conflict between rule 1 and token OP resolved as reduce (%left OP). 745]]) 746 747AT_CLEANUP 748 749 750## -------------------------------- ## 751## Defaulted Conflicted Reduction. ## 752## -------------------------------- ## 753 754# When there are RR conflicts, some rules are disabled. Usually it is 755# simply displayed as: 756# 757# $end reduce using rule 3 (num) 758# $end [reduce using rule 4 (id)] 759# 760# But when `reduce 3' is the default action, we'd produce: 761# 762# $end [reduce using rule 4 (id)] 763# $default reduce using rule 3 (num) 764# 765# In this precise case (a reduction is masked by the default 766# reduction), we make the `reduce 3' explicit: 767# 768# $end reduce using rule 3 (num) 769# $end [reduce using rule 4 (id)] 770# $default reduce using rule 3 (num) 771# 772# Maybe that's not the best display, but then, please propose something 773# else. 774 775AT_SETUP([Defaulted Conflicted Reduction]) 776AT_KEYWORDS([report]) 777 778AT_DATA([input.y], 779[[%% 780exp: num | id; 781num: '0'; 782id : '0'; 783%% 784]]) 785 786AT_BISON_CHECK([-o input.c --report=all input.y], 0, [], 787[[input.y: conflicts: 1 reduce/reduce 788input.y:4.6-8: warning: rule useless in parser due to conflicts: id: '0' 789]]) 790 791# Check the contents of the report. 792AT_CHECK([cat input.output], [], 793[[Rules useless in parser due to conflicts 794 795 4 id: '0' 796 797 798State 1 conflicts: 1 reduce/reduce 799 800 801Grammar 802 803 0 $accept: exp $end 804 805 1 exp: num 806 2 | id 807 808 3 num: '0' 809 810 4 id: '0' 811 812 813Terminals, with rules where they appear 814 815$end (0) 0 816'0' (48) 3 4 817error (256) 818 819 820Nonterminals, with rules where they appear 821 822$accept (4) 823 on left: 0 824exp (5) 825 on left: 1 2, on right: 0 826num (6) 827 on left: 3, on right: 1 828id (7) 829 on left: 4, on right: 2 830 831 832State 0 833 834 0 $accept: . exp $end 835 1 exp: . num 836 2 | . id 837 3 num: . '0' 838 4 id: . '0' 839 840 '0' shift, and go to state 1 841 842 exp go to state 2 843 num go to state 3 844 id go to state 4 845 846 847State 1 848 849 3 num: '0' . [$end] 850 4 id: '0' . [$end] 851 852 $end reduce using rule 3 (num) 853 $end [reduce using rule 4 (id)] 854 $default reduce using rule 3 (num) 855 856 857State 2 858 859 0 $accept: exp . $end 860 861 $end shift, and go to state 5 862 863 864State 3 865 866 1 exp: num . 867 868 $default reduce using rule 1 (exp) 869 870 871State 4 872 873 2 exp: id . 874 875 $default reduce using rule 2 (exp) 876 877 878State 5 879 880 0 $accept: exp $end . 881 882 $default accept 883]]) 884 885AT_CLEANUP 886 887 888 889 890## -------------------- ## 891## %expect not enough. ## 892## -------------------- ## 893 894AT_SETUP([%expect not enough]) 895 896AT_DATA([input.y], 897[[%token NUM OP 898%expect 0 899%% 900exp: exp OP exp | NUM; 901]]) 902 903AT_BISON_CHECK([-o input.c input.y], 1, [], 904[input.y: conflicts: 1 shift/reduce 905input.y: error: expected 0 shift/reduce conflicts 906]) 907AT_CLEANUP 908 909 910## --------------- ## 911## %expect right. ## 912## --------------- ## 913 914AT_SETUP([%expect right]) 915 916AT_DATA([input.y], 917[[%token NUM OP 918%expect 1 919%% 920exp: exp OP exp | NUM; 921]]) 922 923AT_BISON_CHECK([-o input.c input.y]) 924AT_CLEANUP 925 926 927## ------------------ ## 928## %expect too much. ## 929## ------------------ ## 930 931AT_SETUP([%expect too much]) 932 933AT_DATA([input.y], 934[[%token NUM OP 935%expect 2 936%% 937exp: exp OP exp | NUM; 938]]) 939 940AT_BISON_CHECK([-o input.c input.y], 1, [], 941[input.y: conflicts: 1 shift/reduce 942input.y: error: expected 2 shift/reduce conflicts 943]) 944AT_CLEANUP 945 946 947## ------------------------------- ## 948## %expect with reduce conflicts. ## 949## ------------------------------- ## 950 951AT_SETUP([%expect with reduce conflicts]) 952 953AT_DATA([input.y], 954[[%expect 0 955%% 956program: a 'a' | a a; 957a: 'a'; 958]]) 959 960AT_BISON_CHECK([-o input.c input.y], 1, [], 961[input.y: conflicts: 1 reduce/reduce 962input.y: error: expected 0 reduce/reduce conflicts 963]) 964AT_CLEANUP 965 966 967## ------------------------- ## 968## %prec with user strings. ## 969## ------------------------- ## 970 971AT_SETUP([%prec with user string]) 972 973AT_DATA([[input.y]], 974[[%% 975exp: 976 "foo" %prec "foo" 977; 978]]) 979 980AT_BISON_CHECK([-o input.c input.y]) 981AT_CLEANUP 982 983 984## -------------------------------- ## 985## %no-default-prec without %prec. ## 986## -------------------------------- ## 987 988AT_SETUP([%no-default-prec without %prec]) 989 990AT_DATA([[input.y]], 991[[%left '+' 992%left '*' 993 994%% 995 996%no-default-prec; 997 998e: e '+' e 999 | e '*' e 1000 | '0' 1001 ; 1002]]) 1003 1004AT_BISON_CHECK([-o input.c input.y], 0, [], 1005[[input.y: conflicts: 4 shift/reduce 1006]]) 1007AT_CLEANUP 1008 1009 1010## ----------------------------- ## 1011## %no-default-prec with %prec. ## 1012## ----------------------------- ## 1013 1014AT_SETUP([%no-default-prec with %prec]) 1015 1016AT_DATA([[input.y]], 1017[[%left '+' 1018%left '*' 1019 1020%% 1021 1022%no-default-prec; 1023 1024e: e '+' e %prec '+' 1025 | e '*' e %prec '*' 1026 | '0' 1027 ; 1028]]) 1029 1030AT_BISON_CHECK([-o input.c input.y]) 1031AT_CLEANUP 1032 1033 1034## --------------- ## 1035## %default-prec. ## 1036## --------------- ## 1037 1038AT_SETUP([%default-prec]) 1039 1040AT_DATA([[input.y]], 1041[[%left '+' 1042%left '*' 1043 1044%% 1045 1046%default-prec; 1047 1048e: e '+' e 1049 | e '*' e 1050 | '0' 1051 ; 1052]]) 1053 1054AT_BISON_CHECK([-o input.c input.y]) 1055AT_CLEANUP 1056 1057 1058## ---------------------------------------------- ## 1059## Unreachable States After Conflict Resolution. ## 1060## ---------------------------------------------- ## 1061 1062AT_SETUP([[Unreachable States After Conflict Resolution]]) 1063 1064# If conflict resolution makes states unreachable, remove those states, report 1065# rules that are then unused, and don't report conflicts in those states. Test 1066# what happens when a nonterminal becomes useless as a result of state removal 1067# since that causes lalr.o's goto map to be rewritten. 1068 1069AT_DATA([[input.y]], 1070[[%output "input.c" 1071%left 'a' 1072 1073%% 1074 1075start: resolved_conflict 'a' reported_conflicts 'a' ; 1076 1077/* S/R conflict resolved as reduce, so the state with item 1078 * (resolved_conflict: 'a' . unreachable1) and all it transition successors are 1079 * unreachable, and the associated production is useless. */ 1080resolved_conflict: 1081 'a' unreachable1 1082 | %prec 'a' 1083 ; 1084 1085/* S/R conflict that need not be reported since it is unreachable because of 1086 * the previous conflict resolution. Nonterminal unreachable1 and all its 1087 * productions are useless. */ 1088unreachable1: 1089 'a' unreachable2 1090 | 1091 ; 1092 1093/* Likewise for a R/R conflict and nonterminal unreachable2. */ 1094unreachable2: | ; 1095 1096/* Make sure remaining S/R and R/R conflicts are still reported correctly even 1097 * when their states are renumbered due to state removal. */ 1098reported_conflicts: 1099 'a' 1100 | 'a' 1101 | 1102 ; 1103 1104]]) 1105 1106AT_BISON_CHECK([[--report=all input.y]], 0, [], 1107[[input.y: conflicts: 1 shift/reduce, 1 reduce/reduce 1108input.y:12.5-20: warning: rule useless in parser due to conflicts: resolved_conflict: 'a' unreachable1 1109input.y:20.5-20: warning: rule useless in parser due to conflicts: unreachable1: 'a' unreachable2 1110input.y:21.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */ 1111input.y:25.13: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1112input.y:25.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1113input.y:31.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a' 1114input.y:32.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */ 1115]]) 1116 1117AT_CHECK([[cat input.output]], 0, 1118[[Rules useless in parser due to conflicts 1119 1120 2 resolved_conflict: 'a' unreachable1 1121 1122 4 unreachable1: 'a' unreachable2 1123 5 | /* empty */ 1124 1125 6 unreachable2: /* empty */ 1126 7 | /* empty */ 1127 1128 9 reported_conflicts: 'a' 1129 10 | /* empty */ 1130 1131 1132State 4 conflicts: 1 shift/reduce 1133State 5 conflicts: 1 reduce/reduce 1134 1135 1136Grammar 1137 1138 0 $accept: start $end 1139 1140 1 start: resolved_conflict 'a' reported_conflicts 'a' 1141 1142 2 resolved_conflict: 'a' unreachable1 1143 3 | /* empty */ 1144 1145 4 unreachable1: 'a' unreachable2 1146 5 | /* empty */ 1147 1148 6 unreachable2: /* empty */ 1149 7 | /* empty */ 1150 1151 8 reported_conflicts: 'a' 1152 9 | 'a' 1153 10 | /* empty */ 1154 1155 1156Terminals, with rules where they appear 1157 1158$end (0) 0 1159'a' (97) 1 2 4 8 9 1160error (256) 1161 1162 1163Nonterminals, with rules where they appear 1164 1165$accept (4) 1166 on left: 0 1167start (5) 1168 on left: 1, on right: 0 1169resolved_conflict (6) 1170 on left: 2 3, on right: 1 1171unreachable1 (7) 1172 on left: 4 5, on right: 2 1173unreachable2 (8) 1174 on left: 6 7, on right: 4 1175reported_conflicts (9) 1176 on left: 8 9 10, on right: 1 1177 1178 1179State 0 1180 1181 0 $accept: . start $end 1182 1 start: . resolved_conflict 'a' reported_conflicts 'a' 1183 2 resolved_conflict: . 'a' unreachable1 1184 3 | . ['a'] 1185 1186 $default reduce using rule 3 (resolved_conflict) 1187 1188 start go to state 1 1189 resolved_conflict go to state 2 1190 1191 Conflict between rule 3 and token 'a' resolved as reduce (%left 'a'). 1192 1193 1194State 1 1195 1196 0 $accept: start . $end 1197 1198 $end shift, and go to state 3 1199 1200 1201State 2 1202 1203 1 start: resolved_conflict . 'a' reported_conflicts 'a' 1204 1205 'a' shift, and go to state 4 1206 1207 1208State 3 1209 1210 0 $accept: start $end . 1211 1212 $default accept 1213 1214 1215State 4 1216 1217 1 start: resolved_conflict 'a' . reported_conflicts 'a' 1218 8 reported_conflicts: . 'a' 1219 9 | . 'a' 1220 10 | . ['a'] 1221 1222 'a' shift, and go to state 5 1223 1224 'a' [reduce using rule 10 (reported_conflicts)] 1225 1226 reported_conflicts go to state 6 1227 1228 1229State 5 1230 1231 8 reported_conflicts: 'a' . ['a'] 1232 9 | 'a' . ['a'] 1233 1234 'a' reduce using rule 8 (reported_conflicts) 1235 'a' [reduce using rule 9 (reported_conflicts)] 1236 $default reduce using rule 8 (reported_conflicts) 1237 1238 1239State 6 1240 1241 1 start: resolved_conflict 'a' reported_conflicts . 'a' 1242 1243 'a' shift, and go to state 7 1244 1245 1246State 7 1247 1248 1 start: resolved_conflict 'a' reported_conflicts 'a' . 1249 1250 $default reduce using rule 1 (start) 1251]]) 1252 1253AT_DATA([[input-keep.y]], 1254[[%define lr.keep-unreachable-states 1255]]) 1256AT_CHECK([[cat input.y >> input-keep.y]]) 1257 1258AT_BISON_CHECK([[input-keep.y]], 0, [], 1259[[input-keep.y: conflicts: 2 shift/reduce, 2 reduce/reduce 1260input-keep.y:22.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */ 1261input-keep.y:26.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */ 1262input-keep.y:32.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a' 1263input-keep.y:33.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */ 1264]]) 1265 1266AT_CLEANUP 1267 1268 1269## ------------------------------------------------------------ ## 1270## Solved conflicts report for multiple reductions in a state. ## 1271## ------------------------------------------------------------ ## 1272 1273AT_SETUP([[Solved conflicts report for multiple reductions in a state]]) 1274 1275# Used to lose earlier solved conflict messages even within a single S/R/R. 1276 1277AT_DATA([[input.y]], 1278[[%left 'a' 1279%right 'b' 1280%right 'c' 1281%right 'd' 1282%% 1283start: 1284 'a' 1285 | empty_a 'a' 1286 | 'b' 1287 | empty_b 'b' 1288 | 'c' 1289 | empty_c1 'c' 1290 | empty_c2 'c' 1291 | empty_c3 'c' 1292 ; 1293empty_a: %prec 'a' ; 1294empty_b: %prec 'b' ; 1295empty_c1: %prec 'c' ; 1296empty_c2: %prec 'c' ; 1297empty_c3: %prec 'd' ; 1298]]) 1299AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore]) 1300AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0, 1301[[State 0 1302 1303 0 $accept: . start $end 1304 1 start: . 'a' 1305 2 | . empty_a 'a' 1306 3 | . 'b' 1307 4 | . empty_b 'b' 1308 5 | . 'c' 1309 6 | . empty_c1 'c' 1310 7 | . empty_c2 'c' 1311 8 | . empty_c3 'c' 1312 9 empty_a: . ['a'] 1313 10 empty_b: . [] 1314 11 empty_c1: . [] 1315 12 empty_c2: . [] 1316 13 empty_c3: . ['c'] 1317 1318 'b' shift, and go to state 1 1319 1320 'c' reduce using rule 13 (empty_c3) 1321 $default reduce using rule 9 (empty_a) 1322 1323 start go to state 2 1324 empty_a go to state 3 1325 empty_b go to state 4 1326 empty_c1 go to state 5 1327 empty_c2 go to state 6 1328 empty_c3 go to state 7 1329 1330 Conflict between rule 9 and token 'a' resolved as reduce (%left 'a'). 1331 Conflict between rule 10 and token 'b' resolved as shift (%right 'b'). 1332 Conflict between rule 11 and token 'c' resolved as shift (%right 'c'). 1333 Conflict between rule 12 and token 'c' resolved as shift (%right 'c'). 1334 Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd'). 1335 1336 1337State 1 1338]]) 1339 1340AT_CLEANUP 1341 1342 1343## ------------------------------------------------------------ ## 1344## %nonassoc error actions for multiple reductions in a state. ## 1345## ------------------------------------------------------------ ## 1346 1347# Used to abort when trying to resolve conflicts as %nonassoc error actions for 1348# multiple reductions in a state. 1349 1350# For a %nonassoc error action token, used to print the first remaining 1351# reduction on that token without brackets. 1352 1353AT_SETUP([[%nonassoc error actions for multiple reductions in a state]]) 1354 1355AT_DATA([[input.y]], 1356[[%nonassoc 'a' 'b' 'c' 1357%% 1358start: 1359 'a' 1360 | empty_a 'a' 1361 | 'b' 1362 | empty_b 'b' 1363 | 'c' 1364 | empty_c1 'c' 1365 | empty_c2 'c' 1366 | empty_c3 'c' 1367 ; 1368empty_a: %prec 'a' ; 1369empty_b: %prec 'b' ; 1370empty_c1: %prec 'c' ; 1371empty_c2: %prec 'c' ; 1372empty_c3: %prec 'c' ; 1373]]) 1374 1375AT_BISON_CHECK([[--report=all -o input.c input.y]], 0, [], [ignore]) 1376AT_CHECK([[cat input.output | sed -n '/^State 0$/,/^State 1$/p']], 0, 1377[[State 0 1378 1379 0 $accept: . start $end 1380 1 start: . 'a' 1381 2 | . empty_a 'a' 1382 3 | . 'b' 1383 4 | . empty_b 'b' 1384 5 | . 'c' 1385 6 | . empty_c1 'c' 1386 7 | . empty_c2 'c' 1387 8 | . empty_c3 'c' 1388 9 empty_a: . [] 1389 10 empty_b: . [] 1390 11 empty_c1: . [] 1391 12 empty_c2: . ['c'] 1392 13 empty_c3: . ['c'] 1393 1394 'a' error (nonassociative) 1395 'b' error (nonassociative) 1396 'c' error (nonassociative) 1397 1398 'c' [reduce using rule 12 (empty_c2)] 1399 'c' [reduce using rule 13 (empty_c3)] 1400 1401 start go to state 1 1402 empty_a go to state 2 1403 empty_b go to state 3 1404 empty_c1 go to state 4 1405 empty_c2 go to state 5 1406 empty_c3 go to state 6 1407 1408 Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a'). 1409 Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 'b'). 1410 Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 'c'). 1411 1412 1413State 1 1414]]) 1415AT_CLEANUP 1416 1417 1418## --------------------------------- ## 1419## -W versus %expect and %expect-rr ## 1420## --------------------------------- ## 1421 1422AT_SETUP([[-W versus %expect and %expect-rr]]) 1423 1424AT_DATA([[sr-rr.y]], 1425[[%glr-parser 1426%% 1427start: 'a' | A 'a' | B 'a' ; 1428A: ; 1429B: ; 1430]]) 1431AT_DATA([[sr.y]], 1432[[%glr-parser 1433%% 1434start: 'a' | A 'a' ; 1435A: ; 1436]]) 1437AT_DATA([[rr.y]], 1438[[%glr-parser 1439%% 1440start: A | B ; 1441A: ; 1442B: ; 1443]]) 1444 1445AT_BISON_CHECK([[sr-rr.y]], [[0]], [[]], 1446[[sr-rr.y: conflicts: 1 shift/reduce, 1 reduce/reduce 1447]]) 1448AT_BISON_CHECK([[-Wno-conflicts-sr sr-rr.y]], [[0]], [[]], 1449[[sr-rr.y: conflicts: 1 reduce/reduce 1450]]) 1451AT_BISON_CHECK([[-Wno-conflicts-rr sr-rr.y]], [[0]], [[]], 1452[[sr-rr.y: conflicts: 1 shift/reduce 1453]]) 1454 1455[for gram in sr-rr sr rr; do 1456 for sr_exp_i in '' 0 1 2; do 1457 for rr_exp_i in '' 0 1 2; do 1458 test -z "$sr_exp_i" && test -z "$rr_exp_i" && continue 1459 1460 # Build grammar file. 1461 sr_exp=0 1462 rr_exp=0 1463 file=$gram 1464 directives= 1465 if test -n "$sr_exp_i"; then 1466 sr_exp=$sr_exp_i 1467 file=$file-expect-$sr_exp 1468 directives="%expect $sr_exp" 1469 fi 1470 if test -n "$rr_exp_i"; then 1471 rr_exp=$rr_exp_i 1472 file=$file-expect-rr-$rr_exp 1473 directives="$directives %expect-rr $rr_exp" 1474 fi 1475 file=$file.y 1476 echo "$directives" > $file 1477 cat $gram.y >> $file 1478 1479 # Count actual conflicts. 1480 conflicts= 1481 sr_count=0 1482 rr_count=0 1483 if test $gram = sr || test $gram = sr-rr; then 1484 conflicts="1 shift/reduce" 1485 sr_count=1 1486 fi 1487 if test $gram = rr || test $gram = sr-rr; then 1488 if test -n "$conflicts"; then 1489 conflicts="$conflicts, " 1490 fi 1491 conflicts="${conflicts}1 reduce/reduce" 1492 rr_count=1 1493 fi 1494 1495 # Run tests. 1496 if test $sr_count -eq $sr_exp && test $rr_count -eq $rr_exp; then 1497 ]AT_BISON_CHECK([[-Wnone $file]])[ 1498 ]AT_BISON_CHECK([[-Werror $file]])[ 1499 else 1500 echo "$file: conflicts: $conflicts" > experr 1501 if test $sr_count -ne $sr_exp; then 1502 if test $sr_exp -ne 1; then s=s; else s= ; fi 1503 echo "$file: error: expected $sr_exp shift/reduce conflict$s" >> experr 1504 fi 1505 if test $rr_count -ne $rr_exp; then 1506 if test $rr_exp -ne 1; then s=s; else s= ; fi 1507 echo "$file: error: expected $rr_exp reduce/reduce conflict$s" >> experr 1508 fi 1509 ]AT_BISON_CHECK([[-Wnone $file]], [[1]], [[]], [[experr]])[ 1510 ]AT_BISON_CHECK([[-Werror $file]], [[1]], [[]], [[experr]])[ 1511 fi 1512 done 1513 done 1514done] 1515 1516AT_CLEANUP 1517