tests/sets.at

   1 # Exercising Bison Grammar Sets.                      -*- Autotest -*-
   2
   3 # Copyright (C) 2001-2002, 2005, 2007, 2009-2015, 2018-2021 Free
   4 # Software 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 <https://www.gnu.org/licenses/>.
  18
  19
  20 AT_BANNER([[Grammar Sets (Firsts etc.).]])
  21
  22
  23 ## ---------- ##
  24 ## Nullable.  ##
  25 ## ---------- ##
  26
  27 AT_SETUP([Nullable])
  28
  29 # At some point, nullable had been smoking grass, and managed to say:
  30 #
  31 # Entering set_nullable
  32 # NULLABLE
  33 #         'e': yes
  34 #         (null): no
  35 # ...
  36
  37 AT_DATA([[input.y]],
  38 [[%%
  39 e: 'e' | /* Nothing */;
  40 ]])
  41
  42 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
  43 AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
  44 [[DERIVES
  45   $accept derives
  46       0  e $end
  47   e derives
  48       1  'e'
  49       2  %empty
  50 NULLABLE
  51   $accept: no
  52   e: yes
  53 FIRSTS
  54   $accept firsts
  55     $accept
  56     e
  57   e firsts
  58     e
  59 FDERIVES
  60   $accept derives
  61       0  e $end
  62       1  'e'
  63       2  %empty
  64   e derives
  65       1  'e'
  66       2  %empty
  67 ]])
  68
  69 AT_CLEANUP
  70
  71
  72 ## ---------------- ##
  73 ## Broken Closure.  ##
  74 ## ---------------- ##
  75
  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
  79 # exotic closure:
  80 #
  81 # TC: Input
  82 #
  83 #    01234567
  84 #   +--------+
  85 #  0| 1      |
  86 #  1|  1     |
  87 #  2|   1    |
  88 #  3|    1   |
  89 #  4|     1  |
  90 #  5|      1 |
  91 #  6|       1|
  92 #  7|        |
  93 #   +--------+
  94 #
  95 # TC: Output
  96 #
  97 #    01234567
  98 #   +--------+
  99 #  0| 1      |
 100 #  1| 111    |
 101 #  2| 111    |
 102 #  3| 1111   |
 103 #  4| 111 1  |
 104 #  5| 111  1 |
 105 #  6| 111   1|
 106 #  7| 111    |
 107 #   +--------+
 108 #
 109 # instead of that below.
 110
 111 AT_SETUP([Broken Closure])
 112
 113 AT_DATA([input.y],
 114 [[%%
 115 a: b;
 116 b: c;
 117 c: d;
 118 d: e;
 119 e: f;
 120 f: g;
 121 g: h;
 122 h: 'h';
 123 ]])
 124
 125 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 126
 127 AT_CHECK([[sed -n 's/[   ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
 128 [[RTC: Firsts Output BEGIN
 129
 130    012345678
 131   .---------.
 132  0|111111111|
 133  1| 11111111|
 134  2|  1111111|
 135  3|   111111|
 136  4|    11111|
 137  5|     1111|
 138  6|      111|
 139  7|       11|
 140  8|        1|
 141   `---------'
 142 RTC: Firsts Output END
 143 ]])
 144
 145 AT_CLEANUP
 146
 147
 148
 149 ## -------- ##
 150 ## Firsts.  ##
 151 ## -------- ##
 152
 153 AT_SETUP([Firsts])
 154
 155 AT_DATA([input.y],
 156 [[%nonassoc '<' '>'
 157 %left '+' '-'
 158 %right '^' '='
 159 %%
 160 exp:
 161    exp '<' exp
 162  | exp '>' exp
 163  | exp '+' exp
 164  | exp '-' exp
 165  | exp '^' exp
 166  | exp '=' exp
 167  | "exp"
 168  ;
 169 ]])
 170
 171 AT_BISON_CHECK([[--trace=sets input.y]], [], [], [stderr])
 172 AT_SETS_CHECK([stderr], [[DERIVES], [NULLABLE], [FIRSTS], [FDERIVES]],
 173 [[DERIVES
 174   $accept derives
 175       0  exp $end
 176   exp derives
 177       1  exp '<' exp
 178       2  exp '>' exp
 179       3  exp '+' exp
 180       4  exp '-' exp
 181       5  exp '^' exp
 182       6  exp '=' exp
 183       7  "exp"
 184 NULLABLE
 185   $accept: no
 186   exp: no
 187 FIRSTS
 188   $accept firsts
 189     $accept
 190     exp
 191   exp firsts
 192     exp
 193 FDERIVES
 194   $accept derives
 195       0  exp $end
 196       1  exp '<' exp
 197       2  exp '>' exp
 198       3  exp '+' exp
 199       4  exp '-' exp
 200       5  exp '^' exp
 201       6  exp '=' exp
 202       7  "exp"
 203   exp derives
 204       1  exp '<' exp
 205       2  exp '>' exp
 206       3  exp '+' exp
 207       4  exp '-' exp
 208       5  exp '^' exp
 209       6  exp '=' exp
 210       7  "exp"
 211 ]])
 212
 213 AT_CLEANUP
 214
 215
 216
 217
 218 ## -------- ##
 219 ## Accept.  ##
 220 ## -------- ##
 221
 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
 226 # "end of file"'.
 227
 228 AT_SETUP([Accept])
 229
 230 AT_DATA([input.y],
 231 [[%token END 0
 232 %%
 233 input:
 234   'a'
 235 | '(' input ')'
 236 | '(' error END
 237 ;
 238 ]])
 239
 240 AT_BISON_CHECK([[-v -o input.c input.y]])
 241
 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]],
 244          0, [stdout])
 245 mv stdout expout
 246
 247 # Get the final state in the report, from the "accept" action..
 248 AT_CHECK([sed -n '
 249            /^State \(.*\)/{
 250              s//final state \1/
 251              x
 252            }
 253            / accept/{
 254              x
 255              p
 256              q
 257            }
 258         ' input.output],
 259         0, [expout])
 260
 261 AT_CLEANUP
 262
 263
 264
 265 ## ----------------- ##
 266 ## Build relations.  ##
 267 ## ----------------- ##
 268
 269 AT_SETUP([Build relations])
 270
 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).
 277 #
 278 # https://lists.gnu.org/r/bug-bison/2019-03/msg00007.html
 279
 280 AT_DATA([input.y],
 281 [[%%
 282 expr: term | term | term | term | term | term
 283 term: 'n'
 284 ]])
 285
 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
 291       |              ^~~~
 292 input.y:2.21-24: warning: rule useless in parser due to conflicts [-Wother]
 293     2 | expr: term | term | term | term | term | term
 294       |                     ^~~~
 295 input.y:2.28-31: warning: rule useless in parser due to conflicts [-Wother]
 296     2 | expr: term | term | term | term | term | term
 297       |                            ^~~~
 298 input.y:2.35-38: warning: rule useless in parser due to conflicts [-Wother]
 299     2 | expr: term | term | term | term | term | term
 300       |                                   ^~~~
 301 input.y:2.42-45: warning: rule useless in parser due to conflicts [-Wother]
 302     2 | expr: term | term | term | term | term | term
 303       |                                          ^~~~
 304 ]])
 305
 306 AT_CLEANUP
 307
 308
 309 ## ----------------- ##
 310 ## Reduced Grammar.  ##
 311 ## ----------------- ##
 312
 313 # Check information about the grammar, once reduced.
 314
 315 AT_SETUP([Reduced Grammar])
 316
 317 AT_DATA([input.y],
 318 [[%%
 319 expr: expr "+" term | term
 320 term: term "*" fact | fact
 321 useless: "useless"
 322 fact: "num"
 323 ]])
 324
 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]
 330 Reduced Grammar
 331
 332 ntokens = 7, nnterms = 4, nsyms = 11, nrules = 6, nritems = 17
 333
 334 Tokens
 335 ------
 336
 337 Value  Sprec  Sassoc  Tag
 338     0      0       0  $end
 339     1      0       0  error
 340     2      0       0  $undefined
 341     3      0       0  "+"
 342     4      0       0  "*"
 343     5      0       0  "useless"
 344     6      0       0  "num"
 345
 346
 347 Nonterminals
 348 ------------
 349
 350 Value  Tag
 351     7  $accept
 352     8  expr
 353     9  term
 354    10  fact
 355
 356
 357 Rules
 358 -----
 359
 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
 368
 369
 370 Rules interpreted
 371 -----------------
 372
 373 0      $accept: expr $end
 374 1      expr: expr "+" term
 375 2      expr: term
 376 3      term: term "*" fact
 377 4      term: fact
 378 5      fact: "num"
 379 6      useless: "useless"
 380
 381
 382 reduced input.y defines 7 terminals, 4 nonterminals, and 6 productions.
 383 ]])
 384
 385 AT_CLEANUP
 386
 387
 388 ## ------------------------------------- ##
 389 ## Reduced Grammar with prec and assoc.  ##
 390 ## ------------------------------------- ##
 391
 392 # Check information about the grammar, once reduced.
 393
 394 AT_SETUP([Reduced Grammar with prec and assoc])
 395
 396 AT_DATA([input.y],
 397 [[%nonassoc '<' '>'
 398 %left '+' '-'
 399 %right '^' '='
 400 %%
 401 exp:
 402    exp '<' exp
 403  | exp '>' exp
 404  | exp '+' exp
 405  | exp '-' exp
 406  | exp '^' exp
 407  | exp '=' exp
 408  | "exp"
 409  ;
 410 ]])
 411
 412 AT_BISON_CHECK([[--trace=grammar -o input.c input.y]], [], [],
 413 [[bison (GNU Bison) ]AT_PACKAGE_VERSION[
 414 Reduced Grammar
 415
 416 ntokens = 10, nnterms = 2, nsyms = 12, nrules = 8, nritems = 29
 417
 418 Tokens
 419 ------
 420
 421 Value  Sprec  Sassoc  Tag
 422     0      0       0  $end
 423     1      0       0  error
 424     2      0       0  $undefined
 425     3      1       3  '<'
 426     4      1       3  '>'
 427     5      2       2  '+'
 428     6      2       2  '-'
 429     7      3       1  '^'
 430     8      3       1  '='
 431     9      0       0  "exp"
 432
 433
 434 Nonterminals
 435 ------------
 436
 437 Value  Tag
 438    10  $accept
 439    11  exp
 440
 441
 442 Rules
 443 -----
 444
 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
 454
 455
 456 Rules interpreted
 457 -----------------
 458
 459 0      $accept: exp $end
 460 1      exp: exp '<' exp
 461 2      exp: exp '>' exp
 462 3      exp: exp '+' exp
 463 4      exp: exp '-' exp
 464 5      exp: exp '^' exp
 465 6      exp: exp '=' exp
 466 7      exp: "exp"
 467
 468
 469 reduced input.y defines 10 terminals, 2 nonterminals, and 8 productions.
 470 ]])
 471
 472 AT_CLEANUP