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(const char *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 yyerror(const char *msg)
 688 {
 689   fprintf (stderr, "error\n");
 690 }
 691
 692 static int lexIndex;
 693
 694 int yylex (void)
 695 {
 696   lexIndex += 1;
 697   switch (lexIndex)
 698     {
 699     case 1:
 700       yylloc.first_column = 1;
 701       yylloc.last_column = 9;
 702       return T_PORT;
 703     case 2:
 704       yylloc.first_column = 13;
 705       yylloc.last_column = 17;
 706       return T_PORT;
 707     default:
 708       return 0;
 709     }
 710 }
 711
 712 int
 713 main (void)
 714 {
 715   yyparse();
 716   return 0;
 717 }
 718 ]])
 719
 720 AT_CHECK([[bison -o glr-regr8.c glr-regr8.y]], 0, [],
 721 [glr-regr8.y: conflicts: 1 reduce/reduce
 722 ])
 723 AT_COMPILE([glr-regr8])
 724
 725 AT_CHECK([[./glr-regr8]], 0,
 726 [empty: 9/9
 727 1/9 - 9/9 - 13/17
 728 ],
 729 [])
 730
 731 AT_CLEANUP
 732
 733
 734 ## ------------------------------------------------------------------------- ##
 735 ## No users destructors if stack 0 deleted.  See                             ##
 736 ## <http://lists.gnu.org/archive/html/bison-patches/2005-09/msg00109.html>.  ##
 737 ## ------------------------------------------------------------------------- ##
 738
 739 AT_SETUP([No users destructors if stack 0 deleted])
 740
 741 AT_DATA_GRAMMAR([glr-regr9.y],
 742 [[
 743 %{
 744 # include <stdio.h>
 745 # include <stdlib.h>
 746   static void yyerror (char const *);
 747   static int yylex (void);
 748 # define YYSTACKEXPANDABLE 0
 749   static int tokens = 0;
 750   static int destructors = 0;
 751 # define USE(Var)
 752 %}
 753
 754 %glr-parser
 755 %union { int dummy; }
 756 %type <dummy> 'a'
 757
 758 %destructor {
 759   destructors += 1;
 760 } 'a'
 761
 762 %%
 763
 764 start:
 765     ambig0 'a'   { destructors += 2; USE ($2); }
 766   | ambig1 start { destructors += 1; }
 767   | ambig2 start { destructors += 1; }
 768   ;
 769
 770 ambig0: 'a' ;
 771 ambig1: 'a' ;
 772 ambig2: 'a' ;
 773
 774 %%
 775
 776 static int
 777 yylex (void)
 778 {
 779   tokens += 1;
 780   return 'a';
 781 }
 782
 783 static void
 784 yyerror (char const *msg)
 785 {
 786   fprintf (stderr, "%s\n", msg);
 787 }
 788
 789 int
 790 main (void)
 791 {
 792   int exit_status;
 793   exit_status = yyparse ();
 794   if (tokens != destructors)
 795     {
 796       fprintf (stderr, "Tokens = %d, Destructors = %d\n", tokens, destructors);
 797       return 1;
 798     }
 799   return !exit_status;
 800 }
 801 ]])
 802
 803 AT_CHECK([[bison -o glr-regr9.c glr-regr9.y]], 0, [],
 804 [glr-regr9.y: conflicts: 1 reduce/reduce
 805 ])
 806 AT_COMPILE([glr-regr9])
 807
 808 AT_CHECK([[./glr-regr9]], 0, [],
 809 [memory exhausted
 810 ])
 811
 812 AT_CLEANUP
 813
 814
 815 ## ------------------------------------------------------------------------- ##
 816 ## Corrupted semantic options if user action cuts parse.                     ##
 817 ## ------------------------------------------------------------------------- ##
 818
 819 AT_SETUP([Corrupted semantic options if user action cuts parse])
 820
 821 AT_DATA_GRAMMAR([glr-regr10.y],
 822 [[
 823 %{
 824 # include <stdio.h>
 825   static void yyerror (char const *);
 826   static int yylex (void);
 827   #define GARBAGE_SIZE 50
 828   static char garbage[GARBAGE_SIZE];
 829 %}
 830
 831 %glr-parser
 832 %union { char *ptr; }
 833 %type <ptr> start
 834
 835 %%
 836
 837 start:
 838     %dprec 2 { $$ = garbage; YYACCEPT; }
 839   | %dprec 1 { $$ = garbage; YYACCEPT; }
 840   ;
 841
 842 %%
 843
 844 static void
 845 yyerror (char const *msg)
 846 {
 847   fprintf (stderr, "%s\n", msg);
 848 }
 849
 850 static int
 851 yylex (void)
 852 {
 853   return 0;
 854 }
 855
 856 int
 857 main (void)
 858 {
 859   int index;
 860   for (index = 0; index < GARBAGE_SIZE; index+=1)
 861     garbage[index] = 108;
 862   return yyparse ();
 863 }
 864 ]])
 865
 866 AT_CHECK([[bison -t -o glr-regr10.c glr-regr10.y]], 0, [],
 867 [glr-regr10.y: conflicts: 1 reduce/reduce
 868 ])
 869 AT_COMPILE([glr-regr10])
 870
 871 AT_CHECK([[./glr-regr10]], 0, [], [])
 872
 873 AT_CLEANUP
 874
 875
 876 ## ------------------------------------------------------------------------- ##
 877 ## Undesirable destructors if user action cuts parse.                        ##
 878 ## ------------------------------------------------------------------------- ##
 879
 880 AT_SETUP([Undesirable destructors if user action cuts parse])
 881
 882 AT_DATA_GRAMMAR([glr-regr11.y],
 883 [[
 884 %{
 885 # include <stdlib.h>
 886   static void yyerror (char const *);
 887   static int yylex (void);
 888   static int destructors = 0;
 889 # define USE(val)
 890 %}
 891
 892 %glr-parser
 893 %union { int dummy; }
 894 %type <int> 'a'
 895 %destructor { destructors += 1; } 'a'
 896
 897 %%
 898
 899 start:
 900     'a' %dprec 2 { USE ($1); destructors += 1; YYACCEPT; }
 901   | 'a' %dprec 1 { USE ($1); destructors += 1; YYACCEPT; }
 902   ;
 903
 904 %%
 905
 906 static void
 907 yyerror (char const *msg)
 908 {
 909   fprintf (stderr, "%s\n", msg);
 910 }
 911
 912 static int
 913 yylex (void)
 914 {
 915   static char const *input = "a";
 916   return *input++;
 917 }
 918
 919 int
 920 main (void)
 921 {
 922   int exit_status = yyparse ();
 923   if (destructors != 1)
 924     {
 925       fprintf (stderr, "Destructor calls: %d\n", destructors);
 926       return 1;
 927     }
 928   return exit_status;
 929 }
 930 ]])
 931
 932 AT_CHECK([[bison -t -o glr-regr11.c glr-regr11.y]], 0, [],
 933 [glr-regr11.y: conflicts: 1 reduce/reduce
 934 ])
 935 AT_COMPILE([glr-regr11])
 936
 937 AT_CHECK([[./glr-regr11]], 0, [], [])
 938
 939 AT_CLEANUP
 940
 941
 942 ## ------------------------------------------------------------------------- ##
 943 ## Leaked merged semantic value if user action cuts parse.                   ##
 944 ## ------------------------------------------------------------------------- ##
 945
 946 AT_SETUP([Leaked merged semantic value if user action cuts parse])
 947
 948 AT_DATA_GRAMMAR([glr-regr12.y],
 949 [[
 950 %glr-parser
 951 %union { int dummy; }
 952 %type <dummy> start
 953 %destructor { has_value = 0; } start
 954
 955 %{
 956 # include <stdlib.h>
 957   static int merge (YYSTYPE, YYSTYPE);
 958   static void yyerror (char const *);
 959   static int yylex (void);
 960   static int has_value = 0;
 961 # define USE(val)
 962 %}
 963
 964 %%
 965
 966 start:
 967     %merge<merge> { has_value = 1; USE ($$); }
 968   | %merge<merge> { USE ($$); YYACCEPT; }
 969   ;
 970
 971 %%
 972
 973 static int
 974 merge (YYSTYPE s1, YYSTYPE s2)
 975 {
 976   /* Not invoked. */
 977   char dummy = s1.dummy + s2.dummy;
 978   return dummy;
 979 }
 980
 981 static void
 982 yyerror (char const *msg)
 983 {
 984   fprintf (stderr, "%s\n", msg);
 985 }
 986
 987 static int
 988 yylex (void)
 989 {
 990   return 0;
 991 }
 992
 993 int
 994 main (void)
 995 {
 996   int exit_status = yyparse ();
 997   if (has_value)
 998     {
 999       fprintf (stderr, "Destructor not called.\n");
1000       return 1;
1001     }
1002   return exit_status;
1003 }
1004 ]])
1005
1006 AT_CHECK([[bison -t -o glr-regr12.c glr-regr12.y]], 0, [],
1007 [glr-regr12.y: conflicts: 1 reduce/reduce
1008 ])
1009 AT_COMPILE([glr-regr12])
1010
1011 AT_CHECK([[./glr-regr12]], 0, [], [])
1012
1013 AT_CLEANUP
1014
1015
1016 ## ------------------------------------------------------------------------- ##
1017 ## Incorrect lookahead during deterministic GLR.  See                        ##
1018 ## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00017.html>.     ##
1019 ## ------------------------------------------------------------------------- ##
1020
1021 AT_SETUP([Incorrect lookahead during deterministic GLR])
1022
1023 AT_DATA_GRAMMAR([glr-regr13.y],
1024 [[
1025 /* Tests:
1026      - Defaulted state with initial yychar: yychar == YYEMPTY.
1027      - Nondefaulted state: yychar != YYEMPTY.
1028      - Defaulted state after lookahead: yychar != YYEMPTY.
1029      - Defaulted state after shift: yychar == YYEMPTY.  */
1030
1031 %{
1032   #include <stdio.h>
1033   static void yyerror (char const *);
1034   static int yylex (void);
1035   static void print_look_ahead (char const *);
1036   #define USE(value)
1037 %}
1038
1039 %union { char value; }
1040 %type <value> 'a' 'b'
1041 %glr-parser
1042 %locations
1043
1044 %%
1045
1046 start:
1047   defstate_init defstate_shift 'b' {
1048     USE ($3);
1049     print_look_ahead ("start <- defstate_init defstate_shift 'b'");
1050   }
1051   ;
1052 defstate_init:
1053   {
1054     print_look_ahead ("defstate_init <- empty string");
1055   }
1056   ;
1057 defstate_shift:
1058   nondefstate defstate_look 'a' {
1059     USE ($3);
1060     print_look_ahead ("defstate_shift <- nondefstate defstate_look 'a'");
1061   }
1062   ;
1063 defstate_look:
1064   {
1065     print_look_ahead ("defstate_look <- empty string");
1066   }
1067   ;
1068 nondefstate:
1069   {
1070     print_look_ahead ("nondefstate <- empty string");
1071   }
1072   | 'b' {
1073     USE ($1);
1074     print_look_ahead ("nondefstate <- 'b'");
1075   }
1076   ;
1077
1078 %%
1079
1080 static void
1081 yyerror (char const *msg)
1082 {
1083   fprintf (stderr, "%s\n", msg);
1084 }
1085
1086 static int
1087 yylex (void)
1088 {
1089   static char const *input = "ab";
1090   static int index = 0;
1091   yylloc.first_line = yylloc.last_line = 1;
1092   yylloc.first_column = yylloc.last_column = index+1;
1093   yylval.value = input[index] + 'A' - 'a';
1094   return input[index++];
1095 }
1096
1097 static void
1098 print_look_ahead (char const *reduction)
1099 {
1100   printf ("%s:\n  yychar=", reduction);
1101   if (yychar == YYEMPTY)
1102     printf ("YYEMPTY");
1103   else if (yychar == YYEOF)
1104     printf ("YYEOF");
1105   else
1106     {
1107       printf ("'%c', yylval='", yychar);
1108       if (yylval.value > ' ')
1109         printf ("%c", yylval.value);
1110       printf ("', yylloc=(%d,%d),(%d,%d)",
1111               yylloc.first_line, yylloc.first_column,
1112               yylloc.last_line, yylloc.last_column);
1113     }
1114   printf ("\n");
1115 }
1116
1117 int
1118 main (void)
1119 {
1120   yychar = '#'; /* Not a token in the grammar.  */
1121   yylval.value = '!';
1122   return yyparse ();
1123 }
1124 ]])
1125
1126 AT_CHECK([[bison -t -o glr-regr13.c glr-regr13.y]], 0, [], [])
1127 AT_COMPILE([glr-regr13])
1128
1129 AT_CHECK([[./glr-regr13]], 0,
1130 [defstate_init <- empty string:
1131   yychar=YYEMPTY
1132 nondefstate <- empty string:
1133   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1134 defstate_look <- empty string:
1135   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1136 defstate_shift <- nondefstate defstate_look 'a':
1137   yychar=YYEMPTY
1138 start <- defstate_init defstate_shift 'b':
1139   yychar=YYEMPTY
1140 ], [])
1141
1142 AT_CLEANUP
1143
1144
1145 ## ------------------------------------------------------------------------- ##
1146 ## Incorrect lookahead during nondeterministic GLR.                          ##
1147 ## ------------------------------------------------------------------------- ##
1148
1149 AT_SETUP([Incorrect lookahead during nondeterministic GLR])
1150
1151 AT_DATA_GRAMMAR([glr-regr14.y],
1152 [[
1153 /* Tests:
1154      - Conflicting actions (split-off parse, which copies lookahead need,
1155        which is necessarily yytrue) and nonconflicting actions (non-split-off
1156        parse) for nondefaulted state: yychar != YYEMPTY.
1157      - Merged deferred actions (lookahead need and RHS from different stack
1158        than the target state) and nonmerged deferred actions (same stack).
1159      - Defaulted state after lookahead: yychar != YYEMPTY.
1160      - Defaulted state after shift: yychar == YYEMPTY.
1161      - yychar != YYEMPTY but lookahead need is yyfalse (a previous stack has
1162        seen the lookahead but current stack has not).
1163      - Exceeding stack capacity (stack explosion), and thus reallocating
1164        lookahead need array.
1165    Note that it does not seem possible to see the initial yychar value during
1166    nondeterministic operation since:
1167      - In order to preserve the initial yychar, only defaulted states may be
1168        entered.
1169      - If only defaulted states are entered, there are no conflicts, so
1170        nondeterministic operation does not start.  */
1171
1172 %union { char value; }
1173
1174 %{
1175   #include <stdio.h>
1176   static void yyerror (char const *);
1177   static int yylex (void);
1178   static void print_look_ahead (char const *);
1179   static char merge (union YYSTYPE, union YYSTYPE);
1180   #define USE(value)
1181 %}
1182
1183 %type <value> 'a' 'b' 'c' 'd' stack_explosion
1184 %glr-parser
1185 %locations
1186
1187 %%
1188
1189 start:
1190   merge 'c' stack_explosion {
1191     USE ($2); USE ($3);
1192     print_look_ahead ("start <- merge 'c' stack_explosion");
1193   }
1194   ;
1195
1196 /* When merging the 2 deferred actions, the lookahead needs are different.  */
1197 merge:
1198   nonconflict1 'a' 'b' nonconflict2 %dprec 1 {
1199     USE ($2); USE ($3);
1200     print_look_ahead ("merge <- nonconflict1 'a' 'b' nonconflict2");
1201   }
1202   | conflict defstate_look 'a' nonconflict2 'b' defstate_shift %dprec 2 {
1203     USE ($3); USE ($5);
1204     print_look_ahead ("merge <- conflict defstate_look 'a' nonconflict2 'b'"
1205                       " defstate_shift");
1206   }
1207   ;
1208
1209 nonconflict1:
1210   {
1211     print_look_ahead ("nonconflict1 <- empty string");
1212   }
1213   ;
1214 nonconflict2:
1215   {
1216     print_look_ahead ("nonconflict2 <- empty string");
1217   }
1218   | 'a' {
1219     USE ($1);
1220     print_look_ahead ("nonconflict2 <- 'a'");
1221   }
1222   ;
1223 conflict:
1224   {
1225     print_look_ahead ("conflict <- empty string");
1226   }
1227   ;
1228 defstate_look:
1229   {
1230     print_look_ahead ("defstate_look <- empty string");
1231   }
1232   ;
1233
1234 /* yychar != YYEMPTY but lookahead need is yyfalse.  */
1235 defstate_shift:
1236   {
1237     print_look_ahead ("defstate_shift <- empty string");
1238   }
1239   ;
1240
1241 stack_explosion:
1242   { $$ = '\0'; }
1243   | alt1 stack_explosion %merge<merge> { $$ = $2; }
1244   | alt2 stack_explosion %merge<merge> { $$ = $2; }
1245   | alt3 stack_explosion %merge<merge> { $$ = $2; }
1246   ;
1247 alt1:
1248   'd' no_look {
1249     USE ($1);
1250     if (yychar != 'd' && yychar != YYEOF)
1251       {
1252         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1253       }
1254   }
1255   ;
1256 alt2:
1257   'd' no_look {
1258     USE ($1);
1259     if (yychar != 'd' && yychar != YYEOF)
1260       {
1261         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1262       }
1263   }
1264   ;
1265 alt3:
1266   'd' no_look {
1267     USE ($1);
1268     if (yychar != 'd' && yychar != YYEOF)
1269       {
1270         fprintf (stderr, "Incorrect lookahead during stack explosion.\n");
1271       }
1272   }
1273   ;
1274 no_look:
1275   {
1276     if (yychar != YYEMPTY)
1277       {
1278         fprintf (stderr,
1279                  "Found lookahead where shouldn't during stack explosion.\n");
1280       }
1281   }
1282   ;
1283
1284 %%
1285
1286 static void
1287 yyerror (char const *msg)
1288 {
1289   fprintf (stderr, "%s\n", msg);
1290 }
1291
1292 static int
1293 yylex (void)
1294 {
1295   static char const *input = "abcdddd";
1296   static int index = 0;
1297   yylloc.first_line = yylloc.last_line = 1;
1298   yylloc.first_column = yylloc.last_column = index+1;
1299   yylval.value = input[index] + 'A' - 'a';
1300   return input[index++];
1301 }
1302
1303 static void
1304 print_look_ahead (char const *reduction)
1305 {
1306   printf ("%s:\n  yychar=", reduction);
1307   if (yychar == YYEMPTY)
1308     printf ("YYEMPTY");
1309   else if (yychar == YYEOF)
1310     printf ("YYEOF");
1311   else
1312     {
1313       printf ("'%c', yylval='", yychar);
1314       if (yylval.value > ' ')
1315         printf ("%c", yylval.value);
1316       printf ("', yylloc=(%d,%d),(%d,%d)",
1317               yylloc.first_line, yylloc.first_column,
1318               yylloc.last_line, yylloc.last_column);
1319     }
1320   printf ("\n");
1321 }
1322
1323 static char
1324 merge (union YYSTYPE s1, union YYSTYPE s2)
1325 {
1326   char dummy = s1.value + s2.value;
1327   return dummy;
1328 }
1329
1330 int
1331 main (void)
1332 {
1333   yychar = '#'; /* Not a token in the grammar.  */
1334   yylval.value = '!';
1335   return yyparse ();
1336 }
1337 ]])
1338
1339 AT_CHECK([[bison -t -o glr-regr14.c glr-regr14.y]], 0, [],
1340 [glr-regr14.y: conflicts: 3 reduce/reduce
1341 ])
1342 AT_COMPILE([glr-regr14])
1343
1344 AT_CHECK([[./glr-regr14]], 0,
1345 [conflict <- empty string:
1346   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1347 defstate_look <- empty string:
1348   yychar='a', yylval='A', yylloc=(1,1),(1,1)
1349 nonconflict2 <- empty string:
1350   yychar='b', yylval='B', yylloc=(1,2),(1,2)
1351 defstate_shift <- empty string:
1352   yychar=YYEMPTY
1353 merge <- conflict defstate_look 'a' nonconflict2 'b' defstate_shift:
1354   yychar=YYEMPTY
1355 start <- merge 'c' stack_explosion:
1356   yychar=YYEOF
1357 ], [])
1358
1359 AT_CLEANUP