tests/glr-regression.at

   1 # Checking GLR Parsing: Regression Tests           -*- Autotest -*-
   2 # Copyright (C) 2002, 2003, 2005, 2006 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., 51 Franklin Street, Fifth Floor, Boston, MA
  17 # 02110-1301, USA.
  18
  19 AT_BANNER([[GLR Regression Tests]])
  20
  21 ## --------------------------- ##
  22 ## Badly Collapsed GLR States. ##
  23 ## --------------------------- ##
  24
  25 AT_SETUP([Badly Collapsed GLR States])
  26
  27 AT_DATA_GRAMMAR([glr-regr1.y],
  28 [[/* Regression Test: Improper state compression */
  29 /* Reported by Scott McPeak */
  30
  31 %{
  32 #include <stdio.h>
  33
  34 #define YYSTYPE int
  35 static YYSTYPE exprMerge (YYSTYPE x0, YYSTYPE x1);
  36 int yylex (void);
  37 void yyerror (char const *msg);
  38 %}
  39
  40
  41 %glr-parser
  42
  43
  44 /* -------- productions ------ */
  45 %%
  46
  47 StartSymbol: E  { $$=0; }                   %merge <exprMerge>
  48            ;
  49
  50 E: E 'P' E { $$=1; printf("E -> E 'P' E\n"); }  %merge <exprMerge>
  51  | 'B'     { $$=2; printf("E -> 'B'\n"); }      %merge <exprMerge>
  52  ;
  53
  54
  55
  56 /* ---------- C code ----------- */
  57 %%
  58
  59 static YYSTYPE exprMerge (YYSTYPE x0, YYSTYPE x1)
  60 {
  61   (void) x0;
  62   (void) x1;
  63   printf ("<OR>\n");
  64   return 0;
  65 }
  66
  67 int
  68 main (void)
  69 {
  70   return yyparse ();
  71 }
  72
  73 void
  74 yyerror (char const *msg)
  75 {
  76   fprintf (stderr, "%s\n", msg);
  77 }
  78
  79
  80 int
  81 yylex (void)
  82 {
  83   for (;;)
  84     {
  85       int ch = getchar ();
  86       if (ch == EOF)
  87         return 0;
  88       else if (ch == 'B' || ch == 'P')
  89         return ch;
  90     }
  91 }
  92 ]])
  93
  94 AT_CHECK([[bison -o glr-regr1.c glr-regr1.y]], 0, [],
  95 [glr-regr1.y: conflicts: 1 shift/reduce
  96 ])
  97 AT_COMPILE([glr-regr1])
  98 AT_CHECK([[echo BPBPB | ./glr-regr1]], 0,
  99 [[E -> 'B'
 100 E -> 'B'
 101 E -> E 'P' E
 102 E -> 'B'
 103 E -> E 'P' E
 104 E -> 'B'
 105 E -> E 'P' E
 106 E -> E 'P' E
 107 <OR>
 108 ]], [])
 109
 110 AT_CLEANUP
 111
 112 ## ------------------------------------------------------------ ##
 113 ## Improper handling of embedded actions and $-N in GLR parsers ##
 114 ## ------------------------------------------------------------ ##
 115
 116 AT_SETUP([Improper handling of embedded actions and dollar(-N) in GLR parsers])
 117
 118 AT_DATA_GRAMMAR([glr-regr2a.y],
 119 [[/* Regression Test: Improper handling of embedded actions and $-N  */
 120 /* Reported by S. Eken */
 121
 122 %{
 123   #define YYSTYPE char *
 124
 125   #include <ctype.h>
 126   #include <stdio.h>
 127   #include <stdlib.h>
 128   #include <string.h>
 129   int yylex (void);
 130   void yyerror (char const *);
 131 %}
 132
 133 %glr-parser
 134
 135 %%
 136
 137 command:
 138     's' var 't'
 139        { printf ("Variable: '%s'\n", $2); }
 140     'v' 'x' 'q'
 141        { free ($2); }
 142   | 's' var_list 't' 'e'
 143        { printf ("Varlist: '%s'\n", $2); free ($2); }
 144   | 's' var 't' var_printer 'x'
 145        { free ($2); }
 146   ;
 147
 148 var:
 149   'V'
 150      { $$ = $1; }
 151   ;
 152
 153 var_list:
 154   var
 155     { $$ = $1; }
 156   | var ',' var_list
 157     {
 158       char *s = (char *) realloc ($1, strlen ($1) + 1 + strlen ($3) + 1);
 159       strcat (s, ",");
 160       strcat (s, $3);
 161       free ($3);
 162       $$ = s;
 163     }
 164   ;
 165
 166 var_printer: 'v'
 167    { printf ("Variable: '%s'\n", $-1); }
 168
 169 %%
 170
 171 FILE *input = NULL;
 172
 173 int
 174 yylex (void)
 175 {
 176   char buf[50];
 177   char *s;
 178   switch (fscanf (input, " %1[a-z,]", buf)) {
 179   case 1:
 180     return buf[0];
 181   case EOF:
 182     return 0;
 183   default:
 184     break;
 185   }
 186   if (fscanf (input, "%49s", buf) != 1)
 187     return 0;
 188   if (sizeof buf - 1 <= strlen (buf))
 189     abort ();
 190   s = (char *) malloc (strlen (buf) + 1);
 191   strcpy (s, buf);
 192   yylval = s;
 193   return 'V';
 194 }
 195
 196 void
 197 yyerror (char const *s)
 198 { printf ("%s\n", s);
 199 }
 200
 201 int
 202 main (int argc, char **argv)
 203 {
 204   input = stdin;
 205   if (argc == 2 && !(input = fopen (argv[1], "r"))) return 3;
 206   return yyparse ();
 207 }
 208 ]])
 209
 210 AT_CHECK([[bison -o glr-regr2a.c glr-regr2a.y]], 0, [],
 211 [glr-regr2a.y: conflicts: 2 shift/reduce
 212 ])
 213 AT_COMPILE([glr-regr2a])
 214
 215 AT_CHECK([[echo s VARIABLE_1 t v x q | ./glr-regr2a]], 0,
 216 [[Variable: 'VARIABLE_1'
 217 ]], [])
 218 AT_CHECK([[echo s VARIABLE_1 , ANOTHER_VARIABLE_2 t e | ./glr-regr2a]], 0,
 219 [[Varlist: 'VARIABLE_1,ANOTHER_VARIABLE_2'
 220 ]])
 221 AT_CHECK([[echo s VARIABLE_3 t v x | ./glr-regr2a]], 0,
 222 [[Variable: 'VARIABLE_3'
 223 ]], [])
 224
 225
 226 AT_CLEANUP
 227
 228 ## ------------------------------------------------------------ ##
 229 ## Improper merging of GLR delayed action sets                  ##
 230 ## ------------------------------------------------------------ ##
 231
 232 AT_SETUP([Improper merging of GLR delayed action sets])
 233
 234 AT_DATA_GRAMMAR([glr-regr3.y],
 235 [[/* Regression Test: Improper merging of GLR delayed action sets.  */
 236 /* Reported by M. Rosien */
 237
 238 %{
 239 #include <stdio.h>
 240 #include <stdarg.h>
 241
 242 static int MergeRule (int x0, int x1);
 243 static void yyerror (char const * s);
 244 int yylex (void);
 245
 246 #define RULE(x) (1 << (x))
 247
 248 %}
 249
 250 %glr-parser
 251
 252 %token BAD_CHAR
 253 %token P1 P2 T1 T2 T3 T4 O1 O2
 254
 255 %%
 256
 257 S : P1 T4 O2 NT6 P2  { printf ("Result: %x\n", $4); }
 258 ;
 259
 260 NT1 : P1 T1 O1 T2 P2 { $$ = RULE(2); }  %merge<MergeRule>
 261 ;
 262
 263 NT2 : NT1             { $$ = RULE(3); } %merge<MergeRule>
 264     | P1 NT1 O1 T3 P2 { $$ = RULE(4); } %merge<MergeRule>
 265 ;
 266
 267 NT3 : T3              { $$ = RULE(5); } %merge<MergeRule>
 268     | P1 NT1 O1 T3 P2 { $$ = RULE(6); } %merge<MergeRule>
 269 ;
 270
 271 NT4 : NT3              { $$ = RULE(7); } %merge<MergeRule>
 272     | NT2              { $$ = RULE(8); } %merge<MergeRule>
 273     | P1 NT2 O1 NT3 P2 { $$ = RULE(9); } %merge<MergeRule>
 274 ;
 275
 276 NT5 : NT4              { $$ = RULE(10); } %merge<MergeRule>
 277 ;
 278
 279 NT6 : P1 NT1 O1 T3 P2  { $$ = RULE(11) | $2; } %merge<MergeRule>
 280     | NT5              { $$ = RULE(12) | $1; } %merge<MergeRule>
 281 ;
 282
 283 %%
 284
 285 static int MergeRule (int x0, int x1) {
 286   return x0 | x1;
 287 }
 288
 289 static void yyerror(char const * s) {
 290   fprintf(stderr,"error: %s\n",s);
 291 }
 292
 293 FILE *input = NULL;
 294
 295 int P[] = { P1, P2 };
 296 int O[] = { O1, O2 };
 297 int T[] = { T1, T2, T3, T4 };
 298
 299 int yylex (void)
 300 {
 301   char inp[3];
 302   if (fscanf (input, "%2s", inp) == EOF)
 303     return 0;
 304   switch (inp[0])
 305     {
 306     case 'p': return P[inp[1] - '1'];
 307     case 't': return T[inp[1] - '1'];
 308     case 'o': return O[inp[1] - '1'];
 309     }
 310   return BAD_CHAR;
 311 }
 312
 313 int main(int argc, char* argv[]) {
 314   input = stdin;
 315   if (argc == 2 && !(input = fopen (argv[1], "r"))) return 3;
 316   return yyparse ();
 317 }
 318 ]])
 319
 320 AT_CHECK([[bison -o glr-regr3.c glr-regr3.y]], 0, [],
 321 [glr-regr3.y: conflicts: 1 shift/reduce, 1 reduce/reduce
 322 ])
 323 AT_COMPILE([glr-regr3])
 324
 325 AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 p2 o1 t3 p2 p2 | ./glr-regr3]], 0,
 326 [[Result: 1c04
 327 ]], [])
 328
 329 AT_CLEANUP
 330
 331
 332 ## ------------------------------------------------------------------------- ##
 333 ## Duplicate representation of merged trees.  See                            ##
 334 ## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>.     ##
 335 ## ------------------------------------------------------------------------- ##
 336
 337 AT_SETUP([Duplicate representation of merged trees])
 338
 339 AT_DATA_GRAMMAR([glr-regr4.y],
 340 [[
 341 %union { char *ptr; }
 342 %type <ptr> S A A1 A2 B
 343 %glr-parser
 344
 345 %{
 346   #include <stdio.h>
 347   #include <stdlib.h>
 348   #include <string.h>
 349   static char *merge (YYSTYPE, YYSTYPE);
 350   static char *make_value (char const *, char const *);
 351   static void yyerror (char const *);
 352   static int yylex (void);
 353 %}
 354
 355 %%
 356
 357 tree: S { printf ("%s\n", $1); } ;
 358
 359 S:
 360   A   %merge<merge> { $$ = make_value ("S", $1); }
 361   | B %merge<merge> { $$ = make_value ("S", $1); }
 362   ;
 363
 364 A:
 365   A1   %merge<merge> { $$ = make_value ("A", $1); }
 366   | A2 %merge<merge> { $$ = make_value ("A", $1); }
 367   ;
 368
 369 A1: 'a' { $$ = make_value ("A1", "'a'"); } ;
 370 A2: 'a' { $$ = make_value ("A2", "'a'"); } ;
 371 B:  'a' { $$ = make_value ("B", "'a'");  } ;
 372
 373 %%
 374
 375 static int
 376 yylex (void)
 377 {
 378   static char const *input = "a";
 379   return *input++;
 380 }
 381
 382 int
 383 main (void)
 384 {
 385   return yyparse ();
 386 }
 387
 388 static char *
 389 make_value (char const *parent, char const *child)
 390 {
 391   char const format[] = "%s <- %s";
 392   char *value =
 393     (char *) malloc (strlen (parent) + strlen (child) + sizeof format);
 394   sprintf (value, format, parent, child);
 395   return value;
 396 }
 397
 398 static char *
 399 merge (YYSTYPE s1, YYSTYPE s2)
 400 {
 401   char const format[] = "merge{ %s and %s }";
 402   char *value =
 403     (char *) malloc (strlen (s1.ptr) + strlen (s2.ptr) + sizeof format);
 404   sprintf (value, format, s1.ptr, s2.ptr);
 405   return value;
 406 }
 407
 408 static void
 409 yyerror (char const *msg)
 410 {
 411   fprintf (stderr, "%s\n", msg);
 412 }
 413 ]])
 414
 415 AT_CHECK([[bison -o glr-regr4.c glr-regr4.y]], 0, [],
 416 [glr-regr4.y: conflicts: 1 reduce/reduce
 417 ])
 418 AT_COMPILE([glr-regr4])
 419
 420 AT_CHECK([[./glr-regr4]], 0,
 421 [[merge{ S <- merge{ A <- A1 <- 'a' and A <- A2 <- 'a' } and S <- B <- 'a' }
 422 ]], [])
 423
 424 AT_CLEANUP
 425
 426
 427 ## -------------------------------------------------------------------------- ##
 428 ## User destructor for unresolved GLR semantic value.  See                    ##
 429 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00016.html>.   ##
 430 ## -------------------------------------------------------------------------- ##
 431
 432 AT_SETUP([User destructor for unresolved GLR semantic value])
 433
 434 AT_DATA_GRAMMAR([glr-regr5.y],
 435 [[
 436 %{
 437   #include <stdio.h>
 438   #include <stdlib.h>
 439   static void yyerror (char const *);
 440   static int yylex (void);
 441   enum { MAGIC_VALUE = -1057808125 }; /* originally chosen at random */
 442 %}
 443
 444 %glr-parser
 445 %union { int value; }
 446 %type <value> start
 447
 448 %destructor {
 449   if ($$ != MAGIC_VALUE)
 450     {
 451       fprintf (stderr, "Bad destructor call.\n");
 452       exit (EXIT_FAILURE);
 453     }
 454 } start
 455
 456 %%
 457
 458 start:
 459    'a' { $$ = MAGIC_VALUE; }
 460    | 'a' { $$ = MAGIC_VALUE; }
 461    ;
 462
 463 %%
 464
 465 static int
 466 yylex (void)
 467 {
 468   static char const *input = "a";
 469   return *input++;
 470 }
 471
 472 static void
 473 yyerror (char const *msg)
 474 {
 475   fprintf (stderr, "%s\n", msg);
 476 }
 477
 478 int
 479 main (void)
 480 {
 481   return yyparse () != 1;
 482 }
 483 ]])
 484
 485 AT_CHECK([[bison -o glr-regr5.c glr-regr5.y]], 0, [],
 486 [glr-regr5.y: conflicts: 1 reduce/reduce
 487 ])
 488 AT_COMPILE([glr-regr5])
 489
 490 AT_CHECK([[./glr-regr5]], 0, [],
 491 [syntax is ambiguous
 492 ])
 493
 494 AT_CLEANUP
 495
 496
 497 ## -------------------------------------------------------------------------- ##
 498 ## User destructor after an error during a split parse.  See                  ##
 499 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00029.html>.   ##
 500 ## -------------------------------------------------------------------------- ##
 501
 502 AT_SETUP([User destructor after an error during a split parse])
 503
 504 AT_DATA_GRAMMAR([glr-regr6.y],
 505 [[
 506 %{
 507   #include <stdio.h>
 508   #include <stdlib.h>
 509   static void yyerror (char const *);
 510   static int yylex (void);
 511 %}
 512
 513 %glr-parser
 514 %union { int value; }
 515 %type <value> 'a'
 516
 517 %destructor {
 518   printf ("Destructor called.\n");
 519 } 'a'
 520
 521 %%
 522
 523 start: 'a' | 'a' ;
 524
 525 %%
 526
 527 static int
 528 yylex (void)
 529 {
 530   static char const *input = "a";
 531   return *input++;
 532 }
 533
 534 static void
 535 yyerror (char const *msg)
 536 {
 537   fprintf (stderr, "%s\n", msg);
 538 }
 539
 540 int
 541 main (void)
 542 {
 543   return yyparse () != 1;
 544 }
 545 ]])
 546
 547 AT_CHECK([[bison -o glr-regr6.c glr-regr6.y]], 0, [],
 548 [glr-regr6.y: conflicts: 1 reduce/reduce
 549 ])
 550 AT_COMPILE([glr-regr6])
 551
 552 AT_CHECK([[./glr-regr6]], 0,
 553 [Destructor called.
 554 ],
 555 [syntax is ambiguous
 556 ])
 557
 558 AT_CLEANUP
 559
 560
 561 ## ------------------------------------------------------------------------- ##
 562 ## Duplicated user destructor for lookahead.  See                            ##
 563 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00035.html>.  ##
 564 ## ------------------------------------------------------------------------- ##
 565
 566 AT_SETUP([Duplicated user destructor for lookahead])
 567
 568 AT_DATA_GRAMMAR([glr-regr7.y],
 569 [[
 570 %{
 571   #include <stdio.h>
 572   #include <stdlib.h>
 573   static void yyerror (char const *);
 574   static int yylex (void);
 575   #define YYSTACKEXPANDABLE 0
 576 %}
 577
 578 %glr-parser
 579 %union { int *count; }
 580 %type <count> 'a'
 581
 582 %destructor {
 583   if ((*$$)++)
 584     fprintf (stderr, "Destructor called on same value twice.\n");
 585 } 'a'
 586
 587 %%
 588
 589 start:
 590     stack1 start
 591   | stack2 start
 592   | /* empty */
 593   ;
 594 stack1: 'a' ;
 595 stack2: 'a' ;
 596
 597 %%
 598
 599 static int
 600 yylex (void)
 601 {
 602   yylval.count = (int *) malloc (sizeof (int));
 603   if (!yylval.count)
 604     {
 605       fprintf (stderr, "Test inconclusive.\n");
 606       exit (EXIT_FAILURE);
 607     }
 608   *yylval.count = 0;
 609   return 'a';
 610 }
 611
 612 static void
 613 yyerror (char const *msg)
 614 {
 615   fprintf (stderr, "%s\n", msg);
 616 }
 617
 618 int
 619 main (void)
 620 {
 621   return yyparse ();
 622 }
 623 ]])
 624
 625 AT_CHECK([[bison -o glr-regr7.c glr-regr7.y]], 0, [],
 626 [glr-regr7.y: conflicts: 2 reduce/reduce
 627 ])
 628 AT_COMPILE([glr-regr7])
 629
 630 AT_CHECK([[./glr-regr7]], 2, [],
 631 [memory exhausted
 632 ])
 633
 634 AT_CLEANUP
 635
 636
 637 ## ------------------------------------------------------------------------- ##
 638 ## Incorrect default location for empty right-hand sides.  Adapted from bug  ##
 639 ## report by Claudia Hermann.                                                ##
 640 ## See http://lists.gnu.org/archive/html/bug-bison/2005-10/msg00069.html and ##
 641 ## http://lists.gnu.org/archive/html/bug-bison/2005-10/msg00072.html         ##
 642 ## ------------------------------------------------------------------------- ##
 643
 644 AT_SETUP([Incorrectly initialized location for empty right-hand side in GLR])
 645
 646 AT_DATA_GRAMMAR([glr-regr8.y],
 647 [[
 648 %{
 649   #include <stdio.h>
 650   #include <stdlib.h>
 651   static void yyerror (char const *);
 652   static int yylex (void);
 653   static void yyerror (char const *msg);
 654 %}
 655
 656 %token T_CONSTANT
 657 %token T_PORT
 658 %token T_SIGNAL
 659
 660 %glr-parser
 661
 662 %%
 663
 664
 665 PortClause      : T_PORT InterfaceDeclaration T_PORT
 666                 { printf("%d/%d - %d/%d - %d/%d\n",
 667                          @1.first_column, @1.last_column,
 668                          @2.first_column, @2.last_column,
 669                          @3.first_column, @3.last_column); }
 670         ;
 671
 672 InterfaceDeclaration    : OptConstantWord       %dprec 1
 673         | OptSignalWord %dprec 2
 674         ;
 675
 676 OptConstantWord : /* empty */
 677         | T_CONSTANT
 678         ;
 679
 680 OptSignalWord   : /* empty */
 681                 { printf("empty: %d/%d\n", @$.first_column, @$.last_column); }
 682         | T_SIGNAL
 683         ;
 684
 685 %%
 686
 687 void
 688 yyerror (char const *msg)
 689 {
 690   fprintf (stderr, "%s\n", msg);
 691 }
 692
 693 static int lexIndex;
 694
 695 int yylex (void)
 696 {
 697   lexIndex += 1;
 698   switch (lexIndex)
 699     {
 700     case 1:
 701       yylloc.first_column = 1;
 702       yylloc.last_column = 9;
 703       return T_PORT;
 704     case 2:
 705       yylloc.first_column = 13;
 706       yylloc.last_column = 17;
 707       return T_PORT;
 708     default:
 709       return 0;
 710     }
 711 }
 712
 713 int
 714 main (void)
 715 {
 716   yyparse();
 717   return 0;
 718 }
 719 ]])
 720
 721 AT_CHECK([[bison -o glr-regr8.c glr-regr8.y]], 0, [],
 722 [glr-regr8.y: conflicts: 1 reduce/reduce
 723 ])
 724 AT_COMPILE([glr-regr8])
 725
 726 AT_CHECK([[./glr-regr8]], 0,
 727 [empty: 9/9
 728 1/9 - 9/9 - 13/17
 729 ],
 730 [])
 731
 732 AT_CLEANUP
 733
 734
 735 ## ------------------------------------------------------------------------- ##
 736 ## No users destructors if stack 0 deleted.  See                             ##
 737 ## <http://lists.gnu.org/archive/html/bison-patches/2005-09/msg00109.html>.  ##
 738 ## ------------------------------------------------------------------------- ##
 739
 740 AT_SETUP([No users destructors if stack 0 deleted])
 741
 742 AT_DATA_GRAMMAR([glr-regr9.y],
 743 [[
 744 %{
 745 # include <stdio.h>
 746 # include <stdlib.h>
 747   static void yyerror (char const *);
 748   static int yylex (void);
 749 # define YYSTACKEXPANDABLE 0
 750   static int tokens = 0;
 751   static int destructors = 0;
 752 # define USE(Var)
 753 %}
 754
 755 %glr-parser
 756 %union { int dummy; }
 757 %type <dummy> 'a'
 758
 759 %destructor {
 760   destructors += 1;
 761 } 'a'
 762
 763 %%
 764
 765 start:
 766     ambig0 'a'   { destructors += 2; USE ($2); }
 767   | ambig1 start { destructors += 1; }
 768   | ambig2 start { destructors += 1; }
 769   ;
 770
 771 ambig0: 'a' ;
 772 ambig1: 'a' ;
 773 ambig2: 'a' ;
 774
 775 %%
 776
 777 static int
 778 yylex (void)
 779 {
 780   tokens += 1;
 781   return 'a';
 782 }
 783
 784 static void
 785 yyerror (char const *msg)
 786 {
 787   fprintf (stderr, "%s\n", msg);
 788 }
 789
 790 int
 791 main (void)
 792 {
 793   int exit_status;
 794   exit_status = yyparse ();
 795   if (tokens != destructors)
 796     {
 797       fprintf (stderr, "Tokens = %d, Destructors = %d\n", tokens, destructors);
 798       return 1;
 799     }
 800   return !exit_status;
 801 }
 802 ]])
 803
 804 AT_CHECK([[bison -o glr-regr9.c glr-regr9.y]], 0, [],
 805 [glr-regr9.y: conflicts: 1 reduce/reduce
 806 ])
 807 AT_COMPILE([glr-regr9])
 808
 809 AT_CHECK([[./glr-regr9]], 0, [],
 810 [memory exhausted
 811 ])
 812
 813 AT_CLEANUP
 814
 815
 816 ## ------------------------------------------------------------------------- ##
 817 ## Corrupted semantic options if user action cuts parse.                     ##
 818 ## ------------------------------------------------------------------------- ##
 819
 820 AT_SETUP([Corrupted semantic options if user action cuts parse])
 821
 822 AT_DATA_GRAMMAR([glr-regr10.y],
 823 [[
 824 %{
 825 # include <stdio.h>
 826   static void yyerror (char const *);
 827   static int yylex (void);
 828   #define GARBAGE_SIZE 50
 829   static char garbage[GARBAGE_SIZE];
 830 %}
 831
 832 %glr-parser
 833 %union { char *ptr; }
 834 %type <ptr> start
 835
 836 %%
 837
 838 start:
 839     %dprec 2 { $$ = garbage; YYACCEPT; }
 840   | %dprec 1 { $$ = garbage; YYACCEPT; }
 841   ;
 842
 843 %%
 844
 845 static void
 846 yyerror (char const *msg)
 847 {
 848   fprintf (stderr, "%s\n", msg);
 849 }
 850
 851 static int
 852 yylex (void)
 853 {
 854   return 0;
 855 }
 856
 857 int
 858 main (void)
 859 {
 860   int i;
 861   for (i = 0; i < GARBAGE_SIZE; i+=1)
 862     garbage[i] = 108;
 863   return yyparse ();
 864 }
 865 ]])
 866
 867 AT_CHECK([[bison -t -o glr-regr10.c glr-regr10.y]], 0, [],
 868 [glr-regr10.y: conflicts: 1 reduce/reduce
 869 ])
 870 AT_COMPILE([glr-regr10])
 871
 872 AT_CHECK([[./glr-regr10]], 0, [], [])
 873
 874 AT_CLEANUP
 875
 876
 877 ## ------------------------------------------------------------------------- ##
 878 ## Undesirable destructors if user action cuts parse.                        ##
 879 ## ------------------------------------------------------------------------- ##
 880
 881 AT_SETUP([Undesirable destructors if user action cuts parse])
 882
 883 AT_DATA_GRAMMAR([glr-regr11.y],
 884 [[
 885 %{
 886 # include <stdlib.h>
 887   static void yyerror (char const *);
 888   static int yylex (void);
 889   static int destructors = 0;
 890 # define USE(val)
 891 %}
 892
 893 %glr-parser
 894 %union { int dummy; }
 895 %type <int> 'a'
 896 %destructor { destructors += 1; } 'a'
 897
 898 %%
 899
 900 start:
 901     'a' %dprec 2 { USE ($1); destructors += 1; YYACCEPT; }
 902   | 'a' %dprec 1 { USE ($1); destructors += 1; YYACCEPT; }
 903   ;
 904
 905 %%
 906
 907 static void
 908 yyerror (char const *msg)
 909 {
 910   fprintf (stderr, "%s\n", msg);
 911 }
 912
 913 static int
 914 yylex (void)
 915 {
 916   static char const *input = "a";
 917   return *input++;
 918 }
 919
 920 int
 921 main (void)
 922 {
 923   int exit_status = yyparse ();
 924   if (destructors != 1)
 925     {
 926       fprintf (stderr, "Destructor calls: %d\n", destructors);
 927       return 1;
 928     }
 929   return exit_status;
 930 }
 931 ]])
 932
 933 AT_CHECK([[bison -t -o glr-regr11.c glr-regr11.y]], 0, [],
 934 [glr-regr11.y: conflicts: 1 reduce/reduce
 935 ])
 936 AT_COMPILE([glr-regr11])
 937
 938 AT_CHECK([[./glr-regr11]], 0, [], [])
 939
 940 AT_CLEANUP
 941
 942
 943 ## ------------------------------------------------------------------------- ##
 944 ## Leaked merged semantic value if user action cuts parse.                   ##
 945 ## ------------------------------------------------------------------------- ##
 946
 947 AT_SETUP([Leaked merged semantic value if user action cuts parse])
 948
 949 AT_DATA_GRAMMAR([glr-regr12.y],
 950 [[
 951 %glr-parser
 952 %union { int dummy; }
 953 %type <dummy> start
 954 %destructor { has_value = 0; } start
 955
 956 %{
 957 # include <stdlib.h>
 958   static int merge (YYSTYPE, YYSTYPE);
 959   static void yyerror (char const *);
 960   static int yylex (void);
 961   static int has_value = 0;
 962 # define USE(val)
 963 %}
 964
 965 %%
 966
 967 start:
 968     %merge<merge> { has_value = 1; USE ($$); }
 969   | %merge<merge> { USE ($$); YYACCEPT; }
 970   ;
 971
 972 %%
 973
 974 static int
 975 merge (YYSTYPE s1, YYSTYPE s2)
 976 {
 977   /* Not invoked. */
 978   char dummy = s1.dummy + s2.dummy;
 979   return dummy;
 980 }
 981
 982 static void
 983 yyerror (char const *msg)
 984 {
 985   fprintf (stderr, "%s\n", msg);
 986 }
 987
 988 static int
 989 yylex (void)
 990 {
 991   return 0;
 992 }
 993
 994 int
 995 main (void)
 996 {
 997   int exit_status = yyparse ();
 998   if (has_value)
 999     {
1000       fprintf (stderr, "Destructor not called.\n");
1001       return 1;
1002     }
1003   return exit_status;
1004 }
1005 ]])
1006
1007 AT_CHECK([[bison -t -o glr-regr12.c glr-regr12.y]], 0, [],
1008 [glr-regr12.y: conflicts: 1 reduce/reduce
1009 ])
1010 AT_COMPILE([glr-regr12])
1011
1012 AT_CHECK([[./glr-regr12]], 0, [], [])
1013
1014 AT_CLEANUP
1015
1016
1017 ## ------------------------------------------------------------------------- ##
1018 ## Incorrect lookahead during deterministic GLR.  See                        ##
1019 ## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html> and  ##
1020 ## <http://lists.gnu.org/archive/html/bison-patches/2006-01/msg00060.html>.  ##
1021 ## ------------------------------------------------------------------------- ##
1022
1023 AT_SETUP([Incorrect lookahead during deterministic GLR])
1024
1025 AT_DATA_GRAMMAR([glr-regr13.y],
1026 [[
1027 /* Tests:
1028      - Defaulted state with initial yychar: yychar == YYEMPTY.
1029      - Nondefaulted state: yychar != YYEMPTY.
1030      - Defaulted state after lookahead: yychar != YYEMPTY.
1031      - Defaulted state after shift: yychar == YYEMPTY.
1032      - User action changing the lookahead.  */
1033
1034 %{
1035   #include <stdio.h>
1036   static void yyerror (char const *);
1037   static int yylex (void);
1038   static void print_look_ahead (char const *);
1039   #define USE(value)
1040 %}
1041
1042 %union { char value; }
1043 %type <value> 'a' 'b'
1044 %glr-parser
1045 %locations
1046
1047 %%
1048
1049 start:
1050   defstate_init defstate_shift 'b' change_lookahead 'a' {
1051     USE ($3);
1052     print_look_ahead ("start <- defstate_init defstate_shift 'b'");
1053   }
1054   ;
1055 defstate_init:
1056   {
1057     print_look_ahead ("defstate_init <- empty string");
1058   }
1059   ;
1060 defstate_shift:
1061   nondefstate defstate_look 'a' {
1062     USE ($3);
1063     print_look_ahead ("defstate_shift <- nondefstate defstate_look 'a'");
1064   }
1065   ;
1066 defstate_look:
1067   {
1068     print_look_ahead ("defstate_look <- empty string");
1069   }
1070   ;
1071 nondefstate:
1072   {
1073     print_look_ahead ("nondefstate <- empty string");
1074   }
1075   | 'b' {
1076     USE ($1);
1077     print_look_ahead ("nondefstate <- 'b'");
1078   }
1079   ;
1080 change_lookahead:
1081   {
1082     yychar = 'a';
1083   }
1084   ;
1085
1086 %%
1087
1088 static void
1089 yyerror (char const *msg)
1090 {
1091   fprintf (stderr, "%s\n", msg);
1092 }
1093
1094 static int
1095 yylex (void)
1096 {
1097   static char const *input = "ab";
1098   static int i = 0;
1099   yylloc.first_line = yylloc.last_line = 1;
1100   yylloc.first_column = yylloc.last_column = i + 1;
1101   yylval.value = input[i] + 'A' - 'a';
1102   return input[i++];
1103 }
1104
1105 static void
1106 print_look_ahead (char const *reduction)
1107 {
1108   printf ("%s:\n  yychar=", reduction);
1109   if (yychar == YYEMPTY)
1110     printf ("YYEMPTY");
1111   else if (yychar == YYEOF)
1112     printf ("YYEOF");
1113   else
1114     {
1115       printf ("'%c', yylval='", yychar);
1116       if (yylval.value > ' ')
1117         printf ("%c", yylval.value);
1118       printf ("', yylloc=(%d,%d),(%d,%d)",
1119               yylloc.first_line, yylloc.first_column,
1120               yylloc.last_line, yylloc.last_column);
1121     }
1122   printf ("\n");
1123 }
1124
1125 int
1126 main (void)
1127 {
1128   yychar = '#'; /* Not a token in the grammar.  */
1129   yylval.value = '!';
1130   return yyparse ();
1131 }
1132 ]])
1133
1134 AT_CHECK([[bison -t -o glr-regr13.c glr-regr13.y]], 0, [], [])
1135 AT_COMPILE([glr-regr13])
1136
1137 AT_CHECK([[./glr-regr13]], 0,
1138 [defstate_init <- empty string:
1139   yychar=YYEMPTY
1140 nondefstate <- empty string:
1141   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1142 defstate_look <- empty string:
1143   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1144 defstate_shift <- nondefstate defstate_look 'a':
1145   yychar=YYEMPTY
1146 start <- defstate_init defstate_shift 'b':
1147   yychar=YYEMPTY
1148 ], [])
1149
1150 AT_CLEANUP
1151
1152
1153 ## ------------------------------------------------------------------------- ##
1154 ## Incorrect lookahead during nondeterministic GLR.                          ##
1155 ## ------------------------------------------------------------------------- ##
1156
1157 AT_SETUP([Incorrect lookahead during nondeterministic GLR])
1158
1159 AT_DATA_GRAMMAR([glr-regr14.y],
1160 [[
1161 /* Tests:
1162      - Conflicting actions (split-off parse, which copies lookahead need,
1163        which is necessarily yytrue) and nonconflicting actions (non-split-off
1164        parse) for nondefaulted state: yychar != YYEMPTY.
1165      - Merged deferred actions (lookahead need and RHS from different stack
1166        than the target state) and nonmerged deferred actions (same stack).
1167      - Defaulted state after lookahead: yychar != YYEMPTY.
1168      - Defaulted state after shift: yychar == YYEMPTY.
1169      - yychar != YYEMPTY but lookahead need is yyfalse (a previous stack has
1170        seen the lookahead but current stack has not).
1171      - Exceeding stack capacity (stack explosion), and thus reallocating
1172        lookahead need array.
1173    Note that it does not seem possible to see the initial yychar value during
1174    nondeterministic operation since:
1175      - In order to preserve the initial yychar, only defaulted states may be
1176        entered.
1177      - If only defaulted states are entered, there are no conflicts, so
1178        nondeterministic operation does not start.  */
1179
1180 %union { char value; }
1181
1182 %{
1183   #include <stdio.h>
1184   static void yyerror (char const *);
1185   static int yylex (void);
1186   static void print_look_ahead (char const *);
1187   static char merge (union YYSTYPE, union YYSTYPE);
1188   #define USE(value)
1189 %}
1190
1191 %type <value> 'a' 'b' 'c' 'd' stack_explosion
1192 %glr-parser
1193 %locations
1194
1195 %%
1196
1197 start:
1198   merge 'c' stack_explosion {
1199     USE ($2); USE ($3);
1200     print_look_ahead ("start <- merge 'c' stack_explosion");
1201   }
1202   ;
1203
1204 /* When merging the 2 deferred actions, the lookahead needs are different.  */
1205 merge:
1206   nonconflict1 'a' 'b' nonconflict2 %dprec 1 {
1207     USE ($2); USE ($3);
1208     print_look_ahead ("merge <- nonconflict1 'a' 'b' nonconflict2");
1209   }
1210   | conflict defstate_look 'a' nonconflict2 'b' defstate_shift %dprec 2 {
1211     USE ($3); USE ($5);
1212     print_look_ahead ("merge <- conflict defstate_look 'a' nonconflict2 'b'"
1213                       " defstate_shift");
1214   }
1215   ;
1216
1217 nonconflict1:
1218   {
1219     print_look_ahead ("nonconflict1 <- empty string");
1220   }
1221   ;
1222 nonconflict2:
1223   {
1224     print_look_ahead ("nonconflict2 <- empty string");
1225   }
1226   | 'a' {
1227     USE ($1);
1228     print_look_ahead ("nonconflict2 <- 'a'");
1229   }
1230   ;
1231 conflict:
1232   {
1233     print_look_ahead ("conflict <- empty string");
1234   }
1235   ;
1236 defstate_look:
1237   {
1238     print_look_ahead ("defstate_look <- empty string");
1239   }
1240   ;
1241
1242 /* yychar != YYEMPTY but lookahead need is yyfalse.  */
1243 defstate_shift:
1244   {
1245     print_look_ahead ("defstate_shift <- empty string");
1246   }
1247   ;
1248
1249 stack_explosion:
1250   { $$ = '\0'; }
1251   | alt1 stack_explosion %merge<merge> { $$ = $2; }
1252   | alt2 stack_explosion %merge<merge> { $$ = $2; }
1253   | alt3 stack_explosion %merge<merge> { $$ = $2; }
1254   ;
1255 alt1:
1256   'd' no_look {
1257     USE ($1);
1258     if (yychar != 'd' && yychar != YYEOF)
1259       {
1260         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1261       }
1262   }
1263   ;
1264 alt2:
1265   'd' no_look {
1266     USE ($1);
1267     if (yychar != 'd' && yychar != YYEOF)
1268       {
1269         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1270       }
1271   }
1272   ;
1273 alt3:
1274   'd' no_look {
1275     USE ($1);
1276     if (yychar != 'd' && yychar != YYEOF)
1277       {
1278         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1279       }
1280   }
1281   ;
1282 no_look:
1283   {
1284     if (yychar != YYEMPTY)
1285       {
1286         fprintf (stderr,
1287                  "Found lookahead where shouldn't during stack explosion.\n");
1288       }
1289   }
1290   ;
1291
1292 %%
1293
1294 static void
1295 yyerror (char const *msg)
1296 {
1297   fprintf (stderr, "%s\n", msg);
1298 }
1299
1300 static int
1301 yylex (void)
1302 {
1303   static char const *input = "abcdddd";
1304   static int i = 0;
1305   yylloc.first_line = yylloc.last_line = 1;
1306   yylloc.first_column = yylloc.last_column = i + 1;
1307   yylval.value = input[i] + 'A' - 'a';
1308   return input[i++];
1309 }
1310
1311 static void
1312 print_look_ahead (char const *reduction)
1313 {
1314   printf ("%s:\n  yychar=", reduction);
1315   if (yychar == YYEMPTY)
1316     printf ("YYEMPTY");
1317   else if (yychar == YYEOF)
1318     printf ("YYEOF");
1319   else
1320     {
1321       printf ("'%c', yylval='", yychar);
1322       if (yylval.value > ' ')
1323         printf ("%c", yylval.value);
1324       printf ("', yylloc=(%d,%d),(%d,%d)",
1325               yylloc.first_line, yylloc.first_column,
1326               yylloc.last_line, yylloc.last_column);
1327     }
1328   printf ("\n");
1329 }
1330
1331 static char
1332 merge (union YYSTYPE s1, union YYSTYPE s2)
1333 {
1334   char dummy = s1.value + s2.value;
1335   return dummy;
1336 }
1337
1338 int
1339 main (void)
1340 {
1341   yychar = '#'; /* Not a token in the grammar.  */
1342   yylval.value = '!';
1343   return yyparse ();
1344 }
1345 ]])
1346
1347 AT_CHECK([[bison -t -o glr-regr14.c glr-regr14.y]], 0, [],
1348 [glr-regr14.y: conflicts: 3 reduce/reduce
1349 ])
1350 AT_COMPILE([glr-regr14])
1351
1352 AT_CHECK([[./glr-regr14]], 0,
1353 [conflict <- empty string:
1354   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1355 defstate_look <- empty string:
1356   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1357 nonconflict2 <- empty string:
1358   yychar='b', yylval='B', yylloc=(1,2),(1,2)
1359 defstate_shift <- empty string:
1360   yychar=YYEMPTY
1361 merge <- conflict defstate_look 'a' nonconflict2 'b' defstate_shift:
1362   yychar=YYEMPTY
1363 start <- merge 'c' stack_explosion:
1364   yychar=YYEOF
1365 ], [])
1366
1367 AT_CLEANUP