Expression occurrences in flex/bison

Question

Suppose I have a Bison expression like this:

multiply:    T_FIGURE                     { $$ = $1; }
        |    multiply T_ASTERISK multiply { $$ = $1 * $3; }
;

It should return a result of multiplying some figures or give the input back if only one figure provided. If I wanted to limit the number of figures provided to at most 3, I would rewrite the expression like this:

multiply:   T_FIGURE                                          { $$ = $1; }
      |     T_FIGURE T_MULTIPLY T_FIGURE                      { $$ = $1 * $3; }
      |     T_FIGURE T_MULTIPLY T_FIGURE T_MULTIPLY T_FIGURE  { $$ = $1 * $3 * $5; }
;

My question: is there a way to rewrite this expression so that I wouldn't have to manually specify the occurrences and instead use some kind of parameter to be able to easily change the upper limit to, for example, 30 occurrences?

Answer 1

In a word, "No". That is not a feature of bison (nor any yacc derivative I know of).

The easiest way to solve problems like this is to use a code generator. Either use an available macro processor like m4 or write your own script in whatever scripting language you feel comfortable with.

You could also solve the problem dynamically by counting arguments in your semantic action (which means modifying your semantic type to include both a value and a count.) You could then throw a syntax error if the count is exceeded. (Again, in your semantic action.) The main advantage of this approach is that avoids blowing up the parser's state table. If your limits are large and interact with each other, you might find you are producing a very large state machine.

As a very simple example (with only a single operator):

%{
   typedef struct ExprNode {
     int    count;
     double value;
   } ExprNode;
%}

%union {
     ExprNode expr;
     double   value;
}

%token  <value> T_FIGURE
%type   <expr>  expr multiply 
%%

expr:     T_FIGURE          { $$.count = 0; $$.value = $1; }
multiply: expr
        | multiply '*' expr { if ($1.count >= LIMIT) {
                                yyerror("Too many products");
                                YYABORT;
                              }
                              else {
                                $$.count = $1.count + 1;
                                $$.value = $1.value * $3.value;
                              }
                            }