tests/conflicts.at

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