next up previous contents
Next: 5 Semantic Actions Up: 4 Abstract Syntax Previous: 4.2 Building Abstract Syntax   Contents

4.3 Building Abstract Syntax Trees in C

The previous example of expression ASTs can be written as follows in C:

typedef struct Exp {
  enum { integer_exp, string_exp, variable_exp,
         binary_exp, unary_exp, call_exp,
         projection_exp, record_exp } tag;
  union { int                                      integerExp;
          string                                   stringExp;
          string                                   variableExp;
          struct { string           operator;
                   struct Exp*      left;
                   struct Exp*      right; }       binaryExp;
          struct { string           operator;
                   struct Exp*      operand; }     unaryExp;
          struct { string           name;
                   struct Exp_list* arguments; }   callExp;
          struct { struct Exp*  record;
                   string       attribute; }       projectionExp;
          struct rec { string       attribute;
                       struct Exp*  value;
                       struct rec*  next; }        recordExp;
      } op;
} ast;
where Exp_list is a list of ASTs:
typedef struct Exp_list { 
  ast*             elem;
  struct Exp_list* next;
} ast_list;
It's a good idea to define a constructor for every kind of expression to simplify the task of constructing ASTs:
ast* make_binaryExp ( string operator, ast* left, ast* right ) {
  ast* e = (ast*) malloc(sizeof(ast));
  e->tag = binary_exp;
  e->op.binary.operator = operator;
  e->op.binary.left = left;
  e->op.binary.right = right;
  return e;
For example,
constructs the AST for the input (x-2)+3.