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.
typedef struct WhileLoopNode	WhileLoopNode
	AST while loop structure.
typedef struct ReturnNode	ReturnNode
	AST return statement structure.
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.
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.
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.
void	dummy_print (void *, FILE *)
	Fake "print" function that does nothing.
void	int_attr_print (void *, FILE *)
	Simple "print" function that prints an attribute value as an integer.
const char *	NodeType_to_string (NodeType type)
	Return a string representation of a node type.
struct ASTNode *	ProgramNode_new (struct NodeList *vars, struct NodeList *funcs)
	Allocate a new program AST node.
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.
ParameterList *	ParameterList_new (void)
	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.
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.
struct ASTNode *	BlockNode_new (struct NodeList *vars, struct NodeList *stmts, int source_line)
	Allocate a new block declaration AST node.
struct ASTNode *	AssignmentNode_new (struct ASTNode *location, struct ASTNode *value, int source_line)
	Allocate a new assignment statement AST node.
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.
struct ASTNode *	WhileLoopNode_new (struct ASTNode *condition, struct ASTNode *body, int source_line)
	Allocate a new while loop statement AST node.
struct ASTNode *	ReturnNode_new (struct ASTNode *value, int source_line)
	Allocate a new return statement AST node.
struct ASTNode *	BreakNode_new (int source_line)
	Allocate a new break statement AST node.
struct ASTNode *	ContinueNode_new (int source_line)
	Allocate a new continue statement AST node.
const char *	BinaryOpToString (BinaryOpType op)
	Convert a BinaryOpType to a string.
struct ASTNode *	BinaryOpNode_new (BinaryOpType operator, struct ASTNode *left, struct ASTNode *right, int source_line)
	Allocate a new binary operation expression AST node.
const char *	UnaryOpToString (UnaryOpType op)
	Convert a UnaryOpType to a string.
struct ASTNode *	UnaryOpNode_new (UnaryOpType operator, struct ASTNode *child, int source_line)
	Allocate a new unary operation expression AST node.
struct ASTNode *	LocationNode_new (const char *name, struct ASTNode *index, int source_line)
	Allocate a new location expression AST node.
struct ASTNode *	FuncCallNode_new (const char *name, struct NodeList *args, int source_line)
	Allocate a new function call expression AST node.
struct ASTNode *	LiteralNode_new_int (int value, int source_line)
	Allocate a new integer literal expression AST node.
struct ASTNode *	LiteralNode_new_bool (bool value, int source_line)
	Allocate a new boolean literal expression AST node.
struct ASTNode *	LiteralNode_new_string (const char *value, int source_line)
	Allocate a new string literal expression AST node.
NodeList *	NodeList_new (void)
	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.
ASTNode *	ASTNode_new (NodeType type, int line)
	Allocate a new AST node.
void	ASTNode_set_attribute (ASTNode *node, const char *key, void *value, Destructor dtor)
	Add or change an attribute for an AST node.
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.
void	ASTNode_set_int_attribute (ASTNode *node, const char *key, int value)
	Add or change an integer attribute for an AST node.
bool	ASTNode_has_attribute (ASTNode *node, const char *key)
	Check to see if a node has a particular attribute.
void *	ASTNode_get_attribute (ASTNode *node, const char *key)
	Retrieve a particular attribute from a node.
int	ASTNode_get_int_attribute (ASTNode *node, const char *key)
	Retrieve a particular integer attribute from a node.
void	ASTNode_free (ASTNode *node)
	Deallocate an AST node structure.

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):

Key	Description
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)
code	ILOC instructions generated from the subtree rooted at this node
reg	Register storing the result of the expression rooted at this node (only in expression 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:

• ASTNode_set_attribute
• ASTNode_set_int_attribute
• ASTNode_set_printable_attribute
• ASTNode_has_attribute
• ASTNode_get_attribute

ConditionalNode

typedef struct ConditionalNode 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

location	Left-hand side of assignment
value	Right-hand side of assignment
source_line	Source 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

node	Pointer 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

node	Node to access
key	Key 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

node	Node to access
key	Key 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

node	Node to check
key	Key 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.

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

type	Node type
line	Source 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

node	Node to add the attribute to
key	Attribute key (used to retrieve it later)
value	Attribute value (may be a pointer)
dtor	Pointer 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

node	Node to add the attribute to
key	Attribute key (used to retrieve it later)
value	Attribute 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

node	Node to add the attribute to
key	Attribute key (used to retrieve it later)
value	Attribute value (may be a pointer)
dot_printer	Pointer to printing function that will be used to include the attribute value in DOT graph output
dtor	Pointer 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

operator	BinaryOpType flag
left	Left-hand operand
right	Right-hand operand
source_line	Source code line where code begins

Returns

Allocated AST node

BinaryOpToString()

const char * BinaryOpToString

(

BinaryOpType

op

)

Convert a BinaryOpType to a string.

Parameters

op	Operand to convert

Returns

String representation of binary operator

BlockNode_new()

struct ASTNode * BlockNode_new	(	struct NodeList *	vars,
		struct NodeList *	stmts,
		int	source_line
	)

Allocate a new block declaration AST node.

Parameters

vars	List of local variable declarations
stmts	List of body statements
source_line	Source code line where code begins

Returns

Allocated AST node

BreakNode_new()

struct ASTNode * BreakNode_new

(

int

source_line

)

Allocate a new break statement AST node.

Parameters

source_line

Source 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

condition	Conditional expression
if_block	Block to be executed if conditional is true
else_block	Block to be executed if conditional is false (may be NULL if there is no such block)
source_line	Source code line where code begins

Returns

Allocated AST node

ContinueNode_new()

struct ASTNode * ContinueNode_new

(

int

source_line

)

Allocate a new continue statement AST node.

Parameters

source_line

Source code line where code begins

Returns

Allocated AST node

dummy_free()

void dummy_free

(

void *

data

)

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 *	data,
		FILE *	output
	)

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,
		struct NodeList *	args,
		int	source_line
	)

Allocate a new function call expression AST node.

Parameters

name	Name of function
args	List of actual arguments
source_line	Source 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

name	Function name
return_type	Function return type
parameters	List of function parameters
body	Body of function (block)
source_line	Source code line where code begins

Returns

Allocated AST node

int_attr_print()

void int_attr_print	(	void *	data,
		FILE *	output
	)

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

value	Literal value
source_line	Source 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

value	Literal value
source_line	Source 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

value	Literal value
source_line	Source 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

name	Name of location
index	Index expression (or NULL if not an array location)
source_line	Source 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

type	Type 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

list	List to add the new parameter to
name	Name of new parameter
type	Type of new parameter

Returns

Allocated parameter

ProgramNode_new()

struct ASTNode * ProgramNode_new	(	struct NodeList *	vars,
		struct NodeList *	funcs
	)

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.

Parameters

vars	List of global variable declarations
funcs	List of function declarations

Returns

Allocated AST node

ReturnNode_new()

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

Allocate a new return statement AST node.

Parameters

value	Return expression (can be NULL)
source_line	Source 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

operator	UnaryOpType flag
child	Child operand
source_line	Source code line where code begins

Returns

Allocated AST node

UnaryOpToString()

const char * UnaryOpToString

(

UnaryOpType

op

)

Convert a UnaryOpType to a string.

Parameters

op	Operand 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

name	Variable name
type	Variable type
is_array	Whether the variable is an array
array_length	If is_array, the length of the array
source_line	Source 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

condition	Conditional expression
body	Block to be executed as long as condition is true
source_line	Source code line where code begins

Returns

Allocated AST node