]> git.saurik.com Git - bison.git/blob - tests/glr-regression.at
* src/reader.c, src/symlist.h, src/symlist.c: s/mid_rule/midrule/.
[bison.git] / 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 *
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 ##
334 ## Thanks to Joel E. Denny for this test; see ##
335 ## <http://lists.gnu.org/archive/html/help-bison/2005-07/msg00013.html>. ##
336 ## ---------------------------------------------------------------------- ##
337
338 AT_SETUP([Duplicate representation of merged trees])
339
340 AT_DATA_GRAMMAR([glr-regr4.y],
341 [[
342 %union { char *ptr; }
343 %type <ptr> S A A1 A2 B
344 %glr-parser
345
346 %{
347 #include <stdio.h>
348 #include <stdlib.h>
349 #include <string.h>
350 static char *merge (YYSTYPE, YYSTYPE);
351 static char *make_value (char const *, char const *);
352 static void yyerror (char const *);
353 static int yylex (void);
354 %}
355
356 %%
357
358 tree: S { printf ("%s\n", $1); } ;
359
360 S:
361 A %merge<merge> { $$ = make_value ("S", $1); }
362 | B %merge<merge> { $$ = make_value ("S", $1); }
363 ;
364
365 A:
366 A1 %merge<merge> { $$ = make_value ("A", $1); }
367 | A2 %merge<merge> { $$ = make_value ("A", $1); }
368 ;
369
370 A1: 'a' { $$ = make_value ("A1", "'a'"); } ;
371 A2: 'a' { $$ = make_value ("A2", "'a'"); } ;
372 B: 'a' { $$ = make_value ("B", "'a'"); } ;
373
374 %%
375
376 static int
377 yylex (void)
378 {
379 static char const *input = "a";
380 return *input++;
381 }
382
383 int
384 main (void)
385 {
386 return yyparse ();
387 }
388
389 static char *
390 make_value (char const *parent, char const *child)
391 {
392 char const format[] = "%s <- %s";
393 char *value =
394 (char *) malloc (strlen (parent) + strlen (child) + sizeof format);
395 sprintf (value, format, parent, child);
396 return value;
397 }
398
399 static char *
400 merge (YYSTYPE s1, YYSTYPE s2)
401 {
402 char const format[] = "merge{ %s and %s }";
403 char *value =
404 (char *) malloc (strlen (s1.ptr) + strlen (s2.ptr) + sizeof format);
405 sprintf (value, format, s1.ptr, s2.ptr);
406 return value;
407 }
408
409 static void
410 yyerror (char const *msg)
411 {
412 fprintf (stderr, "%s\n", msg);
413 }
414 ]])
415
416 AT_CHECK([[bison -o glr-regr4.c glr-regr4.y]], 0, [],
417 [glr-regr4.y: conflicts: 1 reduce/reduce
418 ])
419 AT_COMPILE([glr-regr4])
420
421 AT_CHECK([[./glr-regr4]], 0,
422 [[merge{ S <- merge{ A <- A1 <- 'a' and A <- A2 <- 'a' } and S <- B <- 'a' }
423 ]], [])
424
425 AT_CLEANUP
426
427
428 ## ------------------------------------------------------------------------- ##
429 ## User destructor for unresolved GLR semantic value ##
430 ## Thanks to Joel E. Denny for this test; see ##
431 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00016.html>. ##
432 ## ------------------------------------------------------------------------- ##
433
434 AT_SETUP([User destructor for unresolved GLR semantic value])
435
436 AT_DATA_GRAMMAR([glr-regr5.y],
437 [[
438 %{
439 #include <stdio.h>
440 #include <stdlib.h>
441 static void yyerror (char const *);
442 static int yylex (void);
443 enum { MAGIC_VALUE = -1057808125 }; /* originally chosen at random */
444 %}
445
446 %glr-parser
447 %union { int value; }
448 %type <value> start
449
450 %destructor {
451 if ($$ != MAGIC_VALUE)
452 {
453 fprintf (stderr, "Bad destructor call.\n");
454 exit (EXIT_FAILURE);
455 }
456 } start
457
458 %%
459
460 start:
461 'a' { $$ = MAGIC_VALUE; }
462 | 'a' { $$ = MAGIC_VALUE; }
463 ;
464
465 %%
466
467 static int
468 yylex (void)
469 {
470 static char const *input = "a";
471 return *input++;
472 }
473
474 static void
475 yyerror (char const *msg)
476 {
477 fprintf (stderr, "%s\n", msg);
478 }
479
480 int
481 main (void)
482 {
483 return yyparse () != 1;
484 }
485 ]])
486
487 AT_CHECK([[bison -o glr-regr5.c glr-regr5.y]], 0, [],
488 [glr-regr5.y: conflicts: 1 reduce/reduce
489 ])
490 AT_COMPILE([glr-regr5])
491
492 AT_CHECK([[./glr-regr5]], 0, [],
493 [syntax is ambiguous
494 ])
495
496 AT_CLEANUP
497
498
499 ## ------------------------------------------------------------------------- ##
500 ## User destructor after an error during a split parse ##
501 ## Thanks to Joel E. Denny for this test; see ##
502 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00029.html>. ##
503 ## ------------------------------------------------------------------------- ##
504
505 AT_SETUP([User destructor after an error during a split parse])
506
507 AT_DATA_GRAMMAR([glr-regr6.y],
508 [[
509 %{
510 #include <stdio.h>
511 #include <stdlib.h>
512 static void yyerror (char const *);
513 static int yylex (void);
514 %}
515
516 %glr-parser
517 %union { int value; }
518 %type <value> 'a'
519
520 %destructor {
521 printf ("Destructor called.\n");
522 } 'a'
523
524 %%
525
526 start: 'a' | 'a' ;
527
528 %%
529
530 static int
531 yylex (void)
532 {
533 static char const *input = "a";
534 return *input++;
535 }
536
537 static void
538 yyerror (char const *msg)
539 {
540 fprintf (stderr, "%s\n", msg);
541 }
542
543 int
544 main (void)
545 {
546 return yyparse () != 1;
547 }
548 ]])
549
550 AT_CHECK([[bison -o glr-regr6.c glr-regr6.y]], 0, [],
551 [glr-regr6.y: conflicts: 1 reduce/reduce
552 ])
553 AT_COMPILE([glr-regr6])
554
555 AT_CHECK([[./glr-regr6]], 0,
556 [Destructor called.
557 ],
558 [syntax is ambiguous
559 ])
560
561 AT_CLEANUP
562
563
564 ## ------------------------------------------------------------------------- ##
565 ## Duplicated user destructor for lookahead ##
566 ## Thanks to Joel E. Denny for this test; see ##
567 ## <http://lists.gnu.org/archive/html/bison-patches/2005-08/msg00035.html>. ##
568 ## ------------------------------------------------------------------------- ##
569
570 AT_SETUP([Duplicated user destructor for lookahead])
571
572 AT_DATA_GRAMMAR([glr-regr7.y],
573 [[
574 %{
575 #include <stdio.h>
576 #include <stdlib.h>
577 static void yyerror (char const *);
578 static int yylex (void);
579 #define YYSTACKEXPANDABLE 0
580 %}
581
582 %glr-parser
583 %union { int *count; }
584 %type <count> 'a'
585
586 %destructor {
587 if ((*$$)++)
588 fprintf (stderr, "Destructor called on same value twice.\n");
589 } 'a'
590
591 %%
592
593 start:
594 stack1 start
595 | stack2 start
596 | /* empty */
597 ;
598 stack1: 'a' ;
599 stack2: 'a' ;
600
601 %%
602
603 static int
604 yylex (void)
605 {
606 yylval.count = (int *) malloc (sizeof (int));
607 if (!yylval.count)
608 {
609 fprintf (stderr, "Test inconclusive.\n");
610 exit (EXIT_FAILURE);
611 }
612 *yylval.count = 0;
613 return 'a';
614 }
615
616 static void
617 yyerror (char const *msg)
618 {
619 fprintf (stderr, "%s\n", msg);
620 }
621
622 int
623 main (void)
624 {
625 return yyparse ();
626 }
627 ]])
628
629 AT_CHECK([[bison -o glr-regr7.c glr-regr7.y]], 0, [],
630 [glr-regr7.y: conflicts: 2 reduce/reduce
631 ])
632 AT_COMPILE([glr-regr7])
633
634 AT_CHECK([[./glr-regr7]], 2, [],
635 [memory exhausted
636 ])
637
638 AT_CLEANUP
639
640
641 ## ------------------------------------------------------------------------- ##
642 ## Incorrect default location for empty right-hand sides. Adapted from bug ##
643 ## report by Claudia Hermann. ##
644 ## See http://lists.gnu.org/archive/html/bug-bison/2005-10/msg00069.html and ##
645 ## http://lists.gnu.org/archive/html/bug-bison/2005-10/msg00072.html ##
646 ## ------------------------------------------------------------------------- ##
647
648 AT_SETUP([Incorrectly initialized location for empty right-hand side in GLR])
649
650 AT_DATA_GRAMMAR([glr-regr8.y],
651 [[
652 %{
653 #include <stdio.h>
654 #include <stdlib.h>
655 static void yyerror (char const *);
656 static int yylex (void);
657 static void yyerror(const char *msg);
658 %}
659
660 %token T_CONSTANT
661 %token T_PORT
662 %token T_SIGNAL
663
664 %glr-parser
665
666 %%
667
668
669 PortClause : T_PORT InterfaceDeclaration T_PORT
670 { printf("%d/%d - %d/%d - %d/%d\n",
671 @1.first_column, @1.last_column,
672 @2.first_column, @2.last_column,
673 @3.first_column, @3.last_column); }
674 ;
675
676 InterfaceDeclaration : OptConstantWord %dprec 1
677 | OptSignalWord %dprec 2
678 ;
679
680 OptConstantWord : /* empty */
681 | T_CONSTANT
682 ;
683
684 OptSignalWord : /* empty */
685 { printf("empty: %d/%d\n", @$.first_column, @$.last_column); }
686 | T_SIGNAL
687 ;
688
689 %%
690
691 void yyerror(const char *msg)
692 {
693 fprintf (stderr, "error\n");
694 }
695
696 static int lexIndex;
697
698 int yylex (void)
699 {
700 lexIndex += 1;
701 switch (lexIndex)
702 {
703 case 1:
704 yylloc.first_column = 1;
705 yylloc.last_column = 9;
706 return T_PORT;
707 case 2:
708 yylloc.first_column = 13;
709 yylloc.last_column = 17;
710 return T_PORT;
711 default:
712 return 0;
713 }
714 }
715
716 int
717 main (void)
718 {
719 yyparse();
720 return 0;
721 }
722 ]])
723
724 AT_CHECK([[bison -o glr-regr8.c glr-regr8.y]], 0, [],
725 [glr-regr8.y: conflicts: 1 reduce/reduce
726 ])
727 AT_COMPILE([glr-regr8])
728
729 AT_CHECK([[./glr-regr8]], 0,
730 [empty: 9/9
731 1/9 - 9/9 - 13/17
732 ],
733 [])
734
735 AT_CLEANUP
736
737
738 ## ------------------------------------------------------------------------- ##
739 ## No users destructors if stack 0 deleted ##
740 ## Thanks to Joel E. Denny for this test; see ##
741 ## <http://lists.gnu.org/archive/html/bison-patches/2005-09/msg00109.html>. ##
742 ## ------------------------------------------------------------------------- ##
743
744 AT_SETUP([No users destructors if stack 0 deleted])
745
746 AT_DATA_GRAMMAR([glr-regr9.y],
747 [[
748 %{
749 # include <stdio.h>
750 # include <stdlib.h>
751 static void yyerror (char const *);
752 static int yylex (void);
753 # define YYSTACKEXPANDABLE 0
754 static int tokens = 0;
755 static int destructors = 0;
756 # define USE(Var)
757 %}
758
759 %glr-parser
760 %union { int dummy; }
761 %type <dummy> 'a'
762
763 %destructor {
764 destructors += 1;
765 } 'a'
766
767 %%
768
769 start:
770 ambig0 'a' { destructors += 2; USE ($2); }
771 | ambig1 start { destructors += 1; }
772 | ambig2 start { destructors += 1; }
773 ;
774
775 ambig0: 'a' ;
776 ambig1: 'a' ;
777 ambig2: 'a' ;
778
779 %%
780
781 static int
782 yylex (void)
783 {
784 tokens += 1;
785 return 'a';
786 }
787
788 static void
789 yyerror (char const *msg)
790 {
791 fprintf (stderr, "%s\n", msg);
792 }
793
794 int
795 main (void)
796 {
797 int exit_status;
798 exit_status = yyparse ();
799 if (tokens != destructors)
800 {
801 fprintf (stderr, "Tokens = %d, Destructors = %d\n", tokens, destructors);
802 return 1;
803 }
804 return !exit_status;
805 }
806 ]])
807
808 AT_CHECK([[bison -o glr-regr9.c glr-regr9.y]], 0, [],
809 [glr-regr9.y: conflicts: 1 reduce/reduce
810 ])
811 AT_COMPILE([glr-regr9])
812
813 AT_CHECK([[./glr-regr9]], 0, [],
814 [memory exhausted
815 ])
816
817 AT_CLEANUP