C2008 Abstract Syntax Trees - CSCI310 – Spring 2008

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.