Re: Building a parse tree...

[Hans Aberg]

Reply-to: address@hidden

At 09:10 +0530 2002/05/18, Steve Fernandez wrote:
>        I'm really sorry if this isn't the place to ask my question, but
>I found no other. I am a novice as far as bison is concerned. I wrote a
>desktop calculator, a common exercise, to compute the value of an
>arithmetic expression. The result was correct. But I need to construct a
>parse tree for the expression. Now I discovered that I could get the
>postfix form of the input expression from the parser, and is there some
>way to build a parse tree using this? Or is there an easier way?

You need to build the parse tree by putting into the grammar suitable
actions that constructs the parse tree during runtime.

I have not needed to do this in practise myself, but here is a suggestion:

If your original calculator grammar has say:
  expr: expr '+' expr { $$.value = $1.value + $3.value }
    | expr '-' expr { $$.value = $1.value - $3.value }
    | expr '*' expr { $$.value = $1.value * $3.value }
    | expr '/' expr { $$.value = $1.value / $3.value }
    | expr '^' expr { $$.value = pow($1.value, $3.value) }
    | '(' expr ')'  { $$.value = $2.value }
    | '-' expr  %prec UMINUS { $$.value = -$2.value }
    | IDENTIFIER expr { $$.value = sqrt($2.value) }
    | ELEMENTARY_FUNCTION expr  { $$.value = (*$1.f)($2.value) }
    | NUMBER
    ;

Then you may for example add (and it is easier to do this under C++ than
under C) to the YYSTYPE a field "branch" that allows you to add nodes say
by:

expr: expr '+' expr { $$.branch = node("expr", "expr", "+", "expr"); }
  | expr '-' expr { $$.branch = node("expr", "expr", "-", "expr"); }
  ...

Here the function node() would create a node of the parse tree with first
argument the grammar rule LHS. This way you need to write it out all for
every rule, so one may try to make some kind of workaround.

The best way would probably be if one defined a macro like
  #define rule_3(x, x1, x2, x3) x: x1 x2 x3 { $$.branch = node(x, x1, x2,
x3); }
and used that to pass the grammar part through the C preprocessor before
passing  the output to Bison. Then your rule would look like:
  rule_3(expr, expr, '+', expr);
  rule_3(expr, expr, '-', expr);
  ...

Unfortunately, Bison is not hooked up like that; the C preprocessor is only
invoked by the (C/C++) compiler processing the Bison output. Therefore one
might try a dynamic (but somewhat runtime slower) solution: Make sure
YYSTYPE is given field "name", with the idea that the code should look like
  expr: expr '+' expr { $$.name = "expr";
     $$.branch = node($$.name, $1.name, $2.name, $3.name); }
  | expr '-' expr { $$.name = "expr";
    $$.branch = node($$.name, $1.name, $2.name, $3.name) }
  ...

As you see, all the rule actions now become the same, except for the rule
length and the LHS name. But the rule length is dynamically available
during parsing, in bison.simple, it is called yylen. And the end of the
stack (probably corresponding to $n) is called yyvsp. So you should be able
to write a function
  node($$.name, yyvsp)
that constructs the parser tree node. (Be aware, though that when you
change skeleton file, names like yyvsp and yylen may change.)

If you the define a macro
  #define NODE(x)  $$.name = #x; node($$.name, yyvsp)
your grammar code might look something like:
  expr: expr '+' expr          { NODE(expr); }
    | expr '-' expr            { NODE(expr); }
    ...
    | '(' expr ')'             { NODE(expr); }
    | '-' expr  %prec UMINUS   { NODE(expr); }
    | IDENTIFIER expr          { NODE(expr); }
    | ELEMENTARY_FUNCTION expr { NODE(expr); }
    | NUMBER                   { NODE(expr); }
    ;

That is, all actions now look the same, which should be fairly easy, even
if they must be written in by hand.

  Hans Aberg