1# Checking GLR Parsing.                         -*- Autotest -*-
2# Copyright (C) 2002, 2003, 2004, 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
19AT_BANNER([[C++ Type Syntax (GLR).]])
20
21# _AT_TEST_GLR_CXXTYPES(DECL, RESOLVE1, RESOLVE2)
22# -----------------------------------------------
23# Store into types.y the calc program, with DECL inserted as a declaration,
24# and with RESOLVE1 and RESOLVE2 as annotations on the conflicted rule for
25# stmt.  Then compile the result.
26m4_define([_AT_TEST_GLR_CXXTYPES],
27[
28AT_BISON_OPTION_PUSHDEFS([$1])
29
30AT_DATA_GRAMMAR([types.y],
31[[/* Simplified C++ Type and Expression Grammar.  */
32
33$1
34
35%{
36  #include <stdio.h>
37  union Node {
38    struct {
39      int isNterm;
40      int parents;
41    } nodeInfo;
42    struct {
43      int isNterm; /* 1 */
44      int parents;
45      char const *form;
46      union Node *children[3];
47    } nterm;
48    struct {
49      int isNterm; /* 0 */
50      int parents;
51      char *text;
52    } term;
53  };
54  typedef union Node Node;
55  static Node *new_nterm (char const *, Node *, Node *, Node *);
56  static Node *new_term (char *);
57  static void free_node (Node *);
58  static char *node_to_string (Node *);
59  #define YYSTYPE Node *
60]m4_bmatch([$2], [stmtMerge],
61[ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);])[
62  #define YYINITDEPTH 10
63  #define YYSTACKEXPANDABLE 1
64  struct YYLTYPE;
65#if YYPURE
66# if YYLSP_NEEDED
67#  define LEX_PARAMETERS YYSTYPE *lvalp, struct YYLTYPE *llocp
68#  define ERROR_PARAMETERS struct YYLTYPE *llocp, char const *s
69# else
70#  define LEX_PARAMETERS YYSTYPE *lvalp
71# endif
72#endif
73#ifndef LEX_PARAMETERS
74# define LEX_PARAMETERS void
75#endif
76#ifndef ERROR_PARAMETERS
77# define ERROR_PARAMETERS char const *s
78#endif
79  int yylex (LEX_PARAMETERS);
80  void yyerror (ERROR_PARAMETERS);
81%}
82
83%token TYPENAME ID
84
85%right '='
86%left '+'
87
88%glr-parser
89
90%destructor { free_node ($$); } stmt expr decl declarator TYPENAME ID
91
92%%
93
94prog :
95     | prog stmt   {
96			char *output;]AT_LOCATION_IF([
97			printf ("%d.%d-%d.%d: ",
98			     @2.first_line, @2.first_column,
99			     @2.last_line, @2.last_column);])[
100			output = node_to_string (]$[2);
101			printf ("%s\n", output);
102			free (output);
103			free_node (]$[2);
104		   }
105     ;
106
107stmt : expr ';'  $2	{ $$ = ]$[1; }
108     | decl      $3
109     | error ';'	{ $$ = new_nterm ("<error>", 0, 0, 0); }
110     | '@'		{ YYACCEPT; }
111     ;
112
113expr : ID
114     | TYPENAME '(' expr ')'
115			{ $$ = new_nterm ("<cast>(%s,%s)", ]$[3, ]$[1, 0); }
116     | expr '+' expr	{ $$ = new_nterm ("+(%s,%s)", ]$[1, ]$[3, 0); }
117     | expr '=' expr    { $$ = new_nterm ("=(%s,%s)", ]$[1, ]$[3, 0); }
118     ;
119
120decl : TYPENAME declarator ';'
121			{ $$ = new_nterm ("<declare>(%s,%s)", ]$[1, ]$[2, 0); }
122     | TYPENAME declarator '=' expr ';'
123			{ $$ = new_nterm ("<init-declare>(%s,%s,%s)", ]$[1,
124					  ]$[2, ]$[4); }
125     ;
126
127declarator : ID
128     | '(' declarator ')' { $$ = ]$[2; }
129     ;
130
131%%
132
133#include <ctype.h>
134#include <stdlib.h>
135#include <string.h>
136#include <stdarg.h>
137
138int
139main (int argc, char **argv)
140{
141  if (argc != 2)
142    abort ();
143  if (!freopen (argv[1], "r", stdin))
144    return 3;
145  return yyparse ();
146}
147
148int
149yylex (LEX_PARAMETERS)
150{
151  char buffer[256];
152  int c;
153  unsigned int i;
154  static int lineNum = 1;
155  static int colNum = 0;
156
157#if YYPURE
158# undef yylloc
159# define yylloc (*llocp)
160# undef yylval
161# define yylval (*lvalp)
162#endif
163
164  while (1)
165    {
166      c = getchar ();
167      switch (c)
168	{
169	case EOF:
170	  return 0;
171	case '\t':
172	  colNum = (colNum + 7) & ~7;
173	  break;
174	case ' ': case '\f':
175	  colNum += 1;
176	  break;
177	case '\n':
178	  lineNum += 1;
179	  colNum = 0;
180	  break;
181	default:
182	  {
183	    int tok;
184#if YYLSP_NEEDED
185	    yylloc.first_line = yylloc.last_line = lineNum;
186	    yylloc.first_column = colNum;
187#endif
188	    if (isalpha (c))
189	      {
190		i = 0;
191
192		do
193		  {
194		    buffer[i++] = c;
195		    colNum += 1;
196		    if (i == sizeof buffer - 1)
197		      abort ();
198		    c = getchar ();
199		  }
200		while (isalnum (c) || c == '_');
201
202		ungetc (c, stdin);
203		buffer[i++] = 0;
204		tok = isupper ((unsigned char) buffer[0]) ? TYPENAME : ID;
205		yylval = new_term (strcpy ((char *) malloc (i), buffer));
206	      }
207	    else
208	      {
209		colNum += 1;
210		tok = c;
211		yylval = 0;
212	      }
213#if YYLSP_NEEDED
214	    yylloc.last_column = colNum-1;
215#endif
216	    return tok;
217	  }
218	}
219    }
220}
221
222void
223yyerror (ERROR_PARAMETERS)
224{
225#if YYPURE && YYLSP_NEEDED
226  /* Pacify GCC by using llocp.  */
227  if (! llocp)
228    abort ();
229#endif
230  fprintf (stderr, "%s\n", s);
231}
232
233static Node *
234new_nterm (char const *form, Node *child0, Node *child1, Node *child2)
235{
236  Node *node = (Node *) malloc (sizeof (Node));
237  node->nterm.isNterm = 1;
238  node->nterm.parents = 0;
239  node->nterm.form = form;
240  node->nterm.children[0] = child0;
241  if (child0)
242    child0->nodeInfo.parents += 1;
243  node->nterm.children[1] = child1;
244  if (child1)
245    child1->nodeInfo.parents += 1;
246  node->nterm.children[2] = child2;
247  if (child2)
248    child2->nodeInfo.parents += 1;
249  return node;
250}
251
252static Node *
253new_term (char *text)
254{
255  Node *node = (Node *) malloc (sizeof (Node));
256  node->term.isNterm = 0;
257  node->term.parents = 0;
258  node->term.text = text;
259  return node;
260}
261
262static void
263free_node (Node *node)
264{
265  if (!node)
266    return;
267  node->nodeInfo.parents -= 1;
268  /* Free only if 0 (last parent) or -1 (no parents).  */
269  if (node->nodeInfo.parents > 0)
270    return;
271  if (node->nodeInfo.isNterm == 1)
272    {
273      free_node (node->nterm.children[0]);
274      free_node (node->nterm.children[1]);
275      free_node (node->nterm.children[2]);
276    }
277  else
278    free (node->term.text);
279  free (node);
280}
281
282static char *
283node_to_string (Node *node)
284{
285  char *child0;
286  char *child1;
287  char *child2;
288  char *buffer;
289  if (!node)
290    {
291      buffer = (char *) malloc (1);
292      buffer[0] = 0;
293    }
294  else if (node->nodeInfo.isNterm == 1)
295    {
296      child0 = node_to_string (node->nterm.children[0]);
297      child1 = node_to_string (node->nterm.children[1]);
298      child2 = node_to_string (node->nterm.children[2]);
299      buffer = (char *) malloc (strlen (node->nterm.form) + strlen (child0)
300				+ strlen (child1) + strlen (child2) + 1);
301      sprintf (buffer, node->nterm.form, child0, child1, child2);
302      free (child0);
303      free (child1);
304      free (child2);
305    }
306  else
307    buffer = strdup (node->term.text);
308  return buffer;
309}
310
311]]
312m4_bmatch([$2], [stmtMerge],
313[[static YYSTYPE
314stmtMerge (YYSTYPE x0, YYSTYPE x1)
315{
316  return new_nterm ("<OR>(%s,%s)", x0, x1, 0);
317}
318]])
319)
320
321AT_DATA([test-input],
322[[
323
324z + q;
325
326T x;
327
328T x = y;
329
330x = y;
331
332T (x) + y;
333
334T (x);
335
336T (y) = z + q;
337
338T (y y) = z + q;
339
340z + q;
341
342@
343
344This is total garbage, but it should be ignored.
345]])
346
347AT_CHECK([bison -o types.c types.y], 0, [], ignore)
348AT_COMPILE([types])
349AT_BISON_OPTION_POPDEFS
350])
351
352m4_define([_AT_RESOLVED_GLR_OUTPUT],
353[[+(z,q)
354<declare>(T,x)
355<init-declare>(T,x,y)
356=(x,y)
357+(<cast>(x,T),y)
358<declare>(T,x)
359<init-declare>(T,y,+(z,q))
360<error>
361+(z,q)
362]])
363
364m4_define([_AT_RESOLVED_GLR_OUTPUT_WITH_LOC],
365[[3.0-3.5: +(z,q)
3665.0-5.3: <declare>(T,x)
3677.0-7.7: <init-declare>(T,x,y)
3689.0-9.5: =(x,y)
36911.0-11.9: +(<cast>(x,T),y)
37013.0-13.5: <declare>(T,x)
37115.0-15.13: <init-declare>(T,y,+(z,q))
37217.0-17.15: <error>
37319.0-19.5: +(z,q)
374]])
375
376m4_define([_AT_AMBIG_GLR_OUTPUT],
377[[+(z,q)
378<declare>(T,x)
379<init-declare>(T,x,y)
380=(x,y)
381+(<cast>(x,T),y)
382<OR>(<declare>(T,x),<cast>(x,T))
383<OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
384<error>
385+(z,q)
386]])
387
388m4_define([_AT_AMBIG_GLR_OUTPUT_WITH_LOC],
389[[3.0-3.5: +(z,q)
3905.0-5.3: <declare>(T,x)
3917.0-7.7: <init-declare>(T,x,y)
3929.0-9.5: =(x,y)
39311.0-11.9: +(<cast>(x,T),y)
39413.0-13.5: <OR>(<declare>(T,x),<cast>(x,T))
39515.0-15.13: <OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
39617.0-17.15: <error>
39719.0-19.5: +(z,q)
398]])
399
400m4_define([_AT_GLR_STDERR],
401[[syntax error
402]])
403
404m4_define([_AT_VERBOSE_GLR_STDERR],
405[[syntax error, unexpected ID, expecting '=' or '+' or ')'
406]])
407
408## ---------------------------------------------------- ##
409## Compile the grammar described in the documentation.  ##
410## ---------------------------------------------------- ##
411
412AT_SETUP([GLR: Resolve ambiguity, impure, no locations])
413_AT_TEST_GLR_CXXTYPES([],
414		      [%dprec 1], [%dprec 2])
415AT_PARSER_CHECK([[./types test-input]], 0,
416		_AT_RESOLVED_GLR_OUTPUT, _AT_GLR_STDERR)
417AT_CLEANUP
418
419AT_SETUP([GLR: Resolve ambiguity, impure, locations])
420_AT_TEST_GLR_CXXTYPES([%locations],[%dprec 1],[%dprec 2])
421AT_PARSER_CHECK([[./types test-input]], 0,
422		_AT_RESOLVED_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
423AT_CLEANUP
424
425AT_SETUP([GLR: Resolve ambiguity, pure, no locations])
426_AT_TEST_GLR_CXXTYPES([%pure-parser],
427		      [%dprec 1], [%dprec 2])
428AT_PARSER_CHECK([[./types test-input]], 0,
429		_AT_RESOLVED_GLR_OUTPUT, _AT_GLR_STDERR)
430AT_CLEANUP
431
432AT_SETUP([GLR: Resolve ambiguity, pure, locations])
433_AT_TEST_GLR_CXXTYPES([%pure-parser %locations],
434		      [%dprec 1], [%dprec 2])
435AT_PARSER_CHECK([[./types test-input]], 0,
436		_AT_RESOLVED_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
437AT_CLEANUP
438
439AT_SETUP([GLR: Merge conflicting parses, impure, no locations])
440_AT_TEST_GLR_CXXTYPES([],
441		      [%merge <stmtMerge>], [%merge <stmtMerge>])
442AT_PARSER_CHECK([[./types test-input]], 0,
443		_AT_AMBIG_GLR_OUTPUT, _AT_GLR_STDERR)
444AT_CLEANUP
445
446AT_SETUP([GLR: Merge conflicting parses, impure, locations])
447_AT_TEST_GLR_CXXTYPES([%locations],
448		      [%merge <stmtMerge>], [%merge <stmtMerge>])
449AT_PARSER_CHECK([[./types test-input]], 0,
450		_AT_AMBIG_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
451AT_CLEANUP
452
453AT_SETUP([GLR: Merge conflicting parses, pure, no locations])
454_AT_TEST_GLR_CXXTYPES([%pure-parser],
455		      [%merge <stmtMerge>], [%merge <stmtMerge>])
456AT_PARSER_CHECK([[./types test-input]], 0,
457		_AT_AMBIG_GLR_OUTPUT, _AT_GLR_STDERR)
458AT_CLEANUP
459AT_SETUP([GLR: Merge conflicting parses, pure, locations])
460_AT_TEST_GLR_CXXTYPES([%pure-parser %locations],
461		      [%merge <stmtMerge>],[%merge <stmtMerge>])
462AT_PARSER_CHECK([[./types test-input]], 0,
463		_AT_AMBIG_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
464AT_CLEANUP
465
466AT_SETUP([GLR: Verbose messages, resolve ambiguity, impure, no locations])
467_AT_TEST_GLR_CXXTYPES([%error-verbose],
468		      [%merge <stmtMerge>], [%merge <stmtMerge>])
469AT_PARSER_CHECK([[./types test-input]], 0,
470		_AT_AMBIG_GLR_OUTPUT, _AT_VERBOSE_GLR_STDERR)
471AT_CLEANUP
472