Making YACC output an AST (token tree)

Question

Is it possible to make YACC (or I'm my case MPPG) output an Abstract Syntax Tree (AST).

All the stuff I'm reading suggests its simple to make YACC do this, but I'm struggling to see how you know when to move up a node in the tree as your building it.

Answer 1

Expanding on Hao's point and from the manual, you want to do something like the following:

Assuming you have your abstract syntax tree with function node which creates an object in the tree:

expr : expr '+' expr
  {  
     $$ = node( '+', $1, $3 );  
  }

This code translates to "When parsing expression with a plus, take the left and right descendants $1/$3 and use them as arguments to node. Save the output to $$ (the return value) of the expression.

$$ (from the manual):

To return a value, the action normally sets the pseudovariable ``$$'' to some value.