# Exercising Bison Grammar Sets. -*- Autotest -*- # Copyright (C) 2001-2002, 2005, 2007, 2009-2015, 2018-2022 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([[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