path: root/tests/sets.at

# 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 <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