tests/conflicts.at

   1 # Exercising Bison on conflicts.                         -*- Autotest -*-
   2 # Copyright (C) 2002 Free Software Foundation, Inc.
   3
   4 # This program is free software; you can redistribute it and/or modify
   5 # it under the terms of the GNU General Public License as published by
   6 # the Free Software Foundation; either version 2, or (at your option)
   7 # any later version.
   8
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program; if not, write to the Free Software
  16 # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  17 # 02111-1307, USA.
  18
  19 AT_BANNER([[Conflicts.]])
  20
  21
  22 ## ---------------- ##
  23 ## S/R in initial.  ##
  24 ## ---------------- ##
  25
  26 # I once hacked Bison in such a way that it lost its reductions on the
  27 # initial state (because it was confusing it with the last state).  It
  28 # took me a while to strip down my failures to this simple case.  So
  29 # make sure it finds the s/r conflict below.
  30
  31 AT_SETUP([S/R in initial])
  32
  33 AT_DATA([[input.y]],
  34 [[%expect 1
  35 %%
  36 exp: e 'e';
  37 e: 'e' | /* Nothing. */;
  38 ]])
  39
  40 AT_CHECK([bison -o input.c input.y], 0, [],
  41 [[input.y:4.8: warning: rule never reduced because of conflicts: e: /* empty */
  42 ]])
  43
  44 AT_CLEANUP
  45
  46
  47 ## ------------------- ##
  48 ## %nonassoc and eof.  ##
  49 ## ------------------- ##
  50
  51 AT_SETUP([%nonassoc and eof])
  52
  53 AT_DATA([input.y],
  54 [[
  55 %{
  56 #include <config.h>
  57 /* We don't need perfect functions for these tests. */
  58 #undef malloc
  59 #undef memcmp
  60 #undef realloc
  61 #include <stdio.h>
  62
  63 #if STDC_HEADERS
  64 # include <stdlib.h>
  65 #endif
  66
  67 #define YYERROR_VERBOSE 1
  68 static void
  69 yyerror (const char *msg)
  70 {
  71   fprintf (stderr, "%s\n", msg);
  72   exit (1);
  73 }
  74
  75 /* The current argument. */
  76 static const char *input = NULL;
  77
  78 static int
  79 yylex (void)
  80 {
  81   /* No token stands for end of file. */
  82   if (input && *input)
  83     return *input++;
  84   else
  85     return 0;
  86 }
  87
  88 %}
  89
  90 %nonassoc '<' '>'
  91
  92 %%
  93 expr: expr '<' expr
  94     | expr '>' expr
  95     | '0'
  96     ;
  97 %%
  98 int
  99 main (int argc, const char *argv[])
 100 {
 101   if (argc > 1)
 102     input = argv[1];
 103   return yyparse ();
 104 }
 105 ]])
 106
 107 # Specify the output files to avoid problems on different file systems.
 108 AT_CHECK([bison -o input.c input.y])
 109 AT_COMPILE([input])
 110
 111 AT_PARSER_CHECK([./input '0<0'])
 112 # FIXME: This is an actual bug, but a new one, in the sense that
 113 # no one has ever spotted it!  The messages are *wrong*: there should
 114 # be nothing there, it should be expected eof.
 115 AT_PARSER_CHECK([./input '0<0<0'], [1], [],
 116          [parse error, unexpected '<', expecting '<' or '>'
 117 ])
 118
 119 AT_PARSER_CHECK([./input '0>0'])
 120 AT_PARSER_CHECK([./input '0>0>0'], [1], [],
 121          [parse error, unexpected '>', expecting '<' or '>'
 122 ])
 123
 124 AT_PARSER_CHECK([./input '0<0>0'], [1], [],
 125          [parse error, unexpected '>', expecting '<' or '>'
 126 ])
 127
 128 AT_CLEANUP
 129
 130
 131
 132 ## ------------------------- ##
 133 ## Unresolved SR Conflicts.  ##
 134 ## ------------------------- ##
 135
 136 AT_SETUP([Unresolved SR Conflicts])
 137
 138 AT_KEYWORDS([report])
 139
 140 AT_DATA([input.y],
 141 [[%token NUM OP
 142 %%
 143 exp: exp OP exp | NUM;
 144 ]])
 145
 146 AT_CHECK([bison -o input.c --report=all input.y], 0, [],
 147 [input.y: warning: 1 shift/reduce conflict
 148 ])
 149
 150 # Check the contents of the report.
 151 AT_CHECK([cat input.output], [],
 152 [[State 5 contains 1 shift/reduce conflict.
 153
 154
 155 Grammar
 156
 157     0 $accept: exp $end
 158
 159     1 exp: exp OP exp
 160     2    | NUM
 161
 162
 163 Terminals, with rules where they appear
 164
 165 $end (0) 0
 166 error (256)
 167 NUM (258) 2
 168 OP (259) 1
 169
 170
 171 Nonterminals, with rules where they appear
 172
 173 $accept (5)
 174     on left: 0
 175 exp (6)
 176     on left: 1 2, on right: 0 1
 177
 178
 179 state 0
 180
 181     0 $accept: . exp $end
 182     1 exp: . exp OP exp
 183     2    | . NUM
 184
 185     NUM  shift, and go to state 1
 186
 187     exp  go to state 2
 188
 189
 190 state 1
 191
 192     2 exp: NUM .
 193
 194     $default  reduce using rule 2 (exp)
 195
 196
 197 state 2
 198
 199     0 $accept: exp . $end
 200     1 exp: exp . OP exp
 201
 202     $end  shift, and go to state 3
 203     OP    shift, and go to state 4
 204
 205
 206 state 3
 207
 208     0 $accept: exp $end .
 209
 210     $default  accept
 211
 212
 213 state 4
 214
 215     1 exp: . exp OP exp
 216     1    | exp OP . exp
 217     2    | . NUM
 218
 219     NUM  shift, and go to state 1
 220
 221     exp  go to state 5
 222
 223
 224 state 5
 225
 226     1 exp: exp . OP exp  [$end, OP]
 227     1    | exp OP exp .  [$end, OP]
 228
 229     OP  shift, and go to state 4
 230
 231     OP        [reduce using rule 1 (exp)]
 232     $default  reduce using rule 1 (exp)
 233 ]])
 234
 235 AT_CLEANUP
 236
 237
 238
 239 ## ----------------------- ##
 240 ## Resolved SR Conflicts.  ##
 241 ## ----------------------- ##
 242
 243 AT_SETUP([Resolved SR Conflicts])
 244
 245 AT_KEYWORDS([report])
 246
 247 AT_DATA([input.y],
 248 [[%token NUM OP
 249 %left OP
 250 %%
 251 exp: exp OP exp | NUM;
 252 ]])
 253
 254 AT_CHECK([bison -o input.c --report=all input.y])
 255
 256 # Check the contents of the report.
 257 AT_CHECK([cat input.output], [],
 258 [[Grammar
 259
 260     0 $accept: exp $end
 261
 262     1 exp: exp OP exp
 263     2    | NUM
 264
 265
 266 Terminals, with rules where they appear
 267
 268 $end (0) 0
 269 error (256)
 270 NUM (258) 2
 271 OP (259) 1
 272
 273
 274 Nonterminals, with rules where they appear
 275
 276 $accept (5)
 277     on left: 0
 278 exp (6)
 279     on left: 1 2, on right: 0 1
 280
 281
 282 state 0
 283
 284     0 $accept: . exp $end
 285     1 exp: . exp OP exp
 286     2    | . NUM
 287
 288     NUM  shift, and go to state 1
 289
 290     exp  go to state 2
 291
 292
 293 state 1
 294
 295     2 exp: NUM .
 296
 297     $default  reduce using rule 2 (exp)
 298
 299
 300 state 2
 301
 302     0 $accept: exp . $end
 303     1 exp: exp . OP exp
 304
 305     $end  shift, and go to state 3
 306     OP    shift, and go to state 4
 307
 308
 309 state 3
 310
 311     0 $accept: exp $end .
 312
 313     $default  accept
 314
 315
 316 state 4
 317
 318     1 exp: . exp OP exp
 319     1    | exp OP . exp
 320     2    | . NUM
 321
 322     NUM  shift, and go to state 1
 323
 324     exp  go to state 5
 325
 326
 327 state 5
 328
 329     1 exp: exp . OP exp  [$end, OP]
 330     1    | exp OP exp .  [$end, OP]
 331
 332     $default  reduce using rule 1 (exp)
 333
 334     Conflict between rule 1 and token OP resolved as reduce (%left OP).
 335 ]])
 336
 337 AT_CLEANUP
 338
 339
 340 ## -------------------------------- ##
 341 ## Defaulted Conflicted Reduction.  ##
 342 ## -------------------------------- ##
 343
 344 # When there are RR conflicts, some rules are disabled.  Usually it is
 345 # simply displayed as:
 346 #
 347 #    $end           reduce using rule 3 (num)
 348 #    $end           [reduce using rule 4 (id)]
 349 #
 350 # But when `reduce 3' is the default action, we'd produce:
 351 #
 352 #    $end           [reduce using rule 4 (id)]
 353 #    $default    reduce using rule 3 (num)
 354 #
 355 # In this precise case (a reduction is masked by the default
 356 # reduction), we make the `reduce 3' explicit:
 357 #
 358 #    $end           reduce using rule 3 (num)
 359 #    $end           [reduce using rule 4 (id)]
 360 #    $default    reduce using rule 3 (num)
 361 #
 362 # Maybe that's not the best display, but then, please propose something
 363 # else.
 364
 365 AT_SETUP([Defaulted Conflicted Reduction])
 366 AT_KEYWORDS([report])
 367
 368 AT_DATA([input.y],
 369 [[%%
 370 exp: num | id;
 371 num: '0';
 372 id : '0';
 373 %%
 374 ]])
 375
 376 AT_CHECK([bison -o input.c --report=all input.y], 0, [],
 377 [[input.y: warning: 1 reduce/reduce conflict
 378 input.y:4.4-8: warning: rule never reduced because of conflicts: id: '0'
 379 ]])
 380
 381 # Check the contents of the report.
 382 AT_CHECK([cat input.output], [],
 383 [[Rules never reduced
 384
 385     4 id: '0'
 386
 387
 388 State 1 contains 1 reduce/reduce conflict.
 389
 390
 391 Grammar
 392
 393     0 $accept: exp $end
 394
 395     1 exp: num
 396     2    | id
 397
 398     3 num: '0'
 399
 400     4 id: '0'
 401
 402
 403 Terminals, with rules where they appear
 404
 405 $end (0) 0
 406 '0' (48) 3 4
 407 error (256)
 408
 409
 410 Nonterminals, with rules where they appear
 411
 412 $accept (4)
 413     on left: 0
 414 exp (5)
 415     on left: 1 2, on right: 0
 416 num (6)
 417     on left: 3, on right: 1
 418 id (7)
 419     on left: 4, on right: 2
 420
 421
 422 state 0
 423
 424     0 $accept: . exp $end
 425     1 exp: . num
 426     2    | . id
 427     3 num: . '0'
 428     4 id: . '0'
 429
 430     '0'  shift, and go to state 1
 431
 432     exp  go to state 2
 433     num  go to state 3
 434     id   go to state 4
 435
 436
 437 state 1
 438
 439     3 num: '0' .  [$end]
 440     4 id: '0' .  [$end]
 441
 442     $end      reduce using rule 3 (num)
 443     $end      [reduce using rule 4 (id)]
 444     $default  reduce using rule 3 (num)
 445
 446
 447 state 2
 448
 449     0 $accept: exp . $end
 450
 451     $end  shift, and go to state 5
 452
 453
 454 state 3
 455
 456     1 exp: num .
 457
 458     $default  reduce using rule 1 (exp)
 459
 460
 461 state 4
 462
 463     2 exp: id .
 464
 465     $default  reduce using rule 2 (exp)
 466
 467
 468 state 5
 469
 470     0 $accept: exp $end .
 471
 472     $default  accept
 473 ]])
 474
 475 AT_CLEANUP
 476
 477
 478
 479
 480 ## -------------------- ##
 481 ## %expect not enough.  ##
 482 ## -------------------- ##
 483
 484 AT_SETUP([%expect not enough])
 485
 486 AT_DATA([input.y],
 487 [[%token NUM OP
 488 %expect 0
 489 %%
 490 exp: exp OP exp | NUM;
 491 ]])
 492
 493 AT_CHECK([bison -o input.c input.y], 1, [],
 494 [input.y: warning: 1 shift/reduce conflict
 495 input.y: expected 0 shift/reduce conflicts
 496 ])
 497 AT_CLEANUP
 498
 499
 500 ## --------------- ##
 501 ## %expect right.  ##
 502 ## --------------- ##
 503
 504 AT_SETUP([%expect right])
 505
 506 AT_DATA([input.y],
 507 [[%token NUM OP
 508 %expect 1
 509 %%
 510 exp: exp OP exp | NUM;
 511 ]])
 512
 513 AT_CHECK([bison -o input.c input.y])
 514 AT_CLEANUP
 515
 516
 517 ## ------------------ ##
 518 ## %expect too much.  ##
 519 ## ------------------ ##
 520
 521 AT_SETUP([%expect too much])
 522
 523 AT_DATA([input.y],
 524 [[%token NUM OP
 525 %expect 2
 526 %%
 527 exp: exp OP exp | NUM;
 528 ]])
 529
 530 AT_CHECK([bison -o input.c input.y], 1, [],
 531 [input.y: warning: 1 shift/reduce conflict
 532 input.y: expected 2 shift/reduce conflicts
 533 ])
 534 AT_CLEANUP