tests/sets.at

   1 # Exercising Bison Grammar Sets.                      -*- Autotest -*-
   2
   3 # Copyright (C) 2001-2002, 2005, 2007, 2009-2011 Free Software
   4 # Foundation, Inc.
   5
   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.
  10 #
  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.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18
  19
  20 # AT_EXTRACT_SETS(INPUT, OUTPUT)
  21 # ------------------------------
  22 # Extract the information about the grammar sets from a bison
  23 # trace output (INPUT), and save it in OUTPUT.
  24 # And remember, there is no alternation in portable sed.
  25 m4_define([AT_EXTRACT_SETS],
  26 [AT_DATA([extract.sed],
  27 [[#n
  28 /^NULLABLE$/ {
  29    :null
  30    p
  31    n
  32    /^[   ]*$/ !b null
  33 }
  34 /^FIRSTS$/ {
  35    :firsts
  36    p
  37    n
  38    /^[   ]*$/ !b firsts
  39 }
  40 /^FDERIVES$/ {
  41    :fderiv
  42    p
  43    n
  44    /^[   ]*$/ !b fderiv
  45 }
  46 /^DERIVES$/ {
  47    :deriv
  48    p
  49    n
  50    /^[   ]*$/ !b deriv
  51 }
  52 ]])
  53 AT_CHECK([sed -f extract.sed $1], 0, [stdout])
  54 AT_CHECK([mv stdout $2])
  55 ])
  56
  57
  58
  59 AT_BANNER([[Grammar Sets (Firsts etc.).]])
  60
  61
  62 ## ---------- ##
  63 ## Nullable.  ##
  64 ## ---------- ##
  65
  66 AT_SETUP([Nullable])
  67
  68 # At some point, nullable had been smoking grass, and managed to say:
  69 #
  70 # Entering set_nullable
  71 # NULLABLE
  72 #         'e': yes
  73 #         (null): no
  74 # ...
  75
  76 AT_DATA([[input.y]],
  77 [[%%
  78 e: 'e' | /* Nothing */;
  79 ]])
  80
  81 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
  82 AT_EXTRACT_SETS([stderr], [sets])
  83 AT_CHECK([[cat sets]], [],
  84 [[DERIVES
  85         $accept derives
  86                   0  e $end
  87         e derives
  88                   1  'e'
  89                   2  /* empty */
  90 NULLABLE
  91         $accept: no
  92         e: yes
  93 FIRSTS
  94         $accept firsts
  95                 $accept
  96                 e
  97         e firsts
  98                 e
  99 FDERIVES
 100         $accept derives
 101                   0  e $end
 102                   1  'e'
 103                   2  /* empty */
 104         e derives
 105                   1  'e'
 106                   2  /* empty */
 107 ]])
 108
 109 AT_CLEANUP
 110
 111
 112 ## ---------------- ##
 113 ## Broken Closure.  ##
 114 ## ---------------- ##
 115
 116 # TC was once broken during a massive `simplification' of the code.
 117 # It resulted in bison dumping core on the following grammar (the
 118 # computation of FIRSTS uses TC).  It managed to produce a pretty
 119 # exotic closure:
 120 #
 121 # TC: Input
 122 #
 123 #    01234567
 124 #   +--------+
 125 #  0| 1      |
 126 #  1|  1     |
 127 #  2|   1    |
 128 #  3|    1   |
 129 #  4|     1  |
 130 #  5|      1 |
 131 #  6|       1|
 132 #  7|        |
 133 #   +--------+
 134 #
 135 # TC: Output
 136 #
 137 #    01234567
 138 #   +--------+
 139 #  0| 1      |
 140 #  1| 111    |
 141 #  2| 111    |
 142 #  3| 1111   |
 143 #  4| 111 1  |
 144 #  5| 111  1 |
 145 #  6| 111   1|
 146 #  7| 111    |
 147 #   +--------+
 148 #
 149 # instead of that below.
 150
 151 AT_SETUP([Broken Closure])
 152
 153 AT_DATA([input.y],
 154 [[%%
 155 a: b;
 156 b: c;
 157 c: d;
 158 d: e;
 159 e: f;
 160 f: g;
 161 g: h;
 162 h: 'h';
 163 ]])
 164
 165 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 166
 167 AT_CHECK([[sed -n 's/[   ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
 168 [[RTC: Firsts Output BEGIN
 169
 170    012345678
 171   .---------.
 172  0|111111111|
 173  1| 11111111|
 174  2|  1111111|
 175  3|   111111|
 176  4|    11111|
 177  5|     1111|
 178  6|      111|
 179  7|       11|
 180  8|        1|
 181   `---------'
 182 RTC: Firsts Output END
 183 ]])
 184
 185 AT_CLEANUP
 186
 187
 188
 189 ## -------- ##
 190 ## Firsts.  ##
 191 ## -------- ##
 192
 193 AT_SETUP([Firsts])
 194
 195 AT_DATA([input.y],
 196 [[%nonassoc '<' '>'
 197 %left '+' '-'
 198 %right '^' '='
 199 %%
 200 exp:
 201    exp '<' exp
 202  | exp '>' exp
 203  | exp '+' exp
 204  | exp '-' exp
 205  | exp '^' exp
 206  | exp '=' exp
 207  | "exp"
 208  ;
 209 ]])
 210
 211 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 212 AT_EXTRACT_SETS([stderr], [sets])
 213 AT_CHECK([[cat sets]], [],
 214 [[DERIVES
 215         $accept derives
 216                   0  exp $end
 217         exp derives
 218                   1  exp '<' exp
 219                   2  exp '>' exp
 220                   3  exp '+' exp
 221                   4  exp '-' exp
 222                   5  exp '^' exp
 223                   6  exp '=' exp
 224                   7  "exp"
 225 NULLABLE
 226         $accept: no
 227         exp: no
 228 FIRSTS
 229         $accept firsts
 230                 $accept
 231                 exp
 232         exp firsts
 233                 exp
 234 FDERIVES
 235         $accept derives
 236                   0  exp $end
 237                   1  exp '<' exp
 238                   2  exp '>' exp
 239                   3  exp '+' exp
 240                   4  exp '-' exp
 241                   5  exp '^' exp
 242                   6  exp '=' exp
 243                   7  "exp"
 244         exp derives
 245                   1  exp '<' exp
 246                   2  exp '>' exp
 247                   3  exp '+' exp
 248                   4  exp '-' exp
 249                   5  exp '^' exp
 250                   6  exp '=' exp
 251                   7  "exp"
 252 ]])
 253
 254 AT_CLEANUP
 255
 256
 257
 258
 259 ## -------- ##
 260 ## Accept.  ##
 261 ## -------- ##
 262
 263 # In some weird cases Bison could compute an incorrect final state
 264 # number.  This happens only if the $end token is used in the user
 265 # grammar, which is a very suspicious accidental feature introduced as
 266 # a side effect of allowing the user to name $end using `%token END 0
 267 # "end of file"'.
 268
 269 AT_SETUP([Accept])
 270
 271 AT_DATA([input.y],
 272 [[%token END 0
 273 %%
 274 input:
 275   'a'
 276 | '(' input ')'
 277 | '(' error END
 278 ;
 279 ]])
 280
 281 AT_BISON_CHECK([[-v -o input.c input.y]])
 282
 283 # Get the final state in the parser.
 284 AT_CHECK([[sed -n 's/.*define YYFINAL *\([0-9][0-9]*\)/final state \1/p' input.c]],
 285          0, [stdout])
 286 mv stdout expout
 287
 288 # Get the final state in the report, from the "accept" action..
 289 AT_CHECK([sed -n '
 290            /^state \(.*\)/{
 291              s//final state \1/
 292              x
 293            }
 294            / accept/{
 295              x
 296              p
 297              q
 298            }
 299         ' input.output],
 300         0, [expout])
 301
 302 AT_CLEANUP