next up previous contents
Next: 5 Semantic Actions Up: 4 Abstract Syntax Previous: 4.1 The Hard Way


4.2 Case Study: Abstract Syntax Trees for the Calculator Example

We use the following C data structure to capture every possible AST for our calculator:

typedef struct ast {
  enum { int_ast, real_ast, var_ast, str_ast, node_ast } tag;
  union { long          integer;
          double        real;
          char*         variable;
          char*         string;
          struct { ast_kind          tag;
                   struct ast_list*  arguments;
        } node;
      } info;
} ast;
typedef struct ast_list { 
  ast*             elem;
  struct ast_list* next;
} ast_list;
The ast_kind enum list contains all possible tags to label various tree nodes:
typedef enum { if_exp, eq_exp, lt_exp, gt_exp, le_exp, ne_exp, ge_exp, plus_exp, minus_exp,
               times_exp, div_exp, or_exp, and_exp, not_exp, call_exp, fnc_def
} ast_kind;
See the signature file ast.h for a complete definition. ASTs are constructed using the following value contsructors only:
ast* mk_int ( const long x );                         /* create an integer AST leaf */
ast* mk_real ( const double x );                      /* create a floating point AST leaf */
ast* mk_var ( const char* x );                        /* create an AST leaf for a variable */
ast* mk_str ( const char* x );                        /* create a string AST leaf */
ast* mk_node ( const ast_kind tag, ast_list* args );  /* create an internal AST node */
For example,
mk_node(plus_exp,cons(mk_node(minus_exp,cons(mk_var("x"),cons(mk_int(2),null))),
                      cons(mk_int(3),null)))
constructs the AST for the input (x-2)+3. Functions cons and null are like CONS and NIL in Lisp and are used to construct ast_list lists.

The nice thing about this approach is that, if we want to define another tree-like data structure, we just add more tags in ast_kind, one for each different kind of node in the new tree structure. The disadvantage is that it's now easier to make mistakes when writing programs to manipulate these tree structures. For example, we may pass a statement tree in a procedure that handles expression trees and this will not be detected by the C compiler.


next up previous contents
Next: 5 Semantic Actions Up: 4 Abstract Syntax Previous: 4.1 The Hard Way
Leonidas Fegaras
2002-08-26