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: 5 Semantic Actions Up: 4 Abstract Syntax Previous: 4.1 The Hard Way
Leonidas Fegaras
2002-08-26