# Exercising Bison Grammar Sets. -*- Autotest -*-
# Copyright (C) 2001-2002, 2005, 2007, 2009-2015, 2018-2021 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 <https://www.gnu.org/licenses/>.
AT_BANNER([[Grammar Sets (Firsts etc.).]])
## ---------- ##
## Nullable. ##
## ---------- ##
AT_SETUP([Nullable])
# At some point, nullable had been smoking grass, and managed to say:
#
# Entering set_nullable
# NULLABLE
# 'e': yes
# (null): no
# ...
AT_DATA([[input.y]],
[[%%
e: 'e' | /* Nothing */;
]])
AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
[[DERIVES
$accept derives
0 e $end
e derives
1 'e'
2 %empty
NULLABLE
$accept: no
e: yes
FIRSTS
$accept firsts
$accept
e
e firsts
e
FDERIVES
$accept derives
0 e $end
1 'e'
2 %empty
e derives
1 'e'
2 %empty
]])
AT_CLEANUP
## ---------------- ##
## Broken Closure. ##
## ---------------- ##
# TC was once broken during a massive 'simplification' of the code.
# It resulted in bison dumping core on the following grammar (the
# computation of FIRSTS uses TC). It managed to produce a pretty
# exotic closure:
#
# TC: Input
#
# 01234567
# +--------+
# 0| 1 |
# 1| 1 |
# 2| 1 |
# 3| 1 |
# 4| 1 |
# 5| 1 |
# 6| 1|
# 7| |
# +--------+
#
# TC: Output
#
# 01234567
# +--------+
# 0| 1 |
# 1| 111 |
# 2| 111 |
# 3| 1111 |
# 4| 111 1 |
# 5| 111 1 |
# 6| 111 1|
# 7| 111 |
# +--------+
#
# instead of that below.
AT_SETUP([Broken Closure])
AT_DATA([input.y],
[[%%
a: b;
b: c;
c: d;
d: e;
e: f;
f: g;
g: h;
h: 'h';
]])
AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
AT_CHECK([[sed -n 's/[ ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
[[RTC: Firsts Output BEGIN
012345678
.---------.
0|111111111|
1| 11111111|
2| 1111111|
3| 111111|
4| 11111|
5| 1111|
6| 111|
7| 11|
8| 1|
`---------'
RTC: Firsts Output END
]])
AT_CLEANUP
## -------- ##
## Firsts. ##
## -------- ##
AT_SETUP([Firsts])
AT_DATA([input.y],
[[%nonassoc '<' '>'
%left '+' '-'
%right '^' '='
%%
exp:
exp '<' exp
| exp '>' exp
| exp '+' exp
| exp '-' exp
| exp '^' exp
| exp '=' exp
| "exp"
;
]])
AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
[[DERIVES
$accept derives
0 exp $end
exp derives
1 exp '<' exp
2 exp '>' exp
3 exp '+' exp
4 exp '-' exp
5 exp '^' exp
6 exp '=' exp
7 "exp"
NULLABLE
$accept: no
exp: no
FIRSTS
$accept firsts
$accept
exp
exp firsts
exp
FDERIVES
$accept derives
0 exp $end
1 exp '<' exp
2 exp '>' exp
3 exp '+' exp
4 exp '-' exp
5 exp '^' exp
6 exp '=' exp
7 "exp"
exp derives
1 exp '<' exp
2 exp '>' exp
3 exp '+' exp
4 exp '-' exp
5 exp '^' exp
6 exp '=' exp
7 "exp"
]])
AT_CLEANUP
## -------- ##
## Accept. ##
## -------- ##
# In some weird cases Bison could compute an incorrect final state
# number. This happens only if the $end token is used in the user
# grammar, which is a very suspicious accidental feature introduced as
# a side effect of allowing the user to name $end using '%token END 0
# "end of file"'.
AT_SETUP([Accept])
AT_DATA([input.y],
[[%token END 0
%%
input:
'a'
| '(' input ')'
| '(' error END
;
]])
AT_BISON_CHECK([[-v -o input.c input.y]])
# Get the final state in the parser.
AT_CHECK([[sed -n 's/.*define YYFINAL *\([0-9][0-9]*\)/final state \1/p' input.c]],
0, [stdout])
mv stdout expout
# Get the final state in the report, from the "accept" action..
AT_CHECK([sed -n '
/^State \(.*\)/{
s//final state \1/
x
}
/ accept/{
x
p
q
}
' input.output],
0, [expout])
AT_CLEANUP
## ----------------- ##
## Build relations. ##
## ----------------- ##
AT_SETUP([Build relations])
# The "includes" relation [DeRemer 1982] is between gotos, so of
# course, for a given goto, there cannot be more that ngotos (number
# of gotos) images. But we manipulate the set of images of a goto as
# a list, without checking that an image was not already introduced.
# So we can "register" way more images than ngotos, leading to a crash
# (heap buffer overflow).
#
# https://lists.gnu.org/r/bug-bison/2019-03/msg00007.html
AT_DATA([input.y],
[[%%
expr: term | term | term | term | term | term
term: 'n'
]])
AT_BISON_CHECK([[-fcaret input.y]], [], [],
[[input.y: warning: 5 reduce/reduce conflicts [-Wconflicts-rr]
input.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
input.y:2.14-17: warning: rule useless in parser due to conflicts [-Wother]
2 | expr: term | term | term | term | term | term
| ^~~~
input.y:2.21-24: warning: rule useless in parser due to conflicts [-Wother]
2 | expr: term | term | term | term | term | term
| ^~~~
input.y:2.28-31: warning: rule useless in parser due to conflicts [-Wother]
2 | expr: term | term | term | term | term | term
| ^~~~
input.y:2.35-38: warning: rule useless in parser due to conflicts [-Wother]
2 | expr: term | term | term | term | term | term
| ^~~~
input.y:2.42-45: warning: rule useless in parser due to conflicts [-Wother]
2 | expr: term | term | term | term | term | term
| ^~~~
]])
AT_CLEANUP
## ----------------- ##
## Reduced Grammar. ##
## ----------------- ##
# Check information about the grammar, once reduced.
AT_SETUP([Reduced Grammar])
AT_DATA([input.y],
[[%%
expr: expr "+" term | term
term: term "*" fact | fact
useless: "useless"
fact: "num"
]])
AT_BISON_CHECK([[--trace=grammar -o input.c input.y]], [], [],
[[bison (GNU Bison) ]AT_PACKAGE_VERSION[
input.y: warning: 1 nonterminal useless in grammar [-Wother]
input.y: warning: 1 rule useless in grammar [-Wother]
input.y:4.1-7: warning: nonterminal useless in grammar: useless [-Wother]
Reduced Grammar
ntokens = 7, nnterms = 4, nsyms = 11, nrules = 6, nritems = 17
Tokens
------
Value Sprec Sassoc Tag
0 0 0 $end
1 0 0 error
2 0 0 $undefined
3 0 0 "+"
4 0 0 "*"
5 0 0 "useless"
6 0 0 "num"
Nonterminals
------------
Value Tag
7 $accept
8 expr
9 term
10 fact
Rules
-----
Num (Prec, Assoc, Useful, UselessChain) Lhs -> (Ritem Range) Rhs
0 ( 0, 0, t, f) 7 -> ( 0- 1) 8 0
1 ( 0, 0, t, f) 8 -> ( 3- 5) 8 3 9
2 ( 0, 0, t, t) 8 -> ( 7- 7) 9
3 ( 0, 0, t, f) 9 -> ( 9-11) 9 4 10
4 ( 0, 0, t, t) 9 -> (13-13) 10
5 ( 0, 0, t, t) 10 -> (17-17) 6
6 ( 0, 0, f, t) 11 -> (15-15) 5
Rules interpreted
-----------------
0 $accept: expr $end
1 expr: expr "+" term
2 expr: term
3 term: term "*" fact
4 term: fact
5 fact: "num"
6 useless: "useless"
reduced input.y defines 7 terminals, 4 nonterminals, and 6 productions.
]])
AT_CLEANUP
## ------------------------------------- ##
## Reduced Grammar with prec and assoc. ##
## ------------------------------------- ##
# Check information about the grammar, once reduced.
AT_SETUP([Reduced Grammar with prec and assoc])
AT_DATA([input.y],
[[%nonassoc '<' '>'
%left '+' '-'
%right '^' '='
%%
exp:
exp '<' exp
| exp '>' exp
| exp '+' exp
| exp '-' exp
| exp '^' exp
| exp '=' exp
| "exp"
;
]])
AT_BISON_CHECK([[--trace=grammar -o input.c input.y]], [], [],
[[bison (GNU Bison) ]AT_PACKAGE_VERSION[
Reduced Grammar
ntokens = 10, nnterms = 2, nsyms = 12, nrules = 8, nritems = 29
Tokens
------
Value Sprec Sassoc Tag
0 0 0 $end
1 0 0 error
2 0 0 $undefined
3 1 3 '<'
4 1 3 '>'
5 2 2 '+'
6 2 2 '-'
7 3 1 '^'
8 3 1 '='
9 0 0 "exp"
Nonterminals
------------
Value Tag
10 $accept
11 exp
Rules
-----
Num (Prec, Assoc, Useful, UselessChain) Lhs -> (Ritem Range) Rhs
0 ( 0, 0, t, f) 10 -> ( 0- 1) 11 0
1 ( 1, 3, t, f) 11 -> ( 3- 5) 11 3 11
2 ( 1, 3, t, f) 11 -> ( 7- 9) 11 4 11
3 ( 2, 2, t, f) 11 -> (11-13) 11 5 11
4 ( 2, 2, t, f) 11 -> (15-17) 11 6 11
5 ( 3, 1, t, f) 11 -> (19-21) 11 7 11
6 ( 3, 1, t, f) 11 -> (23-25) 11 8 11
7 ( 0, 0, t, t) 11 -> (27-27) 9
Rules interpreted
-----------------
0 $accept: exp $end
1 exp: exp '<' exp
2 exp: exp '>' exp
3 exp: exp '+' exp
4 exp: exp '-' exp
5 exp: exp '^' exp
6 exp: exp '=' exp
7 exp: "exp"
reduced input.y defines 10 terminals, 2 nonterminals, and 8 productions.
]])
AT_CLEANUP