• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Checking GLR Parsing.                         -*- Autotest -*-
2
3# Copyright (C) 2002-2012 Free Software Foundation, Inc.
4
5# This program is free software: you can redistribute it and/or modify
6# it under the terms of the GNU General Public License as published by
7# the Free Software Foundation, either version 3 of the License, or
8# (at your option) any later version.
9#
10# This program is distributed in the hope that it will be useful,
11# but WITHOUT ANY WARRANTY; without even the implied warranty of
12# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13# GNU General Public License for more details.
14#
15# You should have received a copy of the GNU General Public License
16# along with this program.  If not, see <http://www.gnu.org/licenses/>.
17
18AT_BANNER([[C++ Type Syntax (GLR).]])
19
20# _AT_TEST_GLR_CXXTYPES(DECL, RESOLVE1, RESOLVE2)
21# -----------------------------------------------
22# Store into types.y the calc program, with DECL inserted as a declaration,
23# and with RESOLVE1 and RESOLVE2 as annotations on the conflicted rule for
24# stmt.  Then compile the result.
25m4_define([_AT_TEST_GLR_CXXTYPES],
26[AT_BISON_OPTION_PUSHDEFS([%glr-parser $1])
27
28AT_DATA_GRAMMAR([types.y],
29[[/* Simplified C++ Type and Expression Grammar.  */
30
31$1
32
33%code requires
34{
35  #include <stdio.h>
36  union Node {
37    struct {
38      int isNterm;
39      int parents;
40    } nodeInfo;
41    struct {
42      int isNterm; /* 1 */
43      int parents;
44      char const *form;
45      union Node *children[3];
46    } nterm;
47    struct {
48      int isNterm; /* 0 */
49      int parents;
50      char *text;
51    } term;
52  };
53  typedef union Node Node;
54  #define YYSTYPE Node *
55}
56
57%code
58{
59  static Node *new_nterm (char const *, Node *, Node *, Node *);
60  static Node *new_term (char *);
61  static void free_node (Node *);
62  static char *node_to_string (Node *);
63]m4_bmatch([$2], [stmtMerge],
64[ static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);])[
65  #define YYINITDEPTH 10
66  #define YYSTACKEXPANDABLE 1
67  ]AT_YYERROR_DECLARE[
68  ]AT_YYLEX_DECLARE[
69}
70
71%token TYPENAME ID
72
73%right '='
74%left '+'
75
76%glr-parser
77
78%destructor { free_node ($$); } stmt expr decl declarator TYPENAME ID
79
80%%
81
82prog :
83     | prog stmt   {
84                        char *output;]AT_LOCATION_IF([
85                        printf ("%d.%d-%d.%d: ",
86                             @2.first_line, @2.first_column,
87                             @2.last_line, @2.last_column);])[
88                        output = node_to_string (]$[2);
89                        printf ("%s\n", output);
90                        free (output);
91                        free_node (]$[2);
92                   }
93     ;
94
95stmt : expr ';'  $2     { $$ = ]$[1; }
96     | decl      $3
97     | error ';'        { $$ = new_nterm ("<error>", YY_NULL, YY_NULL, YY_NULL); }
98     | '@'              { YYACCEPT; }
99     ;
100
101expr : ID
102     | TYPENAME '(' expr ')'
103                        { $$ = new_nterm ("<cast>(%s,%s)", ]$[3, ]$[1, YY_NULL); }
104     | expr '+' expr    { $$ = new_nterm ("+(%s,%s)", ]$[1, ]$[3, YY_NULL); }
105     | expr '=' expr    { $$ = new_nterm ("=(%s,%s)", ]$[1, ]$[3, YY_NULL); }
106     ;
107
108decl : TYPENAME declarator ';'
109                        { $$ = new_nterm ("<declare>(%s,%s)", ]$[1, ]$[2, YY_NULL); }
110     | TYPENAME declarator '=' expr ';'
111                        { $$ = new_nterm ("<init-declare>(%s,%s,%s)", ]$[1,
112                                          ]$[2, ]$[4); }
113     ;
114
115declarator : ID
116     | '(' declarator ')' { $$ = ]$[2; }
117     ;
118
119%%
120
121#include <ctype.h>
122#include <stdlib.h>
123#include <string.h>
124#include <stdarg.h>
125#include <assert.h>
126
127int
128main (int argc, char **argv)
129{
130  assert (argc == 2);
131  if (!freopen (argv[1], "r", stdin))
132    return 3;
133  return yyparse ();
134}
135
136]AT_YYERROR_DEFINE[
137
138]AT_YYLEX_PROTOTYPE[
139{
140  char buffer[256];
141  int c;
142  unsigned int i;
143  static int lineNum = 1;
144  static int colNum = 0;
145
146#if YYPURE
147# undef yylloc
148# define yylloc (*llocp)
149# undef yylval
150# define yylval (*lvalp)
151#endif
152
153  while (1)
154    {
155      assert (!feof (stdin));
156      c = getchar ();
157      switch (c)
158        {
159        case EOF:
160          return 0;
161        case '\t':
162          colNum = (colNum + 7) & ~7;
163          break;
164        case ' ': case '\f':
165          colNum += 1;
166          break;
167        case '\n':
168          lineNum += 1;
169          colNum = 0;
170          break;
171        default:
172          {
173            int tok;]AT_LOCATION_IF([[
174            yylloc.first_line = yylloc.last_line = lineNum;
175            yylloc.first_column = colNum;]])[
176            if (isalpha (c))
177              {
178                i = 0;
179
180                do
181                  {
182                    buffer[i++] = c;
183                    colNum += 1;
184                    assert (i != sizeof buffer - 1);
185                    c = getchar ();
186                  }
187                while (isalnum (c) || c == '_');
188
189                ungetc (c, stdin);
190                buffer[i++] = 0;
191                tok = isupper ((unsigned char) buffer[0]) ? TYPENAME : ID;
192                yylval = new_term (strcpy ((char *) malloc (i), buffer));
193              }
194            else
195              {
196                colNum += 1;
197                tok = c;
198                yylval = YY_NULL;
199              }]AT_LOCATION_IF([[
200            yylloc.last_column = colNum-1;]])[
201            return tok;
202          }
203        }
204    }
205}
206
207static Node *
208new_nterm (char const *form, Node *child0, Node *child1, Node *child2)
209{
210  Node *node = (Node *) malloc (sizeof (Node));
211  node->nterm.isNterm = 1;
212  node->nterm.parents = 0;
213  node->nterm.form = form;
214  node->nterm.children[0] = child0;
215  if (child0)
216    child0->nodeInfo.parents += 1;
217  node->nterm.children[1] = child1;
218  if (child1)
219    child1->nodeInfo.parents += 1;
220  node->nterm.children[2] = child2;
221  if (child2)
222    child2->nodeInfo.parents += 1;
223  return node;
224}
225
226static Node *
227new_term (char *text)
228{
229  Node *node = (Node *) malloc (sizeof (Node));
230  node->term.isNterm = 0;
231  node->term.parents = 0;
232  node->term.text = text;
233  return node;
234}
235
236static void
237free_node (Node *node)
238{
239  if (!node)
240    return;
241  node->nodeInfo.parents -= 1;
242  /* Free only if 0 (last parent) or -1 (no parents).  */
243  if (node->nodeInfo.parents > 0)
244    return;
245  if (node->nodeInfo.isNterm == 1)
246    {
247      free_node (node->nterm.children[0]);
248      free_node (node->nterm.children[1]);
249      free_node (node->nterm.children[2]);
250    }
251  else
252    free (node->term.text);
253  free (node);
254}
255
256static char *
257node_to_string (Node *node)
258{
259  char *child0;
260  char *child1;
261  char *child2;
262  char *buffer;
263  if (!node)
264    {
265      buffer = (char *) malloc (1);
266      buffer[0] = 0;
267    }
268  else if (node->nodeInfo.isNterm == 1)
269    {
270      child0 = node_to_string (node->nterm.children[0]);
271      child1 = node_to_string (node->nterm.children[1]);
272      child2 = node_to_string (node->nterm.children[2]);
273      buffer = (char *) malloc (strlen (node->nterm.form) + strlen (child0)
274                                + strlen (child1) + strlen (child2) + 1);
275      sprintf (buffer, node->nterm.form, child0, child1, child2);
276      free (child0);
277      free (child1);
278      free (child2);
279    }
280  else
281    buffer = strdup (node->term.text);
282  return buffer;
283}
284
285]]
286m4_bmatch([$2], [stmtMerge],
287[[static YYSTYPE
288stmtMerge (YYSTYPE x0, YYSTYPE x1)
289{
290  return new_nterm ("<OR>(%s,%s)", x0, x1, YY_NULL);
291}
292]])
293)
294
295AT_DATA([test-input],
296[[
297
298z + q;
299
300T x;
301
302T x = y;
303
304x = y;
305
306T (x) + y;
307
308T (x);
309
310T (y) = z + q;
311
312T (y y) = z + q;
313
314z + q;
315
316@
317
318This is total garbage, but it should be ignored.
319]])
320
321AT_BISON_CHECK([-o types.c types.y], 0, [], ignore)
322AT_COMPILE([types])
323AT_BISON_OPTION_POPDEFS
324])
325
326m4_define([_AT_RESOLVED_GLR_OUTPUT],
327[[+(z,q)
328<declare>(T,x)
329<init-declare>(T,x,y)
330=(x,y)
331+(<cast>(x,T),y)
332<declare>(T,x)
333<init-declare>(T,y,+(z,q))
334<error>
335+(z,q)
336]])
337
338m4_define([_AT_RESOLVED_GLR_OUTPUT_WITH_LOC],
339[[3.0-3.5: +(z,q)
3405.0-5.3: <declare>(T,x)
3417.0-7.7: <init-declare>(T,x,y)
3429.0-9.5: =(x,y)
34311.0-11.9: +(<cast>(x,T),y)
34413.0-13.5: <declare>(T,x)
34515.0-15.13: <init-declare>(T,y,+(z,q))
34617.0-17.15: <error>
34719.0-19.5: +(z,q)
348]])
349
350m4_define([_AT_AMBIG_GLR_OUTPUT],
351[[+(z,q)
352<declare>(T,x)
353<init-declare>(T,x,y)
354=(x,y)
355+(<cast>(x,T),y)
356<OR>(<declare>(T,x),<cast>(x,T))
357<OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
358<error>
359+(z,q)
360]])
361
362m4_define([_AT_AMBIG_GLR_OUTPUT_WITH_LOC],
363[[3.0-3.5: +(z,q)
3645.0-5.3: <declare>(T,x)
3657.0-7.7: <init-declare>(T,x,y)
3669.0-9.5: =(x,y)
36711.0-11.9: +(<cast>(x,T),y)
36813.0-13.5: <OR>(<declare>(T,x),<cast>(x,T))
36915.0-15.13: <OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
37017.0-17.15: <error>
37119.0-19.5: +(z,q)
372]])
373
374m4_define([_AT_GLR_STDERR],
375[[syntax error
376]])
377
378m4_define([_AT_GLR_STDERR_WITH_LOC],
379[[17.5: syntax error
380]])
381
382m4_define([_AT_VERBOSE_GLR_STDERR],
383[[syntax error, unexpected ID, expecting '=' or '+' or ')'
384]])
385
386m4_define([_AT_VERBOSE_GLR_STDERR_WITH_LOC],
387[[17.5: syntax error, unexpected ID, expecting '=' or '+' or ')'
388]])
389
390## ---------------------------------------------------- ##
391## Compile the grammar described in the documentation.  ##
392## ---------------------------------------------------- ##
393
394AT_SETUP([GLR: Resolve ambiguity, impure, no locations])
395_AT_TEST_GLR_CXXTYPES([],
396                      [%dprec 1], [%dprec 2])
397AT_PARSER_CHECK([[./types test-input]], 0,
398                [_AT_RESOLVED_GLR_OUTPUT], [_AT_GLR_STDERR])
399AT_CLEANUP
400
401AT_SETUP([GLR: Resolve ambiguity, impure, locations])
402_AT_TEST_GLR_CXXTYPES([%locations],[%dprec 1],[%dprec 2])
403AT_PARSER_CHECK([[./types test-input]], 0,
404                [_AT_RESOLVED_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
405AT_CLEANUP
406
407AT_SETUP([GLR: Resolve ambiguity, pure, no locations])
408_AT_TEST_GLR_CXXTYPES([%define api.pure],
409                      [%dprec 1], [%dprec 2])
410AT_PARSER_CHECK([[./types test-input]], 0,
411                [_AT_RESOLVED_GLR_OUTPUT], [_AT_GLR_STDERR])
412AT_CLEANUP
413
414AT_SETUP([GLR: Resolve ambiguity, pure, locations])
415_AT_TEST_GLR_CXXTYPES([%define api.pure %locations],
416                      [%dprec 1], [%dprec 2])
417AT_PARSER_CHECK([[./types test-input]], 0,
418                [_AT_RESOLVED_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
419AT_CLEANUP
420
421AT_SETUP([GLR: Merge conflicting parses, impure, no locations])
422_AT_TEST_GLR_CXXTYPES([],
423                      [%merge <stmtMerge>], [%merge <stmtMerge>])
424AT_PARSER_CHECK([[./types test-input]], 0,
425                [_AT_AMBIG_GLR_OUTPUT], [_AT_GLR_STDERR])
426AT_CLEANUP
427
428AT_SETUP([GLR: Merge conflicting parses, impure, locations])
429_AT_TEST_GLR_CXXTYPES([%locations],
430                      [%merge <stmtMerge>], [%merge <stmtMerge>])
431AT_PARSER_CHECK([[./types test-input]], 0,
432                [_AT_AMBIG_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
433AT_CLEANUP
434
435AT_SETUP([GLR: Merge conflicting parses, pure, no locations])
436_AT_TEST_GLR_CXXTYPES([%define api.pure],
437                      [%merge <stmtMerge>], [%merge <stmtMerge>])
438AT_PARSER_CHECK([[./types test-input]], 0,
439                [_AT_AMBIG_GLR_OUTPUT], [_AT_GLR_STDERR])
440AT_CLEANUP
441AT_SETUP([GLR: Merge conflicting parses, pure, locations])
442_AT_TEST_GLR_CXXTYPES([%define api.pure %locations],
443                      [%merge <stmtMerge>],[%merge <stmtMerge>])
444AT_PARSER_CHECK([[./types test-input]], 0,
445                [_AT_AMBIG_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
446AT_CLEANUP
447
448AT_SETUP([GLR: Verbose messages, resolve ambiguity, impure, no locations])
449_AT_TEST_GLR_CXXTYPES([%error-verbose],
450                      [%merge <stmtMerge>], [%merge <stmtMerge>])
451AT_PARSER_CHECK([[./types test-input]], 0,
452                [_AT_AMBIG_GLR_OUTPUT], [_AT_VERBOSE_GLR_STDERR])
453AT_CLEANUP
454