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