| # Exercising Bison Grammar Sets. -*- Autotest -*- |
| |
| # Copyright (C) 2001-2002, 2005, 2007, 2009-2015, 2018-2019 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 <http://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). |
| # |
| # http://lists.gnu.org/archive/html/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: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]], [], [], |
| [[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, nvars = 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" |
| |
| |
| Non terminals |
| ------------- |
| |
| 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]], [], [], |
| [[Reduced Grammar |
| |
| ntokens = 10, nvars = 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" |
| |
| |
| Non terminals |
| ------------- |
| |
| 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 |
