# Exercising Bison on conflicts. -*- Autotest -*- # Copyright (C) 2002 Free Software Foundation, Inc. # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2, or (at your option) # any later version. # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA # 02111-1307, USA. AT_BANNER([[Conflicts.]]) ## ---------------- ## ## S/R in initial. ## ## ---------------- ## # I once hacked Bison in such a way that it lost its reductions on the # initial state (because it was confusing it with the last state). It # took me a while to strip down my failures to this simple case. So # make sure it finds the s/r conflict below. AT_SETUP([S/R in initial]) AT_DATA([[input.y]], [[%expect 1 %% exp: e 'e'; e: 'e' | /* Nothing. */; ]]) AT_CHECK([bison -o input.c input.y], 0, [], [[input.y:4.8: warning: rule never reduced because of conflicts: e: /* empty */ ]]) AT_CLEANUP ## ------------------- ## ## %nonassoc and eof. ## ## ------------------- ## AT_SETUP([%nonassoc and eof]) AT_DATA([input.y], [[ %{ #include /* We don't need a perfect malloc for these tests. */ #undef malloc #include #if STDC_HEADERS # include #endif #define YYERROR_VERBOSE 1 static void yyerror (const char *msg) { fprintf (stderr, "%s\n", msg); exit (1); } /* The current argument. */ static const char *input = NULL; static int yylex (void) { /* No token stands for end of file. */ if (input && *input) return *input++; else return 0; } %} %nonassoc '<' '>' %% expr: expr '<' expr | expr '>' expr | '0' ; %% int main (int argc, const char *argv[]) { if (argc > 1) input = argv[1]; return yyparse (); } ]]) # Specify the output files to avoid problems on different file systems. AT_CHECK([bison -o input.c input.y]) AT_COMPILE([input]) AT_PARSER_CHECK([./input '0<0']) # FIXME: This is an actual bug, but a new one, in the sense that # no one has ever spotted it! The messages are *wrong*: there should # be nothing there, it should be expected eof. AT_PARSER_CHECK([./input '0<0<0'], [1], [], [parse error, unexpected '<', expecting '<' or '>' ]) AT_PARSER_CHECK([./input '0>0']) AT_PARSER_CHECK([./input '0>0>0'], [1], [], [parse error, unexpected '>', expecting '<' or '>' ]) AT_PARSER_CHECK([./input '0<0>0'], [1], [], [parse error, unexpected '>', expecting '<' or '>' ]) AT_CLEANUP ## ------------------------- ## ## Unresolved SR Conflicts. ## ## ------------------------- ## AT_SETUP([Unresolved SR Conflicts]) AT_KEYWORDS([report]) AT_DATA([input.y], [[%token NUM OP %% exp: exp OP exp | NUM; ]]) AT_CHECK([bison -o input.c --report=all input.y], 0, [], [input.y: warning: 1 shift/reduce conflict ]) # Check the contents of the report. AT_CHECK([cat input.output], [], [[State 5 contains 1 shift/reduce conflict. Grammar 0 $accept: exp $end 1 exp: exp OP exp 2 | NUM Terminals, with rules where they appear $end (0) 0 error (256) NUM (258) 2 OP (259) 1 Nonterminals, with rules where they appear $accept (5) on left: 0 exp (6) on left: 1 2, on right: 0 1 state 0 0 $accept: . exp $end 1 exp: . exp OP exp 2 | . NUM NUM shift, and go to state 1 exp go to state 2 state 1 2 exp: NUM . $default reduce using rule 2 (exp) state 2 0 $accept: exp . $end 1 exp: exp . OP exp $end shift, and go to state 3 OP shift, and go to state 4 state 3 0 $accept: exp $end . $default accept state 4 1 exp: . exp OP exp 1 | exp OP . exp 2 | . NUM NUM shift, and go to state 1 exp go to state 5 state 5 1 exp: exp . OP exp [$end, OP] 1 | exp OP exp . [$end, OP] OP shift, and go to state 4 OP [reduce using rule 1 (exp)] $default reduce using rule 1 (exp) ]]) AT_CLEANUP ## ----------------------- ## ## Resolved SR Conflicts. ## ## ----------------------- ## AT_SETUP([Resolved SR Conflicts]) AT_KEYWORDS([report]) AT_DATA([input.y], [[%token NUM OP %left OP %% exp: exp OP exp | NUM; ]]) AT_CHECK([bison -o input.c --report=all input.y]) # Check the contents of the report. AT_CHECK([cat input.output], [], [[Grammar 0 $accept: exp $end 1 exp: exp OP exp 2 | NUM Terminals, with rules where they appear $end (0) 0 error (256) NUM (258) 2 OP (259) 1 Nonterminals, with rules where they appear $accept (5) on left: 0 exp (6) on left: 1 2, on right: 0 1 state 0 0 $accept: . exp $end 1 exp: . exp OP exp 2 | . NUM NUM shift, and go to state 1 exp go to state 2 state 1 2 exp: NUM . $default reduce using rule 2 (exp) state 2 0 $accept: exp . $end 1 exp: exp . OP exp $end shift, and go to state 3 OP shift, and go to state 4 state 3 0 $accept: exp $end . $default accept state 4 1 exp: . exp OP exp 1 | exp OP . exp 2 | . NUM NUM shift, and go to state 1 exp go to state 5 state 5 1 exp: exp . OP exp [$end, OP] 1 | exp OP exp . [$end, OP] $default reduce using rule 1 (exp) Conflict between rule 1 and token OP resolved as reduce (%left OP). ]]) AT_CLEANUP ## -------------------------------- ## ## Defaulted Conflicted Reduction. ## ## -------------------------------- ## # When there are RR conflicts, some rules are disabled. Usually it is # simply displayed as: # # $end reduce using rule 3 (num) # $end [reduce using rule 4 (id)] # # But when `reduce 3' is the default action, we'd produce: # # $end [reduce using rule 4 (id)] # $default reduce using rule 3 (num) # # In this precise case (a reduction is masked by the default # reduction), we make the `reduce 3' explicit: # # $end reduce using rule 3 (num) # $end [reduce using rule 4 (id)] # $default reduce using rule 3 (num) # # Maybe that's not the best display, but then, please propose something # else. AT_SETUP([Defaulted Conflicted Reduction]) AT_KEYWORDS([report]) AT_DATA([input.y], [[%% exp: num | id; num: '0'; id : '0'; %% ]]) AT_CHECK([bison -o input.c --report=all input.y], 0, [], [[input.y: warning: 1 reduce/reduce conflict input.y:4.4-8: warning: rule never reduced because of conflicts: id: '0' ]]) # Check the contents of the report. AT_CHECK([cat input.output], [], [[Rules never reduced 4 id: '0' State 1 contains 1 reduce/reduce conflict. Grammar 0 $accept: exp $end 1 exp: num 2 | id 3 num: '0' 4 id: '0' Terminals, with rules where they appear $end (0) 0 '0' (48) 3 4 error (256) Nonterminals, with rules where they appear $accept (4) on left: 0 exp (5) on left: 1 2, on right: 0 num (6) on left: 3, on right: 1 id (7) on left: 4, on right: 2 state 0 0 $accept: . exp $end 1 exp: . num 2 | . id 3 num: . '0' 4 id: . '0' '0' shift, and go to state 1 exp go to state 2 num go to state 3 id go to state 4 state 1 3 num: '0' . [$end] 4 id: '0' . [$end] $end reduce using rule 3 (num) $end [reduce using rule 4 (id)] $default reduce using rule 3 (num) state 2 0 $accept: exp . $end $end shift, and go to state 5 state 3 1 exp: num . $default reduce using rule 1 (exp) state 4 2 exp: id . $default reduce using rule 2 (exp) state 5 0 $accept: exp $end . $default accept ]]) AT_CLEANUP ## -------------------- ## ## %expect not enough. ## ## -------------------- ## AT_SETUP([%expect not enough]) AT_DATA([input.y], [[%token NUM OP %expect 0 %% exp: exp OP exp | NUM; ]]) AT_CHECK([bison -o input.c input.y], 1, [], [input.y: warning: 1 shift/reduce conflict input.y: expected 0 shift/reduce conflicts ]) AT_CLEANUP ## --------------- ## ## %expect right. ## ## --------------- ## AT_SETUP([%expect right]) AT_DATA([input.y], [[%token NUM OP %expect 1 %% exp: exp OP exp | NUM; ]]) AT_CHECK([bison -o input.c input.y]) AT_CLEANUP ## ------------------ ## ## %expect too much. ## ## ------------------ ## AT_SETUP([%expect too much]) AT_DATA([input.y], [[%token NUM OP %expect 2 %% exp: exp OP exp | NUM; ]]) AT_CHECK([bison -o input.c input.y], 1, [], [input.y: warning: 1 shift/reduce conflict input.y: expected 2 shift/reduce conflicts ]) AT_CLEANUP