# Exercising Bison on conflicts. -*- Autotest -*-
# Copyright (C) 2002-2005, 2007, 2009-2010 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 3 of the License, 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, see .
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_BISON_CHECK([-o input.c input.y], 0, [],
[[input.y:4.9: warning: rule useless in parser due to 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_BISON_CHECK([-o input.c input.y])
AT_COMPILE([input])
AT_PARSER_CHECK([./input '0<0'])
AT_PARSER_CHECK([./input '0<0<0'], [1], [],
[syntax error, unexpected '<'
])
AT_PARSER_CHECK([./input '0>0'])
AT_PARSER_CHECK([./input '0>0>0'], [1], [],
[syntax error, unexpected '>'
])
AT_PARSER_CHECK([./input '0<0>0'], [1], [],
[syntax error, unexpected '>'
])
# We must disable default reductions in inconsistent states in order to
# have an explicit list of all expected tokens. (However, unless we use
# canonical LR, lookahead sets are merged for different left contexts,
# so it is still possible to have extra incorrect tokens in the expected
# list. That just doesn't happen to be a problem for this test case.)
AT_BISON_CHECK([-Dlr.default-reductions=consistent -o input.c input.y])
AT_COMPILE([input])
AT_PARSER_CHECK([./input '0<0'])
AT_PARSER_CHECK([./input '0<0<0'], [1], [],
[syntax error, unexpected '<', expecting $end
])
AT_PARSER_CHECK([./input '0>0'])
AT_PARSER_CHECK([./input '0>0>0'], [1], [],
[syntax error, unexpected '>', expecting $end
])
AT_PARSER_CHECK([./input '0<0>0'], [1], [],
[syntax error, unexpected '>', expecting $end
])
AT_CLEANUP
## -------------------------------------- ##
## %error-verbose and consistent errors. ##
## -------------------------------------- ##
AT_SETUP([[%error-verbose and consistent errors]])
m4_pushdef([AT_CONSISTENT_ERRORS_CHECK], [
AT_BISON_CHECK([$1[ -o input.c input.y]])
AT_COMPILE([[input]])
m4_pushdef([AT_EXPECTING], [m4_if($3, [ab], [[, expecting 'a' or 'b']],
$3, [a], [[, expecting 'a']],
$3, [b], [[, expecting 'b']])])
AT_PARSER_CHECK([[./input]], [[1]], [],
[[syntax error, unexpected ]$2[]AT_EXPECTING[
]])
m4_popdef([AT_EXPECTING])
])
AT_DATA_GRAMMAR([input.y],
[[%code {
#include
#include
int yylex (void);
void yyerror (char const *);
#define USE(Var)
}
%error-verbose
// The point isn't to test IELR here, but state merging happens to
// complicate the example.
%define lr.type ielr
%nonassoc 'a'
// If yylval=0 here, then we know that the 'a' destructor is being
// invoked incorrectly for the 'b' set in the semantic action below.
// All 'a' tokens are returned by yylex, which sets yylval=1.
%destructor {
if (!$$)
fprintf (stderr, "Wrong destructor.\n");
} 'a'
%%
// The lookahead assigned by the semantic action isn't needed before
// either error action is encountered. In a previous version of Bison,
// this was a problem as it meant yychar was not translated into yytoken
// before either error action. The second error action thus invoked a
// destructor that it selected according to the incorrect yytoken. The
// first error action would have reported an incorrect unexpected token
// except that, due to another bug, the unexpected token is not reported
// at all because the error action is the default action in a consistent
// state. That bug still needs to be fixed.
start: error-reduce consistent-error 'a' { USE ($3); } ;
error-reduce:
'a' 'a' consistent-reduction consistent-error 'a'
{ USE (($1, $2, $5)); }
| 'a' error
{ USE ($1); }
;
consistent-reduction: /*empty*/ {
assert (yychar == YYEMPTY);
yylval = 0;
yychar = 'b';
} ;
consistent-error:
'a' { USE ($1); }
| /*empty*/ %prec 'a'
;
// Provide another context in which all rules are useful so that this
// test case looks a little more realistic.
start: 'b' consistent-error 'b' ;
%%
int
yylex (void)
{
static char const *input = "aa";
yylval = 1;
return *input++;
}
void
yyerror (char const *msg)
{
fprintf (stderr, "%s\n", msg);
}
int
main (void)
{
return yyparse ();
}
]])
# See comments in grammar for why this test doesn't succeed.
AT_XFAIL_IF([[:]])
AT_CONSISTENT_ERRORS_CHECK([], [['b']], [[none]])
AT_CONSISTENT_ERRORS_CHECK([[-Dlr.default-reductions=consistent]],
[['b']], [[none]])
# Canonical LR doesn't foresee the error for 'a'!
AT_CONSISTENT_ERRORS_CHECK([[-Dlr.default-reductions=accepting]],
[[$end]], [[a]])
AT_CONSISTENT_ERRORS_CHECK([[-Flr.type=canonical-lr]], [[$end]], [[a]])
m4_popdef([AT_CONSISTENT_ERRORS_CHECK])
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_BISON_CHECK([-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
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_BISON_CHECK([-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
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_BISON_CHECK([-o input.c --report=all input.y], 0, [],
[[input.y: conflicts: 1 reduce/reduce
input.y:4.6-8: warning: rule useless in parser due to conflicts: id: '0'
]])
# Check the contents of the report.
AT_CHECK([cat input.output], [],
[[Rules useless in parser due to conflicts
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_BISON_CHECK([-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_BISON_CHECK([-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_BISON_CHECK([-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_BISON_CHECK([-o input.c input.y], 1, [],
[input.y: conflicts: 1 reduce/reduce
input.y: expected 0 reduce/reduce conflicts
])
AT_CLEANUP
## ------------------------- ##
## %prec with user strings. ##
## ------------------------- ##
AT_SETUP([%prec with user string])
AT_DATA([[input.y]],
[[%%
exp:
"foo" %prec "foo"
;
]])
AT_BISON_CHECK([-o input.c input.y])
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_BISON_CHECK([-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_BISON_CHECK([-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_BISON_CHECK([-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 reduce, 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_BISON_CHECK([[--report=all input.y]], 0, [],
[[input.y: conflicts: 1 shift/reduce, 1 reduce/reduce
input.y:12.5-20: warning: rule useless in parser due to conflicts: resolved_conflict: 'a' unreachable1
input.y:20.5-20: warning: rule useless in parser due to conflicts: unreachable1: 'a' unreachable2
input.y:21.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */
input.y:25.13: warning: rule useless in parser due to conflicts: unreachable2: /* empty */
input.y:25.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */
input.y:31.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a'
input.y:32.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */
]])
AT_CHECK([[cat input.output]], 0,
[[Rules useless in parser due to conflicts
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_DATA([[input-keep.y]],
[[%define lr.keep-unreachable-states
]])
AT_CHECK([[cat input.y >> input-keep.y]])
AT_BISON_CHECK([[input-keep.y]], 0, [],
[[input-keep.y: conflicts: 2 shift/reduce, 2 reduce/reduce
input-keep.y:22.4: warning: rule useless in parser due to conflicts: unreachable1: /* empty */
input-keep.y:26.16: warning: rule useless in parser due to conflicts: unreachable2: /* empty */
input-keep.y:32.5-7: warning: rule useless in parser due to conflicts: reported_conflicts: 'a'
input-keep.y:33.4: warning: rule useless in parser due to conflicts: reported_conflicts: /* empty */
]])
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_BISON_CHECK([[--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_BISON_CHECK([[--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