tests/conflicts.at

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