Home | History | Annotate | Download | only in tests 
      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 
     18 AT_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.
     25 m4_define([_AT_TEST_GLR_CXXTYPES],
     26 [AT_BISON_OPTION_PUSHDEFS([%glr-parser $1])
     27 
     28 AT_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 
     82 prog :
     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 
     95 stmt : expr ';'  $2     { $$ = ]$[1; }
     96      | decl      $3
     97      | error ';'        { $$ = new_nterm ("<error>", YY_NULL, YY_NULL, YY_NULL); }
     98      | '@'              { YYACCEPT; }
     99      ;
    100 
    101 expr : 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 
    108 decl : 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 
    115 declarator : 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 
    127 int
    128 main (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 
    207 static Node *
    208 new_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 
    226 static Node *
    227 new_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 
    236 static void
    237 free_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 
    256 static char *
    257 node_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 ]]
    286 m4_bmatch([$2], [stmtMerge],
    287 [[static YYSTYPE
    288 stmtMerge (YYSTYPE x0, YYSTYPE x1)
    289 {
    290   return new_nterm ("<OR>(%s,%s)", x0, x1, YY_NULL);
    291 }
    292 ]])
    293 )
    294 
    295 AT_DATA([test-input],
    296 [[
    297 
    298 z + q;
    299 
    300 T x;
    301 
    302 T x = y;
    303 
    304 x = y;
    305 
    306 T (x) + y;
    307 
    308 T (x);
    309 
    310 T (y) = z + q;
    311 
    312 T (y y) = z + q;
    313 
    314 z + q;
    315 
    316 @
    317 
    318 This is total garbage, but it should be ignored.
    319 ]])
    320 
    321 AT_BISON_CHECK([-o types.c types.y], 0, [], ignore)
    322 AT_COMPILE([types])
    323 AT_BISON_OPTION_POPDEFS
    324 ])
    325 
    326 m4_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 
    338 m4_define([_AT_RESOLVED_GLR_OUTPUT_WITH_LOC],
    339 [[3.0-3.5: +(z,q)
    340 5.0-5.3: <declare>(T,x)
    341 7.0-7.7: <init-declare>(T,x,y)
    342 9.0-9.5: =(x,y)
    343 11.0-11.9: +(<cast>(x,T),y)
    344 13.0-13.5: <declare>(T,x)
    345 15.0-15.13: <init-declare>(T,y,+(z,q))
    346 17.0-17.15: <error>
    347 19.0-19.5: +(z,q)
    348 ]])
    349 
    350 m4_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 
    362 m4_define([_AT_AMBIG_GLR_OUTPUT_WITH_LOC],
    363 [[3.0-3.5: +(z,q)
    364 5.0-5.3: <declare>(T,x)
    365 7.0-7.7: <init-declare>(T,x,y)
    366 9.0-9.5: =(x,y)
    367 11.0-11.9: +(<cast>(x,T),y)
    368 13.0-13.5: <OR>(<declare>(T,x),<cast>(x,T))
    369 15.0-15.13: <OR>(<init-declare>(T,y,+(z,q)),=(<cast>(y,T),+(z,q)))
    370 17.0-17.15: <error>
    371 19.0-19.5: +(z,q)
    372 ]])
    373 
    374 m4_define([_AT_GLR_STDERR],
    375 [[syntax error
    376 ]])
    377 
    378 m4_define([_AT_GLR_STDERR_WITH_LOC],
    379 [[17.5: syntax error
    380 ]])
    381 
    382 m4_define([_AT_VERBOSE_GLR_STDERR],
    383 [[syntax error, unexpected ID, expecting '=' or '+' or ')'
    384 ]])
    385 
    386 m4_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 
    394 AT_SETUP([GLR: Resolve ambiguity, impure, no locations])
    395 _AT_TEST_GLR_CXXTYPES([],
    396                       [%dprec 1], [%dprec 2])
    397 AT_PARSER_CHECK([[./types test-input]], 0,
    398                 [_AT_RESOLVED_GLR_OUTPUT], [_AT_GLR_STDERR])
    399 AT_CLEANUP
    400 
    401 AT_SETUP([GLR: Resolve ambiguity, impure, locations])
    402 _AT_TEST_GLR_CXXTYPES([%locations],[%dprec 1],[%dprec 2])
    403 AT_PARSER_CHECK([[./types test-input]], 0,
    404                 [_AT_RESOLVED_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
    405 AT_CLEANUP
    406 
    407 AT_SETUP([GLR: Resolve ambiguity, pure, no locations])
    408 _AT_TEST_GLR_CXXTYPES([%define api.pure],
    409                       [%dprec 1], [%dprec 2])
    410 AT_PARSER_CHECK([[./types test-input]], 0,
    411                 [_AT_RESOLVED_GLR_OUTPUT], [_AT_GLR_STDERR])
    412 AT_CLEANUP
    413 
    414 AT_SETUP([GLR: Resolve ambiguity, pure, locations])
    415 _AT_TEST_GLR_CXXTYPES([%define api.pure %locations],
    416                       [%dprec 1], [%dprec 2])
    417 AT_PARSER_CHECK([[./types test-input]], 0,
    418                 [_AT_RESOLVED_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
    419 AT_CLEANUP
    420 
    421 AT_SETUP([GLR: Merge conflicting parses, impure, no locations])
    422 _AT_TEST_GLR_CXXTYPES([],
    423                       [%merge <stmtMerge>], [%merge <stmtMerge>])
    424 AT_PARSER_CHECK([[./types test-input]], 0,
    425                 [_AT_AMBIG_GLR_OUTPUT], [_AT_GLR_STDERR])
    426 AT_CLEANUP
    427 
    428 AT_SETUP([GLR: Merge conflicting parses, impure, locations])
    429 _AT_TEST_GLR_CXXTYPES([%locations],
    430                       [%merge <stmtMerge>], [%merge <stmtMerge>])
    431 AT_PARSER_CHECK([[./types test-input]], 0,
    432                 [_AT_AMBIG_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
    433 AT_CLEANUP
    434 
    435 AT_SETUP([GLR: Merge conflicting parses, pure, no locations])
    436 _AT_TEST_GLR_CXXTYPES([%define api.pure],
    437                       [%merge <stmtMerge>], [%merge <stmtMerge>])
    438 AT_PARSER_CHECK([[./types test-input]], 0,
    439                 [_AT_AMBIG_GLR_OUTPUT], [_AT_GLR_STDERR])
    440 AT_CLEANUP
    441 AT_SETUP([GLR: Merge conflicting parses, pure, locations])
    442 _AT_TEST_GLR_CXXTYPES([%define api.pure %locations],
    443                       [%merge <stmtMerge>],[%merge <stmtMerge>])
    444 AT_PARSER_CHECK([[./types test-input]], 0,
    445                 [_AT_AMBIG_GLR_OUTPUT_WITH_LOC], [_AT_GLR_STDERR_WITH_LOC])
    446 AT_CLEANUP
    447 
    448 AT_SETUP([GLR: Verbose messages, resolve ambiguity, impure, no locations])
    449 _AT_TEST_GLR_CXXTYPES([%error-verbose],
    450                       [%merge <stmtMerge>], [%merge <stmtMerge>])
    451 AT_PARSER_CHECK([[./types test-input]], 0,
    452                 [_AT_AMBIG_GLR_OUTPUT], [_AT_VERBOSE_GLR_STDERR])
    453 AT_CLEANUP
    454