Use the functions mkleaf and mknode, as described in the ASU book, to create leaf nodes and internal nodes:#define MAX_ARGS 3 struct TreeNode { int type; int leaf_value; TreeNode* args[MAX_ARGS]; };
If you wish, you can use a base class instead, with subclasses for internal nodes and leaf 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; }
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:
And this says that the attribute value associated with the non-terminal term is such a pointer:%union { TreeNode* p; }
Then you can use pointers in the semantic actions:%type <p> term;
expr: expr '+' term { $$ = mknode('+', $1, $3); }
Another hint: In the syntax tree, you can use ';' as an operator that builds lists of statements!