Home | History | Annotate | Download | only in tests 
      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 
     19 AT_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.
     26 m4_define([_AT_TEST_GLR_CXXTYPES],
     27 [
     28 AT_BISON_OPTION_PUSHDEFS([$1])
     29 
     30 AT_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 
     94 prog :
     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 
    107 stmt : expr ';'  $2	{ $$ = ]$[1; }
    108      | decl      $3
    109      | error ';'	{ $$ = new_nterm ("<error>", 0, 0, 0); }
    110      | '@'		{ YYACCEPT; }
    111      ;
    112 
    113 expr : 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 
    120 decl : 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 
    127 declarator : 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 
    138 int
    139 main (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 
    148 int
    149 yylex (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 
    222 void
    223 yyerror (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 
    233 static Node *
    234 new_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 
    252 static Node *
    253 new_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 
    262 static void
    263 free_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 
    282 static char *
    283 node_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 ]]
    312 m4_bmatch([$2], [stmtMerge],
    313 [[static YYSTYPE
    314 stmtMerge (YYSTYPE x0, YYSTYPE x1)
    315 {
    316   return new_nterm ("<OR>(%s,%s)", x0, x1, 0);
    317 }
    318 ]])
    319 )
    320 
    321 AT_DATA([test-input],
    322 [[
    323 
    324 z + q;
    325 
    326 T x;
    327 
    328 T x = y;
    329 
    330 x = y;
    331 
    332 T (x) + y;
    333 
    334 T (x);
    335 
    336 T (y) = z + q;
    337 
    338 T (y y) = z + q;
    339 
    340 z + q;
    341 
    342 @
    343 
    344 This is total garbage, but it should be ignored.
    345 ]])
    346 
    347 AT_CHECK([bison -o types.c types.y], 0, [], ignore)
    348 AT_COMPILE([types])
    349 AT_BISON_OPTION_POPDEFS
    350 ])
    351 
    352 m4_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 
    364 m4_define([_AT_RESOLVED_GLR_OUTPUT_WITH_LOC],
    365 [[3.0-3.5: +(z,q)
    366 5.0-5.3: <declare>(T,x)
    367 7.0-7.7: <init-declare>(T,x,y)
    368 9.0-9.5: =(x,y)
    369 11.0-11.9: +(<cast>(x,T),y)
    370 13.0-13.5: <declare>(T,x)
    371 15.0-15.13: <init-declare>(T,y,+(z,q))
    372 17.0-17.15: <error>
    373 19.0-19.5: +(z,q)
    374 ]])
    375 
    376 m4_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 
    388 m4_define([_AT_AMBIG_GLR_OUTPUT_WITH_LOC],
    389 [[3.0-3.5: +(z,q)
    390 5.0-5.3: <declare>(T,x)
    391 7.0-7.7: <init-declare>(T,x,y)
    392 9.0-9.5: =(x,y)
    393 11.0-11.9: +(<cast>(x,T),y)
    394 13.0-13.5: <OR>(<declare>(T,x),<cast>(x,T))
    395 15.0-15.13: <OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
    396 17.0-17.15: <error>
    397 19.0-19.5: +(z,q)
    398 ]])
    399 
    400 m4_define([_AT_GLR_STDERR],
    401 [[syntax error
    402 ]])
    403 
    404 m4_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 
    412 AT_SETUP([GLR: Resolve ambiguity, impure, no locations])
    413 _AT_TEST_GLR_CXXTYPES([],
    414 		      [%dprec 1], [%dprec 2])
    415 AT_PARSER_CHECK([[./types test-input]], 0,
    416 		_AT_RESOLVED_GLR_OUTPUT, _AT_GLR_STDERR)
    417 AT_CLEANUP
    418 
    419 AT_SETUP([GLR: Resolve ambiguity, impure, locations])
    420 _AT_TEST_GLR_CXXTYPES([%locations],[%dprec 1],[%dprec 2])
    421 AT_PARSER_CHECK([[./types test-input]], 0,
    422 		_AT_RESOLVED_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
    423 AT_CLEANUP
    424 
    425 AT_SETUP([GLR: Resolve ambiguity, pure, no locations])
    426 _AT_TEST_GLR_CXXTYPES([%pure-parser],
    427 		      [%dprec 1], [%dprec 2])
    428 AT_PARSER_CHECK([[./types test-input]], 0,
    429 		_AT_RESOLVED_GLR_OUTPUT, _AT_GLR_STDERR)
    430 AT_CLEANUP
    431 
    432 AT_SETUP([GLR: Resolve ambiguity, pure, locations])
    433 _AT_TEST_GLR_CXXTYPES([%pure-parser %locations],
    434 		      [%dprec 1], [%dprec 2])
    435 AT_PARSER_CHECK([[./types test-input]], 0,
    436 		_AT_RESOLVED_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
    437 AT_CLEANUP
    438 
    439 AT_SETUP([GLR: Merge conflicting parses, impure, no locations])
    440 _AT_TEST_GLR_CXXTYPES([],
    441 		      [%merge <stmtMerge>], [%merge <stmtMerge>])
    442 AT_PARSER_CHECK([[./types test-input]], 0,
    443 		_AT_AMBIG_GLR_OUTPUT, _AT_GLR_STDERR)
    444 AT_CLEANUP
    445 
    446 AT_SETUP([GLR: Merge conflicting parses, impure, locations])
    447 _AT_TEST_GLR_CXXTYPES([%locations],
    448 		      [%merge <stmtMerge>], [%merge <stmtMerge>])
    449 AT_PARSER_CHECK([[./types test-input]], 0,
    450 		_AT_AMBIG_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
    451 AT_CLEANUP
    452 
    453 AT_SETUP([GLR: Merge conflicting parses, pure, no locations])
    454 _AT_TEST_GLR_CXXTYPES([%pure-parser],
    455 		      [%merge <stmtMerge>], [%merge <stmtMerge>])
    456 AT_PARSER_CHECK([[./types test-input]], 0,
    457 		_AT_AMBIG_GLR_OUTPUT, _AT_GLR_STDERR)
    458 AT_CLEANUP
    459 AT_SETUP([GLR: Merge conflicting parses, pure, locations])
    460 _AT_TEST_GLR_CXXTYPES([%pure-parser %locations],
    461 		      [%merge <stmtMerge>],[%merge <stmtMerge>])
    462 AT_PARSER_CHECK([[./types test-input]], 0,
    463 		_AT_AMBIG_GLR_OUTPUT_WITH_LOC, _AT_GLR_STDERR)
    464 AT_CLEANUP
    465 
    466 AT_SETUP([GLR: Verbose messages, resolve ambiguity, impure, no locations])
    467 _AT_TEST_GLR_CXXTYPES([%error-verbose],
    468 		      [%merge <stmtMerge>], [%merge <stmtMerge>])
    469 AT_PARSER_CHECK([[./types test-input]], 0,
    470 		_AT_AMBIG_GLR_OUTPUT, _AT_VERBOSE_GLR_STDERR)
    471 AT_CLEANUP
    472