Multiple, different, %merge of a token sequence

[Derek M Jones]

All,

I'm not sure if the following is a feature or a bug.

There are four parses of the C input (x)*sizeof(y);

(x) can be parsed as:

   1) a cast of the expression *sizeof(y) to the type x (not
      possible semantically, but this is syntax)
   2) the left operand of the multiplication operator *

sizeof(y) can be parsed as:

   1) the sizeof the expression (y)
   2) the sizeof the type y

I put %merge on the production for sizeof (see below) and
was expecting the sizeof ambiguity to  be 'fully' resolved.

What happens is that the bison generated parser builds
all four parse stacks, resolves one pair of sizeof
ambiguities by calling sizeof_merge (leaving three stacks)
and then calls multiplicative_merge twice (leaving 1 stack).

I think there should be two calls to sizeof_merge and one to
multiplicative_merge.

This is a problem because the xxx_merge code free's up the
parse tree generated by the production that is discarded.
The three parse trees passed to multiplicative_merge
some share common subtrees, which means it is possible for
the same nodes to be free'ed more than once (not good).
The nodes of the parse trees passed to sizeof_merge are all
unique and will be free'ed once each.

Is this behavior a bug in the parser generated by bison (I
hope so) or a feature of the way things have to work?

%glr-parser

%token
ID

%{
#include <ctype.h>
#include <stdio.h>

static const char *input = "(x)*S(y);";

#define YYSTYPE char *

static void yyerror (const char *s)
{
  printf ("%s\n", s);
}

static YYSTYPE multiplicative_merge(YYSTYPE a, YYSTYPE b)
{
char *s;
asprintf (&s, "\n{ %s %s }\n\t", a, b);

printf("multiplicative_merge\n");
return s;
}

static YYSTYPE sizeof_merge(YYSTYPE a, YYSTYPE b)
{
char *s;
asprintf (&s, "\n{ %s %s }\n\t", a, b);

printf("sizeof_merge\n");
return s;
}

static int yylex (void);
%}

%%

TU:
        translation_unit
        { }                   ;

translation_unit:
              statement
              { }        ;

primary_expr:
              ID
              { }                      |
              '(' expression ')'
              { }                      ;

postfix_expr:
              primary_expr
              { }                      ;

unary_expr:
              postfix_expr
              { }                 |
              '*' cast_expr
              { }                 |
              'S' unary_expr                   %merge <sizeof_merge>
              {
               printf("S unary_expr\n");
               }                 |
              'S' '(' type_specifier ')'       %merge <sizeof_merge>
              {
               printf("S ( type_specifier )\n");
               }                 ;

cast_expr:
              unary_expr                         %dprec 1
              { }                             |
              '(' type_specifier ')' cast_expr   %dprec 2
              { }                             ;

multiplicative_expr:
              cast_expr                         %merge 
<multiplicative_merge>
              { }                         |
              multiplicative_expr '*' cast_expr %merge 
<multiplicative_merge>
              { }                         ;

expression:
              multiplicative_expr
              { }                     ;

type_specifier:
              typedef_name
              {
              }           ;

typedef_name:
              ID  %dprec 1
              { } ;

statement:
              expression ';'
              {
              printf("%s\n", "statement\n");
              } ;

%%


static int yylex (void)
{
  char c = *input ? *input++ : 0;
  asprintf (&yylval, "%c", c);
  return (isalpha(c) && (c != 'S')) ? ID : c;
}

int main (void)
{
yydebug=1;
printf ("%i\n", yyparse ());
}

--
Derek M. Jones                              tel: +44 (0) 1252 520 667
Knowledge Software Ltd                      mailto:address@hidden
Applications Standards Conformance Testing    http://www.knosof.co.uk