# Exercising Bison on conflicts. -*- Autotest -*- # Copyright (C) 2002, 2003, 2004, 2005, 2007 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., 51 Franklin Street, Fifth Floor, Boston, MA # 02110-1301, 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.9: warning: rule never reduced because of conflicts: e: /* empty */ ]]) AT_CLEANUP ## ------------------- ## ## %nonassoc and eof. ## ## ------------------- ## AT_SETUP([%nonassoc and eof]) AT_DATA_GRAMMAR([input.y], [[ %{ #include #include #include #define YYERROR_VERBOSE 1 static void yyerror (const char *msg) { fprintf (stderr, "%s\n", msg); } /* The current argument. */ static const char *input; static int yylex (void) { static size_t toknum; if (! (toknum <= strlen (input))) abort (); return input[toknum++]; } %} %nonassoc '<' '>' %% expr: expr '<' expr | expr '>' expr | '0' ; %% int main (int argc, const char *argv[]) { input = argc <= 1 ? "" : 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], [], [syntax error, unexpected '<', expecting '<' or '>' ]) AT_PARSER_CHECK([./input '0>0']) AT_PARSER_CHECK([./input '0>0>0'], [1], [], [syntax error, unexpected '>', expecting '<' or '>' ]) AT_PARSER_CHECK([./input '0<0>0'], [1], [], [syntax 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: conflicts: 1 shift/reduce ]) # Check the contents of the report. AT_CHECK([cat input.output], [], [[State 5 conflicts: 1 shift/reduce 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: conflicts: 1 reduce/reduce input.y:4.6-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 conflicts: 1 reduce/reduce 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: conflicts: 1 shift/reduce 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: conflicts: 1 shift/reduce input.y: expected 2 shift/reduce conflicts ]) AT_CLEANUP ## ------------------------------ ## ## %expect with reduce conflicts ## ## ------------------------------ ## AT_SETUP([%expect with reduce conflicts]) AT_DATA([input.y], [[%expect 0 %% program: a 'a' | a a; a: 'a'; ]]) AT_CHECK([bison -o input.c input.y], 1, [], [input.y: conflicts: 1 reduce/reduce input.y: expected 0 reduce/reduce conflicts ]) AT_CLEANUP ## ------------------------------- ## ## %no-default-prec without %prec ## ## ------------------------------- ## AT_SETUP([%no-default-prec without %prec]) AT_DATA([[input.y]], [[%left '+' %left '*' %% %no-default-prec; e: e '+' e | e '*' e | '0' ; ]]) AT_CHECK([bison -o input.c input.y], 0, [], [[input.y: conflicts: 4 shift/reduce ]]) AT_CLEANUP ## ---------------------------- ## ## %no-default-prec with %prec ## ## ---------------------------- ## AT_SETUP([%no-default-prec with %prec]) AT_DATA([[input.y]], [[%left '+' %left '*' %% %no-default-prec; e: e '+' e %prec '+' | e '*' e %prec '*' | '0' ; ]]) AT_CHECK([bison -o input.c input.y]) AT_CLEANUP ## ---------------- ## ## %default-prec ## ## ---------------- ## AT_SETUP([%default-prec]) AT_DATA([[input.y]], [[%left '+' %left '*' %% %default-prec; e: e '+' e | e '*' e | '0' ; ]]) AT_CHECK([bison -o input.c input.y]) AT_CLEANUP ## ---------------------------------------------- ## ## Unreachable States After Conflict Resolution. ## ## ---------------------------------------------- ## AT_SETUP([[Unreachable States After Conflict Resolution]]) # If conflict resolution makes states unreachable, remove those states, report # rules that are then unused, and don't report conflicts in those states. Test # what happens when a nonterminal becomes useless as a result of state removal # since that causes lalr.o's goto map to be rewritten. AT_DATA([[input.y]], [[%output "input.c" %left 'a' %% start: resolved_conflict 'a' reported_conflicts 'a' ; /* S/R conflict resolved as shift, so the state with item * (resolved_conflict: 'a' . unreachable1) and all it transition successors are * unreachable, and the associated production is useless. */ resolved_conflict: 'a' unreachable1 | %prec 'a' ; /* S/R conflict that need not be reported since it is unreachable because of * the previous conflict resolution. Nonterminal unreachable1 and all its * productions are useless. */ unreachable1: 'a' unreachable2 | ; /* Likewise for a R/R conflict and nonterminal unreachable2. */ unreachable2: | ; /* Make sure remaining S/R and R/R conflicts are still reported correctly even * when their states are renumbered due to state removal. */ reported_conflicts: 'a' | 'a' | ; ]]) AT_CHECK([[bison --report=all input.y]], 0, [], [[input.y: conflicts: 1 shift/reduce, 1 reduce/reduce input.y:12.5-20: warning: rule never reduced because of conflicts: resolved_conflict: 'a' unreachable1 input.y:20.5-20: warning: rule never reduced because of conflicts: unreachable1: 'a' unreachable2 input.y:21.4: warning: rule never reduced because of conflicts: unreachable1: /* empty */ input.y:25.13: warning: rule never reduced because of conflicts: unreachable2: /* empty */ input.y:25.16: warning: rule never reduced because of conflicts: unreachable2: /* empty */ input.y:31.5-7: warning: rule never reduced because of conflicts: reported_conflicts: 'a' input.y:32.4: warning: rule never reduced because of conflicts: reported_conflicts: /* empty */ ]]) AT_CHECK([[cat input.output]], 0, [[Rules never reduced 2 resolved_conflict: 'a' unreachable1 4 unreachable1: 'a' unreachable2 5 | /* empty */ 6 unreachable2: /* empty */ 7 | /* empty */ 9 reported_conflicts: 'a' 10 | /* empty */ State 4 conflicts: 1 shift/reduce State 5 conflicts: 1 reduce/reduce Grammar 0 $accept: start $end 1 start: resolved_conflict 'a' reported_conflicts 'a' 2 resolved_conflict: 'a' unreachable1 3 | /* empty */ 4 unreachable1: 'a' unreachable2 5 | /* empty */ 6 unreachable2: /* empty */ 7 | /* empty */ 8 reported_conflicts: 'a' 9 | 'a' 10 | /* empty */ Terminals, with rules where they appear $end (0) 0 'a' (97) 1 2 4 8 9 error (256) Nonterminals, with rules where they appear $accept (4) on left: 0 start (5) on left: 1, on right: 0 resolved_conflict (6) on left: 2 3, on right: 1 unreachable1 (7) on left: 4 5, on right: 2 unreachable2 (8) on left: 6 7, on right: 4 reported_conflicts (9) on left: 8 9 10, on right: 1 state 0 0 $accept: . start $end 1 start: . resolved_conflict 'a' reported_conflicts 'a' 2 resolved_conflict: . 'a' unreachable1 3 | . ['a'] $default reduce using rule 3 (resolved_conflict) start go to state 1 resolved_conflict go to state 2 Conflict between rule 3 and token 'a' resolved as reduce (%left 'a'). state 1 0 $accept: start . $end $end shift, and go to state 3 state 2 1 start: resolved_conflict . 'a' reported_conflicts 'a' 'a' shift, and go to state 4 state 3 0 $accept: start $end . $default accept state 4 1 start: resolved_conflict 'a' . reported_conflicts 'a' 8 reported_conflicts: . 'a' 9 | . 'a' 10 | . ['a'] 'a' shift, and go to state 5 'a' [reduce using rule 10 (reported_conflicts)] reported_conflicts go to state 6 state 5 8 reported_conflicts: 'a' . ['a'] 9 | 'a' . ['a'] 'a' reduce using rule 8 (reported_conflicts) 'a' [reduce using rule 9 (reported_conflicts)] $default reduce using rule 8 (reported_conflicts) state 6 1 start: resolved_conflict 'a' reported_conflicts . 'a' 'a' shift, and go to state 7 state 7 1 start: resolved_conflict 'a' reported_conflicts 'a' . $default reduce using rule 1 (start) ]]) AT_CLEANUP ## ------------------------------------------------------------ ## ## Solved conflicts report for multiple reductions in a state. ## ## ------------------------------------------------------------ ## AT_SETUP([[Solved conflicts report for multiple reductions in a state]]) # Used to lose earlier solved conflict messages even within a single S/R/R. AT_DATA([[input.y]], [[%left 'a' %right 'b' %right 'c' %right 'd' %% start: 'a' | empty_a 'a' | 'b' | empty_b 'b' | 'c' | empty_c1 'c' | empty_c2 'c' | empty_c3 'c' ; empty_a: %prec 'a' ; empty_b: %prec 'b' ; empty_c1: %prec 'c' ; empty_c2: %prec 'c' ; empty_c3: %prec 'd' ; ]]) AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore]) AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0, [[state 0 0 $accept: . start $end 1 start: . 'a' 2 | . empty_a 'a' 3 | . 'b' 4 | . empty_b 'b' 5 | . 'c' 6 | . empty_c1 'c' 7 | . empty_c2 'c' 8 | . empty_c3 'c' 9 empty_a: . ['a'] 10 empty_b: . [] 11 empty_c1: . [] 12 empty_c2: . [] 13 empty_c3: . ['c'] 'b' shift, and go to state 1 'c' reduce using rule 13 (empty_c3) $default reduce using rule 9 (empty_a) start go to state 2 empty_a go to state 3 empty_b go to state 4 empty_c1 go to state 5 empty_c2 go to state 6 empty_c3 go to state 7 Conflict between rule 9 and token 'a' resolved as reduce (%left 'a'). Conflict between rule 10 and token 'b' resolved as shift (%right 'b'). Conflict between rule 11 and token 'c' resolved as shift (%right 'c'). Conflict between rule 12 and token 'c' resolved as shift (%right 'c'). Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd'). state 1 ]]) AT_CLEANUP ## ------------------------------------------------------------ ## ## %nonassoc error actions for multiple reductions in a state. ## ## ------------------------------------------------------------ ## # Used to abort when trying to resolve conflicts as %nonassoc error actions for # multiple reductions in a state. # For a %nonassoc error action token, used to print the first remaining # reduction on that token without brackets. AT_SETUP([[%nonassoc error actions for multiple reductions in a state]]) AT_DATA([[input.y]], [[%nonassoc 'a' 'b' 'c' %% start: 'a' | empty_a 'a' | 'b' | empty_b 'b' | 'c' | empty_c1 'c' | empty_c2 'c' | empty_c3 'c' ; empty_a: %prec 'a' ; empty_b: %prec 'b' ; empty_c1: %prec 'c' ; empty_c2: %prec 'c' ; empty_c3: %prec 'c' ; ]]) AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore]) AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0, [[state 0 0 $accept: . start $end 1 start: . 'a' 2 | . empty_a 'a' 3 | . 'b' 4 | . empty_b 'b' 5 | . 'c' 6 | . empty_c1 'c' 7 | . empty_c2 'c' 8 | . empty_c3 'c' 9 empty_a: . [] 10 empty_b: . [] 11 empty_c1: . [] 12 empty_c2: . ['c'] 13 empty_c3: . ['c'] 'a' error (nonassociative) 'b' error (nonassociative) 'c' error (nonassociative) 'c' [reduce using rule 12 (empty_c2)] 'c' [reduce using rule 13 (empty_c3)] start go to state 1 empty_a go to state 2 empty_b go to state 3 empty_c1 go to state 4 empty_c2 go to state 5 empty_c3 go to state 6 Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a'). Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 'b'). Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 'c'). state 1 ]]) AT_CLEANUP