Decaf Compiler
Classes | Typedefs | Enumerations | Functions
ast.h File Reference

AST nodes and attributes. More...

#include "common.h"

Go to the source code of this file.

Classes

struct  ProgramNode
 AST root structure. More...
 
struct  VarDeclNode
 AST variable structure. More...
 
struct  Parameter
 AST parameter (used in function declarations) More...
 
struct  ParameterList
 Linked list of struct Parameter* elements. More...
 
struct  FuncDeclNode
 AST function structure. More...
 
struct  BlockNode
 AST block structure. More...
 
struct  AssignmentNode
 AST assignment structure. More...
 
struct  ConditionalNode
 AST conditional structure. More...
 
struct  WhileLoopNode
 AST while loop structure. More...
 
struct  ReturnNode
 AST return statement structure. More...
 
struct  BinaryOpNode
 AST binary operation expression structure. More...
 
struct  UnaryOpNode
 AST unary operation expression structure. More...
 
struct  LocationNode
 AST location expression structure. More...
 
struct  FuncCallNode
 AST function call expression structure. More...
 
struct  LiteralNode
 AST literal expression structure. More...
 
struct  Attribute
 AST attribute (basically a key-value store for nodes) More...
 
struct  ASTNode
 Main AST node structure. More...
 
struct  NodeList
 Linked list of struct ASTNode* elements. More...
 

Typedefs

typedef void(* AttributeValueDOTPrinter) (void *, FILE *)
 Function pointer used to store references to custom DOT output routines.
 
typedef void(* Destructor) (void *)
 Function pointer used to store references to custom "free" routines.
 
typedef enum NodeType NodeType
 AST node type tag.
 
typedef struct ProgramNode ProgramNode
 AST root structure.
 
typedef struct VarDeclNode VarDeclNode
 AST variable structure.
 
typedef struct Parameter Parameter
 AST parameter (used in function declarations)
 
typedef struct ParameterList ParameterList
 Linked list of struct Parameter* elements.
 
typedef struct FuncDeclNode FuncDeclNode
 AST function structure.
 
typedef struct BlockNode BlockNode
 AST block structure.
 
typedef struct AssignmentNode AssignmentNode
 AST assignment structure.
 
typedef struct ConditionalNode ConditionalNode
 AST conditional structure. More...
 
typedef struct WhileLoopNode WhileLoopNode
 AST while loop structure.
 
typedef struct ReturnNode ReturnNode
 AST return statement structure. More...
 
typedef enum BinaryOpType BinaryOpType
 Binary operator.
 
typedef struct BinaryOpNode BinaryOpNode
 AST binary operation expression structure.
 
typedef enum UnaryOpType UnaryOpType
 Unary operator.
 
typedef struct UnaryOpNode UnaryOpNode
 AST unary operation expression structure.
 
typedef struct LocationNode LocationNode
 AST location expression structure. More...
 
typedef struct FuncCallNode FuncCallNode
 AST function call expression structure.
 
typedef struct LiteralNode LiteralNode
 AST literal expression structure.
 
typedef struct Attribute Attribute
 AST attribute (basically a key-value store for nodes)
 
typedef struct ASTNode ASTNode
 Main AST node structure. More...
 
typedef struct NodeList NodeList
 Linked list of struct ASTNode* elements.
 

Enumerations

enum  NodeType {
  PROGRAM, VARDECL, FUNCDECL, BLOCK,
  ASSIGNMENT, CONDITIONAL, WHILELOOP, RETURNSTMT,
  BREAKSTMT, CONTINUESTMT, BINARYOP, UNARYOP,
  LOCATION, FUNCCALL, LITERAL
}
 AST node type tag.
 
enum  BinaryOpType {
  OROP, ANDOP, EQOP, NEQOP,
  LTOP, LEOP, GEOP, GTOP,
  ADDOP, SUBOP, MULOP, DIVOP,
  MODOP
}
 Binary operator.
 
enum  UnaryOpType { NEGOP, NOTOP }
 Unary operator.
 

Functions

void dummy_free (void *)
 Fake "free" function that does nothing. More...
 
void dummy_print (void *, FILE *)
 Fake "print" function that does nothing. More...
 
void int_attr_print (void *, FILE *)
 Simple "print" function that prints an attribute value as an integer. More...
 
const char * NodeType_to_string (NodeType type)
 Return a string representation of a node type. More...
 
struct ASTNodeProgramNode_new ()
 Allocate a new program AST node. More...
 
struct ASTNodeVarDeclNode_new (const char *name, DecafType type, bool is_array, int array_length, int source_line)
 Allocate a new variable declaration AST node. More...
 
ParameterListParameterList_new ()
 Allocate and initialize a new, empty list.
 
void ParameterList_add (ParameterList *list, struct Parameter *item)
 Add an item to the end of a list.
 
int ParameterList_size (ParameterList *list)
 Look up the size of a list.
 
bool ParameterList_is_empty (ParameterList *list)
 Test a list to see if it is empty.
 
void ParameterList_free (ParameterList *list)
 Deallocate a list and any contained items.
 
void ParameterList_add_new (ParameterList *list, const char *name, DecafType type)
 Allocate and add a new parameter to a list of parameters. More...
 
struct ASTNodeFuncDeclNode_new (const char *name, DecafType return_type, ParameterList *parameters, struct ASTNode *body, int source_line)
 Allocate a new function declaration AST node. More...
 
struct ASTNodeBlockNode_new (int source_line)
 Allocate a new block declaration AST node. More...
 
struct ASTNodeAssignmentNode_new (struct ASTNode *location, struct ASTNode *value, int source_line)
 Allocate a new assignment statement AST node. More...
 
struct ASTNodeConditionalNode_new (struct ASTNode *condition, struct ASTNode *if_block, struct ASTNode *else_block, int source_line)
 Allocate a new conditional statement AST node. More...
 
struct ASTNodeWhileLoopNode_new (struct ASTNode *condition, struct ASTNode *body, int source_line)
 Allocate a new while loop statement AST node. More...
 
struct ASTNodeReturnNode_new (struct ASTNode *value, int source_line)
 Allocate a new return statement AST node. More...
 
const char * BinaryOpToString (BinaryOpType op)
 Convert a BinaryOpType to a string. More...
 
struct ASTNodeBinaryOpNode_new (BinaryOpType operator, struct ASTNode *left, struct ASTNode *right, int source_line)
 Allocate a new binary operation expression AST node. More...
 
const char * UnaryOpToString (UnaryOpType op)
 Convert a UnaryOpType to a string. More...
 
struct ASTNodeUnaryOpNode_new (UnaryOpType operator, struct ASTNode *child, int source_line)
 Allocate a new unary operation expression AST node. More...
 
struct ASTNodeLocationNode_new (const char *name, struct ASTNode *index, int source_line)
 Allocate a new location expression AST node. More...
 
struct ASTNodeFuncCallNode_new (const char *name, int source_line)
 Allocate a new function call expression AST node. More...
 
struct ASTNodeLiteralNode_new_int (int value, int source_line)
 Allocate a new integer literal expression AST node. More...
 
struct ASTNodeLiteralNode_new_bool (bool value, int source_line)
 Allocate a new boolean literal expression AST node. More...
 
struct ASTNodeLiteralNode_new_string (const char *value, int source_line)
 Allocate a new string literal expression AST node. More...
 
NodeListNodeList_new ()
 Allocate and initialize a new, empty list.
 
void NodeList_add (NodeList *list, struct ASTNode *item)
 Add an item to the end of a list.
 
int NodeList_size (NodeList *list)
 Look up the size of a list.
 
bool NodeList_is_empty (NodeList *list)
 Test a list to see if it is empty.
 
void NodeList_free (NodeList *list)
 Deallocate a list and any contained items.
 
ASTNodeASTNode_new (NodeType type, int line)
 Allocate a new AST node. More...
 
void ASTNode_set_attribute (ASTNode *node, const char *key, void *value, Destructor dtor)
 Add or change an attribute for an AST node. More...
 
void ASTNode_set_printable_attribute (ASTNode *node, const char *key, void *value, AttributeValueDOTPrinter dot_printer, Destructor dtor)
 Add or change a printable attribute for an AST node. More...
 
void ASTNode_set_int_attribute (ASTNode *node, const char *key, int value)
 Add or change an integer attribute for an AST node. More...
 
bool ASTNode_has_attribute (ASTNode *node, const char *key)
 Check to see if a node has a particular attribute. More...
 
void * ASTNode_get_attribute (ASTNode *node, const char *key)
 Retrieve a particular attribute from a node. More...
 
int ASTNode_get_int_attribute (ASTNode *node, const char *key)
 Retrieve a particular integer attribute from a node. More...
 
void ASTNode_free (ASTNode *node)
 Deallocate an AST node structure. More...
 

Detailed Description

AST nodes and attributes.

This module provides declarations of all structures and framework functions for the AST hierarchy. It is a large interface that forms the foundation of several compiler phases and will be necessary for Projects 2 (parsing), 3 (static analysis), and 4 (code generation).

Typedef Documentation

◆ ASTNode

typedef struct ASTNode ASTNode

Main AST node structure.

Provides some basic definitions used across many nodes, such as source code info and attribute management. Storage of type-specific node data is managed using a tagged union of the other *Node structures declared earlier in this file.

AST nodes are designed to be semi-mutable even after parsing by means of the attributes key-value mapping that is stored in every node. List of potential attributes (not exhaustive, and most are irrelevant to Project 2):

KeyDescription
parent Uptree parent ASTNode reference
depth Tree depth (int)
symbolTable Symbol table reference (only in program, function, and block nodes)
type DecafType of node (only in expression nodes)
staticSize Size (in bytes as int) of global variables (only in program node)
localSize Size (in bytes as int) of local variables (only in function nodes)

Generally, the node-type-specific allocators (e.g., ProgramNode_new) should be used to ensure that all of the node-specific data members are initialized correctly. Node structures must be explicitly freed using ASTNode_free.

Methods:

◆ ConditionalNode

AST conditional structure.

else_block can be NULL for if statements with no else clause.

◆ LocationNode

typedef struct LocationNode LocationNode

AST location expression structure.

index can be NULL for non-array locations.

◆ ReturnNode

typedef struct ReturnNode ReturnNode

AST return statement structure.

value can be NULL for return statements with no value (i.e., in void functions).

Function Documentation

◆ AssignmentNode_new()

struct ASTNode* AssignmentNode_new ( struct ASTNode location,
struct ASTNode value,
int  source_line 
)

Allocate a new assignment statement AST node.

Parameters
locationLeft-hand side of assignment
valueRight-hand side of assignment
source_lineSource code line where code begins
Returns
Allocated AST node

◆ ASTNode_free()

void ASTNode_free ( ASTNode node)

Deallocate an AST node structure.

This will recursively free any children, so it is sufficient to free the root of a tree in order to free the entire tree.

It is highly recommended that you subsequently set the pointer to NULL so that you do not unintentionally dereference an invalid pointer.

Parameters
nodePointer to structure to free

◆ ASTNode_get_attribute()

void* ASTNode_get_attribute ( ASTNode node,
const char *  key 
)

Retrieve a particular attribute from a node.

You should immediately cast the returned void* pointer to a pointer of the appropriate type.

Parameters
nodeNode to access
keyKey to retrieve
Returns
Attribute value

◆ ASTNode_get_int_attribute()

int ASTNode_get_int_attribute ( ASTNode node,
const char *  key 
)

Retrieve a particular integer attribute from a node.

This function makes pointer casting unnecessary.

Parameters
nodeNode to access
keyKey to retrieve
Returns
Attribute value

◆ ASTNode_has_attribute()

bool ASTNode_has_attribute ( ASTNode node,
const char *  key 
)

Check to see if a node has a particular attribute.

Parameters
nodeNode to check
keyKey to check for
Returns
True if the node has the requested attribute, false if not

◆ ASTNode_new()

ASTNode* ASTNode_new ( NodeType  type,
int  line 
)

Allocate a new AST node.

Generally, the node-type-specific allocators (e.g., ProgramNode_new) should be used to ensure that all of the node-specific data members are initialized correctly. Exceptions include break and continue nodes, which have no node-specific data.

Node structures allocated by this or any other allocator must be explicitly freed using ASTNode_free (note that this will recursively free any children, so it is sufficient to free the root of a tree in order to free the entire tree).

Parameters
typeNode type
lineSource line (debug info)
Returns
Pointer to allocated node structure

◆ ASTNode_set_attribute()

void ASTNode_set_attribute ( ASTNode node,
const char *  key,
void *  value,
Destructor  dtor 
)

Add or change an attribute for an AST node.

Attributes are node-specific key-value pairs. Keys should be static strings and values should be either integral (i.e., it can fit inside a pointer) or a pointer to some structure on the heap. If the latter, you must provide a pointer to a destructor function that can be used to deallocate the attribute value when the node is deallocated.

Parameters
nodeNode to add the attribute to
keyAttribute key (used to retrieve it later)
valueAttribute value (may be a pointer)
dtorPointer to destructor/deallocator function that should be used to free the attribute value when the node is deallocated

◆ ASTNode_set_int_attribute()

void ASTNode_set_int_attribute ( ASTNode node,
const char *  key,
int  value 
)

Add or change an integer attribute for an AST node.

This is an overload of ASTNode_set_attribute for attributes that are integral; DOT printing and deallocation are handled automatically if you use this function.

Parameters
nodeNode to add the attribute to
keyAttribute key (used to retrieve it later)
valueAttribute value (may be a pointer)

◆ ASTNode_set_printable_attribute()

void ASTNode_set_printable_attribute ( ASTNode node,
const char *  key,
void *  value,
AttributeValueDOTPrinter  dot_printer,
Destructor  dtor 
)

Add or change a printable attribute for an AST node.

This is an overload of ASTNode_set_attribute that requires an additional function pointer that handles printing the value to the DOT graph format.

Parameters
nodeNode to add the attribute to
keyAttribute key (used to retrieve it later)
valueAttribute value (may be a pointer)
dot_printerPointer to printing function that will be used to include the attribute value in DOT graph output
dtorPointer to destructor/deallocator function that should be used to free the attribute value when the node is deallocated

◆ BinaryOpNode_new()

struct ASTNode* BinaryOpNode_new ( BinaryOpType  operator,
struct ASTNode left,
struct ASTNode right,
int  source_line 
)

Allocate a new binary operation expression AST node.

Parameters
operatorBinaryOpType flag
leftLeft-hand operand
rightRight-hand operand
source_lineSource code line where code begins
Returns
Allocated AST node

◆ BinaryOpToString()

const char* BinaryOpToString ( BinaryOpType  op)

Convert a BinaryOpType to a string.

Parameters
opOperand to convert
Returns
String representation of binary operator

◆ BlockNode_new()

struct ASTNode* BlockNode_new ( int  source_line)

Allocate a new block declaration AST node.

Parameters
source_lineSource code line where code begins
Returns
Allocated AST node

◆ ConditionalNode_new()

struct ASTNode* ConditionalNode_new ( struct ASTNode condition,
struct ASTNode if_block,
struct ASTNode else_block,
int  source_line 
)

Allocate a new conditional statement AST node.

Parameters
conditionConditional expression
if_blockBlock to be executed if conditional is true
else_blockBlock to be executed if conditional is false (may be NULL if there is no such block)
source_lineSource code line where code begins
Returns
Allocated AST node

◆ dummy_free()

void dummy_free ( void *  )

Fake "free" function that does nothing.

Useful as a destructor for integral attributes that are smaller than machine pointers (and so can be stored directly in the "value" field of the Attribute struct).

◆ dummy_print()

void dummy_print ( void *  ,
FILE *   
)

Fake "print" function that does nothing.

Useful as a printer for attributes that have no useful representation (e.g., pointers to other nodes).

◆ FuncCallNode_new()

struct ASTNode* FuncCallNode_new ( const char *  name,
int  source_line 
)

Allocate a new function call expression AST node.

Parameters
nameName of function
source_lineSource code line where code begins
Returns
Allocated AST node

◆ FuncDeclNode_new()

struct ASTNode* FuncDeclNode_new ( const char *  name,
DecafType  return_type,
ParameterList parameters,
struct ASTNode body,
int  source_line 
)

Allocate a new function declaration AST node.

Parameters
nameFunction name
return_typeFunction return type
parametersList of function parameters
bodyBody of function (block)
source_lineSource code line where code begins
Returns
Allocated AST node

◆ int_attr_print()

void int_attr_print ( void *  ,
FILE *   
)

Simple "print" function that prints an attribute value as an integer.

Useful as a printer for integral attributes that are smaller than machine pointers (and so can be stored directly in the "value" field of the Attribute struct).

◆ LiteralNode_new_bool()

struct ASTNode* LiteralNode_new_bool ( bool  value,
int  source_line 
)

Allocate a new boolean literal expression AST node.

Parameters
valueLiteral value
source_lineSource code line where code begins
Returns
Allocated AST node

◆ LiteralNode_new_int()

struct ASTNode* LiteralNode_new_int ( int  value,
int  source_line 
)

Allocate a new integer literal expression AST node.

Parameters
valueLiteral value
source_lineSource code line where code begins
Returns
Allocated AST node

◆ LiteralNode_new_string()

struct ASTNode* LiteralNode_new_string ( const char *  value,
int  source_line 
)

Allocate a new string literal expression AST node.

Parameters
valueLiteral value
source_lineSource code line where code begins
Returns
Allocated AST node

◆ LocationNode_new()

struct ASTNode* LocationNode_new ( const char *  name,
struct ASTNode index,
int  source_line 
)

Allocate a new location expression AST node.

Parameters
nameName of location
indexIndex expression (or NULL if not an array location)
source_lineSource code line where code begins
Returns
Allocated AST node

◆ NodeType_to_string()

const char* NodeType_to_string ( NodeType  type)

Return a string representation of a node type.

Parameters
typeType to convert to string
Returns
String representation

◆ ParameterList_add_new()

void ParameterList_add_new ( ParameterList list,
const char *  name,
DecafType  type 
)

Allocate and add a new parameter to a list of parameters.

Parameters
listList to add the new parameter to
nameName of new parameter
typeType of new parameter
Returns
Allocated parameter

◆ ProgramNode_new()

struct ASTNode* ProgramNode_new ( )

Allocate a new program AST node.

This allocator does not require a source code line because it is assumed that the program begins on line 1.

Returns
Allocated AST node

◆ ReturnNode_new()

struct ASTNode* ReturnNode_new ( struct ASTNode value,
int  source_line 
)

Allocate a new return statement AST node.

Parameters
valueReturn expression (can be NULL)
source_lineSource code line where code begins
Returns
Allocated AST node

◆ UnaryOpNode_new()

struct ASTNode* UnaryOpNode_new ( UnaryOpType  operator,
struct ASTNode child,
int  source_line 
)

Allocate a new unary operation expression AST node.

Parameters
operatorUnaryOpType flag
childChild operand
source_lineSource code line where code begins
Returns
Allocated AST node

◆ UnaryOpToString()

const char* UnaryOpToString ( UnaryOpType  op)

Convert a UnaryOpType to a string.

Parameters
opOperand to convert
Returns
String representation of unary operator

◆ VarDeclNode_new()

struct ASTNode* VarDeclNode_new ( const char *  name,
DecafType  type,
bool  is_array,
int  array_length,
int  source_line 
)

Allocate a new variable declaration AST node.

Parameters
nameVariable name
typeVariable type
is_arrayWhether the variable is an array
array_lengthIf is_array, the length of the array
source_lineSource code line where code begins
Returns
Allocated AST node

◆ WhileLoopNode_new()

struct ASTNode* WhileLoopNode_new ( struct ASTNode condition,
struct ASTNode body,
int  source_line 
)

Allocate a new while loop statement AST node.

Parameters
conditionConditional expression
bodyBlock to be executed as long as condition is true
source_lineSource code line where code begins
Returns
Allocated AST node