tests/glr-regression.at

   1 # Checking GLR Parsing: Regression Tests           -*- Autotest -*-
   2 # Copyright (C) 2002, 2003, 2005 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 const *
 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   | 's' var_list 't' 'e'
 142        { printf ("Varlist: '%s'\n", $2); }
 143   | 's' var 't' var_printer 'x'
 144   ;
 145
 146 var:
 147   'V'
 148      { $$ = $1; }
 149   ;
 150
 151 var_list:
 152   var
 153     { $$ = $1; }
 154   | var ',' var_list
 155     {
 156       char *s = (char *) malloc (strlen ($1) + 1 + strlen ($3) + 1);
 157       strcpy (s, $1);
 158       strcat (s, ",");
 159       strcat (s, $3);
 160       $$ = s;
 161     }
 162   ;
 163
 164 var_printer: 'v'
 165    { printf ("Variable: '%s'\n", $-1); }
 166
 167 %%
 168
 169 FILE *input = NULL;
 170
 171 int
 172 yylex (void)
 173 {
 174   char buf[50];
 175   char *s;
 176   switch (fscanf (input, " %1[a-z,]", buf)) {
 177   case 1:
 178     return buf[0];
 179   case EOF:
 180     return 0;
 181   default:
 182     break;
 183   }
 184   if (fscanf (input, "%49s", buf) != 1)
 185     return 0;
 186   if (sizeof buf - 1 <= strlen (buf))
 187     abort ();
 188   s = (char *) malloc (strlen (buf) + 1);
 189   strcpy (s, buf);
 190   yylval = s;
 191   return 'V';
 192 }
 193
 194 void
 195 yyerror (char const *s)
 196 { printf ("%s\n", s);
 197 }
 198
 199 int
 200 main (int argc, char **argv)
 201 {
 202   input = stdin;
 203   if (argc == 2 && !(input = fopen (argv[1], "r"))) return 3;
 204   return yyparse ();
 205 }
 206 ]])
 207
 208 AT_CHECK([[bison -o glr-regr2a.c glr-regr2a.y]], 0, [],
 209 [glr-regr2a.y: conflicts: 2 shift/reduce
 210 ])
 211 AT_COMPILE([glr-regr2a])
 212
 213 AT_CHECK([[echo s VARIABLE_1 t v x q | ./glr-regr2a]], 0,
 214 [[Variable: 'VARIABLE_1'
 215 ]], [])
 216 AT_CHECK([[echo s VARIABLE_1 , ANOTHER_VARIABLE_2 t e | ./glr-regr2a]], 0,
 217 [[Varlist: 'VARIABLE_1,ANOTHER_VARIABLE_2'
 218 ]])
 219 AT_CHECK([[echo s VARIABLE_3 t v x | ./glr-regr2a]], 0,
 220 [[Variable: 'VARIABLE_3'
 221 ]], [])
 222
 223
 224 AT_CLEANUP
 225
 226 ## ------------------------------------------------------------ ##
 227 ## Improper merging of GLR delayed action sets                  ##
 228 ## ------------------------------------------------------------ ##
 229
 230 AT_SETUP([Improper merging of GLR delayed action sets])
 231
 232 AT_DATA_GRAMMAR([glr-regr3.y],
 233 [[/* Regression Test: Improper merging of GLR delayed action sets.  */
 234 /* Reported by M. Rosien */
 235
 236 %{
 237 #include <stdio.h>
 238 #include <stdarg.h>
 239
 240 static int MergeRule (int x0, int x1);
 241 static void yyerror(char const * s);
 242 int yylex (void);
 243
 244 #define RULE(x) (1 << (x))
 245
 246 %}
 247
 248 %glr-parser
 249
 250 %token BAD_CHAR
 251 %token P1 P2 T1 T2 T3 T4 O1 O2
 252
 253 %%
 254
 255 S : P1 T4 O2 NT6 P2  { printf ("Result: %x\n", $4); }
 256 ;
 257
 258 NT1 : P1 T1 O1 T2 P2 { $$ = RULE(2); }  %merge<MergeRule>
 259 ;
 260
 261 NT2 : NT1             { $$ = RULE(3); } %merge<MergeRule>
 262     | P1 NT1 O1 T3 P2 { $$ = RULE(4); } %merge<MergeRule>
 263 ;
 264
 265 NT3 : T3              { $$ = RULE(5); } %merge<MergeRule>
 266     | P1 NT1 O1 T3 P2 { $$ = RULE(6); } %merge<MergeRule>
 267 ;
 268
 269 NT4 : NT3              { $$ = RULE(7); } %merge<MergeRule>
 270     | NT2              { $$ = RULE(8); } %merge<MergeRule>
 271     | P1 NT2 O1 NT3 P2 { $$ = RULE(9); } %merge<MergeRule>
 272 ;
 273
 274 NT5 : NT4              { $$ = RULE(10); } %merge<MergeRule>
 275 ;
 276
 277 NT6 : P1 NT1 O1 T3 P2  { $$ = RULE(11) | $2; } %merge<MergeRule>
 278     | NT5              { $$ = RULE(12) | $1; } %merge<MergeRule>
 279 ;
 280
 281 %%
 282
 283 static int MergeRule (int x0, int x1) {
 284   return x0 | x1;
 285 }
 286
 287 static void yyerror(char const * s) {
 288   fprintf(stderr,"error: %s\n",s);
 289 }
 290
 291 FILE *input = NULL;
 292
 293 int P[] = { P1, P2 };
 294 int O[] = { O1, O2 };
 295 int T[] = { T1, T2, T3, T4 };
 296
 297 int yylex (void)
 298 {
 299   char inp[3];
 300   if (fscanf (input, "%2s", inp) == EOF)
 301     return 0;
 302   switch (inp[0])
 303     {
 304     case 'p': return P[inp[1] - '1'];
 305     case 't': return T[inp[1] - '1'];
 306     case 'o': return O[inp[1] - '1'];
 307     }
 308   return BAD_CHAR;
 309 }
 310
 311 int main(int argc, char* argv[]) {
 312   input = stdin;
 313   if (argc == 2 && !(input = fopen (argv[1], "r"))) return 3;
 314   return yyparse ();
 315 }
 316 ]])
 317
 318 AT_CHECK([[bison -o glr-regr3.c glr-regr3.y]], 0, [],
 319 [glr-regr3.y: conflicts: 1 shift/reduce, 1 reduce/reduce
 320 ])
 321 AT_COMPILE([glr-regr3])
 322
 323 AT_CHECK([[echo p1 t4 o2 p1 p1 t1 o1 t2 p2 o1 t3 p2 p2 | ./glr-regr3]], 0,
 324 [[Result: 1c04
 325 ]], [])
 326
 327 AT_CLEANUP
 328
 329
 330 ## ---------------------------------------------------------------------- ##
 331 ## Duplicate representation of merged trees                               ##
 332 ## Thanks to Joel E. Denny for this test; see                             ##
 333 ## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>.  ##
 334 ## ---------------------------------------------------------------------- ##
 335
 336 AT_SETUP([Duplicate representation of merged trees])
 337
 338 AT_DATA_GRAMMAR([glr-regr4.y],
 339 [[
 340 %union { char *ptr; }
 341 %type <ptr> S A A1 A2 B
 342 %glr-parser
 343
 344 %{
 345   #include <stdio.h>
 346   #include <stdlib.h>
 347   #include <string.h>
 348   static char *merge (YYSTYPE, YYSTYPE);
 349   static char *make_value (char const *, char const *);
 350   static void yyerror (char const *);
 351   static int yylex (void);
 352 %}
 353
 354 %%
 355
 356 tree: S { printf ("%s\n", $1); } ;
 357
 358 S:
 359   A   %merge<merge> { $$ = make_value ("S", $1); }
 360   | B %merge<merge> { $$ = make_value ("S", $1); }
 361   ;
 362
 363 A:
 364   A1   %merge<merge> { $$ = make_value ("A", $1); }
 365   | A2 %merge<merge> { $$ = make_value ("A", $1); }
 366   ;
 367
 368 A1: 'a' { $$ = make_value ("A1", "'a'"); } ;
 369 A2: 'a' { $$ = make_value ("A2", "'a'"); } ;
 370 B:  'a' { $$ = make_value ("B", "'a'");  } ;
 371
 372 %%
 373
 374 static int
 375 yylex (void)
 376 {
 377   static char const *input = "a";
 378   return *input++;
 379 }
 380
 381 int
 382 main (void)
 383 {
 384   return yyparse ();
 385 }
 386
 387 static char *
 388 make_value (char const *parent, char const *child)
 389 {
 390   char const format[] = "%s <- %s";
 391   char *value =
 392     (char *) malloc (strlen (parent) + strlen (child) + sizeof format);
 393   sprintf (value, format, parent, child);
 394   return value;
 395 }
 396
 397 static char *
 398 merge (YYSTYPE s1, YYSTYPE s2)
 399 {
 400   char const format[] = "merge{ %s and %s }";
 401   char *value =
 402     (char *) malloc (strlen (s1.ptr) + strlen (s2.ptr) + sizeof format);
 403   sprintf (value, format, s1.ptr, s2.ptr);
 404   return value;
 405 }
 406
 407 static void
 408 yyerror (char const *msg)
 409 {
 410   fprintf (stderr, "%s\n", msg);
 411 }
 412 ]])
 413
 414 AT_CHECK([[bison -o glr-regr4.c glr-regr4.y]], 0, [],
 415 [glr-regr4.y: conflicts: 1 reduce/reduce
 416 ])
 417 AT_COMPILE([glr-regr4])
 418
 419 AT_CHECK([[./glr-regr4]], 0,
 420 [[merge{ S <- merge{ A <- A1 <- 'a' and A <- A2 <- 'a' } and S <- B <- 'a' }
 421 ]], [])
 422
 423 AT_CLEANUP
 424
 425
 426 ## ------------------------------------------------------------------------- ##
 427 ## User destructor for unresolved GLR semantic value                         ##
 428 ## Thanks to Joel E. Denny for this test; 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                       ##
 499 ## Thanks to Joel E. Denny for this test; see                                ##
 500 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00029.html>.  ##
 501 ## ------------------------------------------------------------------------- ##
 502
 503 AT_SETUP([User destructor after an error during a split parse])
 504
 505 AT_DATA_GRAMMAR([glr-regr6.y],
 506 [[
 507 %{
 508   #include <stdio.h>
 509   #include <stdlib.h>
 510   static void yyerror (char const *);
 511   static int yylex (void);
 512 %}
 513
 514 %glr-parser
 515 %union { int value; }
 516 %type <value> 'a'
 517
 518 %destructor {
 519   printf ("Destructor called.\n");
 520 } 'a'
 521
 522 %%
 523
 524 start: 'a' | 'a' ;
 525
 526 %%
 527
 528 static int
 529 yylex (void)
 530 {
 531   static char const *input = "a";
 532   return *input++;
 533 }
 534
 535 static void
 536 yyerror (char const *msg)
 537 {
 538   fprintf (stderr, "%s\n", msg);
 539 }
 540
 541 int
 542 main (void)
 543 {
 544   return yyparse () != 1;
 545 }
 546 ]])
 547
 548 AT_CHECK([[bison -o glr-regr6.c glr-regr6.y]], 0, [],
 549 [glr-regr6.y: conflicts: 1 reduce/reduce
 550 ])
 551 AT_COMPILE([glr-regr6])
 552
 553 AT_CHECK([[./glr-regr6]], 0,
 554 [Destructor called.
 555 ],
 556 [syntax is ambiguous
 557 ])
 558
 559 AT_CLEANUP
 560
 561
 562 ## ------------------------------------------------------------------------- ##
 563 ## Duplicated user destructor for lookahead                                  ##
 564 ## Thanks to Joel E. Denny for this test; see                                ##
 565 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00035.html>.  ##
 566 ## ------------------------------------------------------------------------- ##
 567
 568 AT_SETUP([Duplicated user destructor for lookahead])
 569
 570 AT_DATA_GRAMMAR([glr-regr7.y],
 571 [[
 572 %{
 573   #include <stdio.h>
 574   #include <stdlib.h>
 575   static void yyerror (char const *);
 576   static int yylex (void);
 577   #define YYSTACKEXPANDABLE 0
 578 %}
 579
 580 %glr-parser
 581 %union { int *count; }
 582 %type <count> 'a'
 583
 584 %destructor {
 585   if ((*$$)++)
 586     fprintf (stderr, "Destructor called on same value twice.\n");
 587 } 'a'
 588
 589 %%
 590
 591 start:
 592     stack1 start
 593   | stack2 start
 594   | /* empty */
 595   ;
 596 stack1: 'a' ;
 597 stack2: 'a' ;
 598
 599 %%
 600
 601 static int
 602 yylex (void)
 603 {
 604   yylval.count = (int *) malloc (sizeof (int));
 605   if (!yylval.count)
 606     {
 607       fprintf (stderr, "Test inconclusive.\n");
 608       exit (EXIT_FAILURE);
 609     }
 610   *yylval.count = 0;
 611   return 'a';
 612 }
 613
 614 static void
 615 yyerror (char const *msg)
 616 {
 617   fprintf (stderr, "%s\n", msg);
 618 }
 619
 620 int
 621 main (void)
 622 {
 623   return yyparse ();
 624 }
 625 ]])
 626
 627 AT_CHECK([[bison -o glr-regr7.c glr-regr7.y]], 0, [],
 628 [glr-regr7.y: conflicts: 2 reduce/reduce
 629 ])
 630 AT_COMPILE([glr-regr7])
 631
 632 AT_CHECK([[./glr-regr7]], 2, [],
 633 [memory exhausted
 634 ])
 635
 636 AT_XFAIL_IF(:)
 637
 638 AT_CLEANUP