Abstract Syntax Trees

There are three basic types of trees you need to deal with:

Statements
Expressions
Declarations

Each of these also has subtypes. The following describes these subtypes.

Statement trees

If statement - used to represent a selection-stmt
```
      If -----------> Next
  |   |    |
Test Then Else(op) 
```
Test will be an Expression tree. Then and Else will be Statement trees. Else is optional (may be NULL). Next points to the next Statement tree or is NULL.
Return statement - used to represent a return-stmt
```
      Return -----> Next
        |
       Exp
```
Exp is an Expression tree. Exp is optional (may be NULL). Next points to the next Statement tree or is NULL.
While statement - used to represent an while-stmt
```
      While -----> Next
      |  |
    Test Body
```
Test is an Expression tree. Body is a Statement tree. Next points to the next Statement tree or is NULL.
For statement - used to represent an for-stmt
```
      For -------------> Next
   |   |    |   |
 Init Test Iter Body
```
Init, Test, Iter are Expression trees (which could be NULL). Body is a Statement tree. Next points to the next Statement tree or is NULL.
Do statement - used to represent an do-stmt
```
      Do -------------> Next
    |    |   
  Test  Body
```
Test is an Expression tree (which could be NULL). Body is a Statement tree. Next points to the next Statement tree or is NULL.
Compound statement - used to represent a compound-stmt
```
       Compound -----> Next
      |        |
    LocalDecls Statement-list
```
LocalDecls is the first of a series of Declaration trees. It may be NULL. Statement-list is the first of a series of Statement trees. It may be NULL. Next points to the next Statement tree or is NULL.
Expression statement - used to represent an expression-stmt
```
      Expression -----> Next
         |  
       Exp 
```
Exp is an Expression tree. Next points to the next Statement tree or is NULL. This structure is optional -- you could use an Expression tree directly instead.

Expression trees

Operation tree - used to represent a var=expression, simple-expression, additive-expression, term, logical operation.
```
   Operator --> Next
     |  |
  LOper ROper 
```
Operator is a structure that includes the type of operation (!, INC, DEC, =,+,-,*,/, and relational operators). LOper and ROper are Expression trees. ROper is NULL for unary operators.Next points to the next Expression tree (used when defining arglists) or may be NULL.
Const tree - used to represent a NUMLIT, FNUMLIT, CHAR
```
Const --> Next
```
Const is a structure containing a value. Next points to the next Expression tree (used when defining arglists) or may be NULL.
Var tree - used to represent a var
```
     Var --> Next
      |
     subscript
```
Var is a structure that includes a name. Subscript is an Expression tree. It may be NULL (if the ID is not an array). Next points to the next Expression tree (used when defining arglists) or may be NULL.
Call tree - used to represent a call
```
    Call --> Next 
    |   |
   var Arglist
```
Call is a structure. Var is a var tree node for the function name. Arglist is the first in a series of expression trees. It may be NULL. Next points to the next Expression tree (used when defining arglists) or may be NULL.

Declaration Trees

Variable Declaration tree - used to represent var-declaration
```
      VarDecl -> Next
```
VarDecl is a structure that includes a name, type, and size. If the variable represented is not an array, size is -1. Otherwise, size is the size of the array. Next points to the next Declaration tree or is NULL.
Function Declaration tree - used to represent fun-declaration
```
     FunDecl -> Next
     |     |
   Params Body
```
FunDecl is a structure that includes a name and type. Params points to the first in a series of Param trees. Params may be NULL. Body is a Compound Statement tree. Next points to the next Declaration tree or is NULL.
Param tree - used to represent param
```
     Param -> Next
```
Param is a structure that includes a name, type, and a flag as to whether the param is a single variable or array. Next points to the next Param tree or is NULL.

Elizabeth Johnson

Last modified: Wed Mar 13 11:11:40 EST 2002