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>.     ##
1020 ## ------------------------------------------------------------------------- ##
1021
1022 AT_SETUP([Incorrect lookahead during deterministic GLR])
1023
1024 AT_DATA_GRAMMAR([glr-regr13.y],
1025 [[
1026 /* Tests:
1027      - Defaulted state with initial yychar: yychar == YYEMPTY.
1028      - Nondefaulted state: yychar != YYEMPTY.
1029      - Defaulted state after lookahead: yychar != YYEMPTY.
1030      - Defaulted state after shift: yychar == YYEMPTY.  */
1031
1032 %{
1033   #include <stdio.h>
1034   static void yyerror (char const *);
1035   static int yylex (void);
1036   static void print_look_ahead (char const *);
1037   #define USE(value)
1038 %}
1039
1040 %union { char value; }
1041 %type <value> 'a' 'b'
1042 %glr-parser
1043 %locations
1044
1045 %%
1046
1047 start:
1048   defstate_init defstate_shift 'b' {
1049     USE ($3);
1050     print_look_ahead ("start <- defstate_init defstate_shift 'b'");
1051   }
1052   ;
1053 defstate_init:
1054   {
1055     print_look_ahead ("defstate_init <- empty string");
1056   }
1057   ;
1058 defstate_shift:
1059   nondefstate defstate_look 'a' {
1060     USE ($3);
1061     print_look_ahead ("defstate_shift <- nondefstate defstate_look 'a'");
1062   }
1063   ;
1064 defstate_look:
1065   {
1066     print_look_ahead ("defstate_look <- empty string");
1067   }
1068   ;
1069 nondefstate:
1070   {
1071     print_look_ahead ("nondefstate <- empty string");
1072   }
1073   | 'b' {
1074     USE ($1);
1075     print_look_ahead ("nondefstate <- 'b'");
1076   }
1077   ;
1078
1079 %%
1080
1081 static void
1082 yyerror (char const *msg)
1083 {
1084   fprintf (stderr, "%s\n", msg);
1085 }
1086
1087 static int
1088 yylex (void)
1089 {
1090   static char const *input = "ab";
1091   static int i = 0;
1092   yylloc.first_line = yylloc.last_line = 1;
1093   yylloc.first_column = yylloc.last_column = i + 1;
1094   yylval.value = input[i] + 'A' - 'a';
1095   return input[i++];
1096 }
1097
1098 static void
1099 print_look_ahead (char const *reduction)
1100 {
1101   printf ("%s:\n  yychar=", reduction);
1102   if (yychar == YYEMPTY)
1103     printf ("YYEMPTY");
1104   else if (yychar == YYEOF)
1105     printf ("YYEOF");
1106   else
1107     {
1108       printf ("'%c', yylval='", yychar);
1109       if (yylval.value > ' ')
1110         printf ("%c", yylval.value);
1111       printf ("', yylloc=(%d,%d),(%d,%d)",
1112               yylloc.first_line, yylloc.first_column,
1113               yylloc.last_line, yylloc.last_column);
1114     }
1115   printf ("\n");
1116 }
1117
1118 int
1119 main (void)
1120 {
1121   yychar = '#'; /* Not a token in the grammar.  */
1122   yylval.value = '!';
1123   return yyparse ();
1124 }
1125 ]])
1126
1127 AT_CHECK([[bison -t -o glr-regr13.c glr-regr13.y]], 0, [], [])
1128 AT_COMPILE([glr-regr13])
1129
1130 AT_CHECK([[./glr-regr13]], 0,
1131 [defstate_init <- empty string:
1132   yychar=YYEMPTY
1133 nondefstate <- empty string:
1134   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1135 defstate_look <- empty string:
1136   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1137 defstate_shift <- nondefstate defstate_look 'a':
1138   yychar=YYEMPTY
1139 start <- defstate_init defstate_shift 'b':
1140   yychar=YYEMPTY
1141 ], [])
1142
1143 AT_CLEANUP
1144
1145
1146 ## ------------------------------------------------------------------------- ##
1147 ## Incorrect lookahead during nondeterministic GLR.                          ##
1148 ## ------------------------------------------------------------------------- ##
1149
1150 AT_SETUP([Incorrect lookahead during nondeterministic GLR])
1151
1152 AT_DATA_GRAMMAR([glr-regr14.y],
1153 [[
1154 /* Tests:
1155      - Conflicting actions (split-off parse, which copies lookahead need,
1156        which is necessarily yytrue) and nonconflicting actions (non-split-off
1157        parse) for nondefaulted state: yychar != YYEMPTY.
1158      - Merged deferred actions (lookahead need and RHS from different stack
1159        than the target state) and nonmerged deferred actions (same stack).
1160      - Defaulted state after lookahead: yychar != YYEMPTY.
1161      - Defaulted state after shift: yychar == YYEMPTY.
1162      - yychar != YYEMPTY but lookahead need is yyfalse (a previous stack has
1163        seen the lookahead but current stack has not).
1164      - Exceeding stack capacity (stack explosion), and thus reallocating
1165        lookahead need array.
1166    Note that it does not seem possible to see the initial yychar value during
1167    nondeterministic operation since:
1168      - In order to preserve the initial yychar, only defaulted states may be
1169        entered.
1170      - If only defaulted states are entered, there are no conflicts, so
1171        nondeterministic operation does not start.  */
1172
1173 %union { char value; }
1174
1175 %{
1176   #include <stdio.h>
1177   static void yyerror (char const *);
1178   static int yylex (void);
1179   static void print_look_ahead (char const *);
1180   static char merge (union YYSTYPE, union YYSTYPE);
1181   #define USE(value)
1182 %}
1183
1184 %type <value> 'a' 'b' 'c' 'd' stack_explosion
1185 %glr-parser
1186 %locations
1187
1188 %%
1189
1190 start:
1191   merge 'c' stack_explosion {
1192     USE ($2); USE ($3);
1193     print_look_ahead ("start <- merge 'c' stack_explosion");
1194   }
1195   ;
1196
1197 /* When merging the 2 deferred actions, the lookahead needs are different.  */
1198 merge:
1199   nonconflict1 'a' 'b' nonconflict2 %dprec 1 {
1200     USE ($2); USE ($3);
1201     print_look_ahead ("merge <- nonconflict1 'a' 'b' nonconflict2");
1202   }
1203   | conflict defstate_look 'a' nonconflict2 'b' defstate_shift %dprec 2 {
1204     USE ($3); USE ($5);
1205     print_look_ahead ("merge <- conflict defstate_look 'a' nonconflict2 'b'"
1206                       " defstate_shift");
1207   }
1208   ;
1209
1210 nonconflict1:
1211   {
1212     print_look_ahead ("nonconflict1 <- empty string");
1213   }
1214   ;
1215 nonconflict2:
1216   {
1217     print_look_ahead ("nonconflict2 <- empty string");
1218   }
1219   | 'a' {
1220     USE ($1);
1221     print_look_ahead ("nonconflict2 <- 'a'");
1222   }
1223   ;
1224 conflict:
1225   {
1226     print_look_ahead ("conflict <- empty string");
1227   }
1228   ;
1229 defstate_look:
1230   {
1231     print_look_ahead ("defstate_look <- empty string");
1232   }
1233   ;
1234
1235 /* yychar != YYEMPTY but lookahead need is yyfalse.  */
1236 defstate_shift:
1237   {
1238     print_look_ahead ("defstate_shift <- empty string");
1239   }
1240   ;
1241
1242 stack_explosion:
1243   { $$ = '\0'; }
1244   | alt1 stack_explosion %merge<merge> { $$ = $2; }
1245   | alt2 stack_explosion %merge<merge> { $$ = $2; }
1246   | alt3 stack_explosion %merge<merge> { $$ = $2; }
1247   ;
1248 alt1:
1249   'd' no_look {
1250     USE ($1);
1251     if (yychar != 'd' && yychar != YYEOF)
1252       {
1253         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1254       }
1255   }
1256   ;
1257 alt2:
1258   'd' no_look {
1259     USE ($1);
1260     if (yychar != 'd' && yychar != YYEOF)
1261       {
1262         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1263       }
1264   }
1265   ;
1266 alt3:
1267   'd' no_look {
1268     USE ($1);
1269     if (yychar != 'd' && yychar != YYEOF)
1270       {
1271         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1272       }
1273   }
1274   ;
1275 no_look:
1276   {
1277     if (yychar != YYEMPTY)
1278       {
1279         fprintf (stderr,
1280                  "Found lookahead where shouldn't during stack explosion.\n");
1281       }
1282   }
1283   ;
1284
1285 %%
1286
1287 static void
1288 yyerror (char const *msg)
1289 {
1290   fprintf (stderr, "%s\n", msg);
1291 }
1292
1293 static int
1294 yylex (void)
1295 {
1296   static char const *input = "abcdddd";
1297   static int i = 0;
1298   yylloc.first_line = yylloc.last_line = 1;
1299   yylloc.first_column = yylloc.last_column = i + 1;
1300   yylval.value = input[i] + 'A' - 'a';
1301   return input[i++];
1302 }
1303
1304 static void
1305 print_look_ahead (char const *reduction)
1306 {
1307   printf ("%s:\n  yychar=", reduction);
1308   if (yychar == YYEMPTY)
1309     printf ("YYEMPTY");
1310   else if (yychar == YYEOF)
1311     printf ("YYEOF");
1312   else
1313     {
1314       printf ("'%c', yylval='", yychar);
1315       if (yylval.value > ' ')
1316         printf ("%c", yylval.value);
1317       printf ("', yylloc=(%d,%d),(%d,%d)",
1318               yylloc.first_line, yylloc.first_column,
1319               yylloc.last_line, yylloc.last_column);
1320     }
1321   printf ("\n");
1322 }
1323
1324 static char
1325 merge (union YYSTYPE s1, union YYSTYPE s2)
1326 {
1327   char dummy = s1.value + s2.value;
1328   return dummy;
1329 }
1330
1331 int
1332 main (void)
1333 {
1334   yychar = '#'; /* Not a token in the grammar.  */
1335   yylval.value = '!';
1336   return yyparse ();
1337 }
1338 ]])
1339
1340 AT_CHECK([[bison -t -o glr-regr14.c glr-regr14.y]], 0, [],
1341 [glr-regr14.y: conflicts: 3 reduce/reduce
1342 ])
1343 AT_COMPILE([glr-regr14])
1344
1345 AT_CHECK([[./glr-regr14]], 0,
1346 [conflict <- empty string:
1347   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1348 defstate_look <- empty string:
1349   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1350 nonconflict2 <- empty string:
1351   yychar='b', yylval='B', yylloc=(1,2),(1,2)
1352 defstate_shift <- empty string:
1353   yychar=YYEMPTY
1354 merge <- conflict defstate_look 'a' nonconflict2 'b' defstate_shift:
1355   yychar=YYEMPTY
1356 start <- merge 'c' stack_explosion:
1357   yychar=YYEOF
1358 ], [])
1359
1360 AT_CLEANUP