KOI: Some hints for lab 5

You can use just one record type to represent both leaf nodes and internal nodes:

#define MAX_ARGS 3

struct TreeNode {
  int type;
  int leaf_value;
  TreeNode* args[MAX_ARGS];
};

Use the functions mkleaf and mknode, as described in the ASU book, to create leaf nodes and internal nodes:

TreeNode* mkleaf(int type, int value) {
  TreeNode* p = new TreeNode();
  p->type = type;
  p->leaf_value = value;
  return p;
}

TreeNode*
mknode(int type, TreeNode* a0 = 0, TreeNode* a1 = 0, TreeNode* a2 = 0) {
  TreeNode* p = new TreeNode();
  p->type = type;
  p->args[0] = a0;
  p->args[1] = a1;
  p->args[2] = a2;
  return p;
}

If you wish, you can use a base class instead, with subclasses for internal nodes and leaf nodes.

By default, the attribute values used by Yacc ("$$", "$1", etc.) are integers, and you need to tell Yacc that now you are using pointers to tree nodes instead. This (in the Yacc input file) says that an attribute can be of the type pointer to TreeNode:

%union {
  TreeNode* p;
}

And this says that the attribute value associated with the non-terminal term is such a pointer:

%type <p> term;

Then you can use pointers in the semantic actions:

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

Another hint: In the syntax tree, you can use ';' as an operator that builds lists of statements!

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) February 11, 2002