1 # Exercising Bison Grammar Sets. -*- Autotest -*-
3 # Copyright (C) 2001-2002, 2005, 2007, 2009-2015, 2018-2021 Free
4 # Software Foundation, Inc.
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.
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.
16 # You should have received a copy of the GNU General Public License
17 # along with this program. If not, see <https://www.gnu.org/licenses/>.
20 AT_BANNER([[Grammar Sets (Firsts etc.).]])
29 # At some point, nullable had been smoking grass, and managed to say:
31 # Entering set_nullable
39 e: 'e' | /* Nothing */;
42 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
43 AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
72 ## ---------------- ##
74 ## ---------------- ##
76 # TC was once broken during a massive 'simplification' of the code.
77 # It resulted in bison dumping core on the following grammar (the
78 # computation of FIRSTS uses TC). It managed to produce a pretty
109 # instead of that below.
111 AT_SETUP([Broken Closure])
125 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
127 AT_CHECK([[sed -n 's/[ ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
128 [[RTC: Firsts Output BEGIN
142 RTC: Firsts Output END
171 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
172 AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
222 # In some weird cases Bison could compute an incorrect final state
223 # number. This happens only if the $end token is used in the user
224 # grammar, which is a very suspicious accidental feature introduced as
225 # a side effect of allowing the user to name $end using '%token END 0
240 AT_BISON_CHECK([[-v -o input.c input.y]])
242 # Get the final state in the parser.
243 AT_CHECK([[sed -n 's/.*define YYFINAL *\([0-9][0-9]*\)/final state \1/p' input.c]],
247 # Get the final state in the report, from the "accept" action..
265 ## ----------------- ##
266 ## Build relations. ##
267 ## ----------------- ##
269 AT_SETUP([Build relations])
271 # The "includes" relation [DeRemer 1982] is between gotos, so of
272 # course, for a given goto, there cannot be more that ngotos (number
273 # of gotos) images. But we manipulate the set of images of a goto as
274 # a list, without checking that an image was not already introduced.
275 # So we can "register" way more images than ngotos, leading to a crash
276 # (heap buffer overflow).
278 # https://lists.gnu.org/r/bug-bison/2019-03/msg00007.html
282 expr: term | term | term | term | term | term
286 AT_BISON_CHECK([[-fcaret input.y]], [], [],
287 [[input.y: warning: 5 reduce/reduce conflicts [-Wconflicts-rr]
288 input.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
289 input.y:2.14-17: warning: rule useless in parser due to conflicts [-Wother]
290 2 | expr: term | term | term | term | term | term
292 input.y:2.21-24: warning: rule useless in parser due to conflicts [-Wother]
293 2 | expr: term | term | term | term | term | term
295 input.y:2.28-31: warning: rule useless in parser due to conflicts [-Wother]
296 2 | expr: term | term | term | term | term | term
298 input.y:2.35-38: warning: rule useless in parser due to conflicts [-Wother]
299 2 | expr: term | term | term | term | term | term
301 input.y:2.42-45: warning: rule useless in parser due to conflicts [-Wother]
302 2 | expr: term | term | term | term | term | term
309 ## ----------------- ##
310 ## Reduced Grammar. ##
311 ## ----------------- ##
313 # Check information about the grammar, once reduced.
315 AT_SETUP([Reduced Grammar])
319 expr: expr "+" term | term
320 term: term "*" fact | fact
325 AT_BISON_CHECK([[--trace=grammar -o input.c input.y]], [], [],
326 [[bison (GNU Bison) ]AT_PACKAGE_VERSION[
327 input.y: warning: 1 nonterminal useless in grammar [-Wother]
328 input.y: warning: 1 rule useless in grammar [-Wother]
329 input.y:4.1-7: warning: nonterminal useless in grammar: useless [-Wother]
332 ntokens = 7, nnterms = 4, nsyms = 11, nrules = 6, nritems = 17
337 Value Sprec Sassoc Tag
360 Num (Prec, Assoc, Useful, UselessChain) Lhs -> (Ritem Range) Rhs
361 0 ( 0, 0, t, f) 7 -> ( 0- 1) 8 0
362 1 ( 0, 0, t, f) 8 -> ( 3- 5) 8 3 9
363 2 ( 0, 0, t, t) 8 -> ( 7- 7) 9
364 3 ( 0, 0, t, f) 9 -> ( 9-11) 9 4 10
365 4 ( 0, 0, t, t) 9 -> (13-13) 10
366 5 ( 0, 0, t, t) 10 -> (17-17) 6
367 6 ( 0, 0, f, t) 11 -> (15-15) 5
374 1 expr: expr "+" term
376 3 term: term "*" fact
382 reduced input.y defines 7 terminals, 4 nonterminals, and 6 productions.
388 ## ------------------------------------- ##
389 ## Reduced Grammar with prec and assoc. ##
390 ## ------------------------------------- ##
392 # Check information about the grammar, once reduced.
394 AT_SETUP([Reduced Grammar with prec and assoc])
412 AT_BISON_CHECK([[--trace=grammar -o input.c input.y]], [], [],
413 [[bison (GNU Bison) ]AT_PACKAGE_VERSION[
416 ntokens = 10, nnterms = 2, nsyms = 12, nrules = 8, nritems = 29
421 Value Sprec Sassoc Tag
445 Num (Prec, Assoc, Useful, UselessChain) Lhs -> (Ritem Range) Rhs
446 0 ( 0, 0, t, f) 10 -> ( 0- 1) 11 0
447 1 ( 1, 3, t, f) 11 -> ( 3- 5) 11 3 11
448 2 ( 1, 3, t, f) 11 -> ( 7- 9) 11 4 11
449 3 ( 2, 2, t, f) 11 -> (11-13) 11 5 11
450 4 ( 2, 2, t, f) 11 -> (15-17) 11 6 11
451 5 ( 3, 1, t, f) 11 -> (19-21) 11 7 11
452 6 ( 3, 1, t, f) 11 -> (23-25) 11 8 11
453 7 ( 0, 0, t, t) 11 -> (27-27) 9
469 reduced input.y defines 10 terminals, 2 nonterminals, and 8 productions.