Decaf Compiler
ast.h
Go to the documentation of this file.
1 
10 #ifndef __AST_H
11 #define __AST_H
12 
13 #include "common.h"
14 
18 typedef void (*AttributeValueDOTPrinter)(void*, FILE*);
19 
23 typedef void (*Destructor)(void*);
24 
32 void dummy_free(void*);
33 
40 void dummy_print(void*, FILE*);
41 
49 void int_attr_print(void*, FILE*);
50 
51 
55 typedef enum NodeType {
56  PROGRAM, VARDECL, FUNCDECL, BLOCK,
57  ASSIGNMENT, CONDITIONAL, WHILELOOP, RETURNSTMT, BREAKSTMT, CONTINUESTMT,
58  BINARYOP, UNARYOP, LOCATION, FUNCCALL, LITERAL
59 } NodeType;
60 
67 const char* NodeType_to_string(NodeType type);
68 
72 typedef struct ProgramNode {
73  struct NodeList* variables;
74  struct NodeList* functions;
75 } ProgramNode;
76 
84 struct ASTNode* ProgramNode_new ();
85 
89 typedef struct VarDeclNode {
90  char name[MAX_ID_LEN];
92  bool is_array;
94 } VarDeclNode;
95 
106 struct ASTNode* VarDeclNode_new (const char* name, DecafType type,
107  bool is_array, int array_length, int source_line);
108 
112 typedef struct Parameter {
113  char name[MAX_ID_LEN];
115  struct Parameter* next;
116 } Parameter;
117 
118 /*
119  * Declare ParameterList to be a linked list of Parameter* elements.
120  */
122 
123 
131 void ParameterList_add_new (ParameterList* list, const char* name, DecafType type);
132 
136 typedef struct FuncDeclNode {
137  char name[MAX_ID_LEN];
140  struct ASTNode* body;
141 } FuncDeclNode;
142 
153 struct ASTNode* FuncDeclNode_new (const char* name, DecafType return_type, ParameterList* parameters,
154  struct ASTNode* body, int source_line);
155 
159 typedef struct BlockNode {
160  struct NodeList* variables;
162 } BlockNode;
163 
170 struct ASTNode* BlockNode_new (int source_line);
171 
175 typedef struct AssignmentNode {
176  struct ASTNode* location;
177  struct ASTNode* value;
179 
188 struct ASTNode* AssignmentNode_new (struct ASTNode* location, struct ASTNode* value, int source_line);
189 
195 typedef struct ConditionalNode {
196  struct ASTNode* condition;
197  struct ASTNode* if_block;
198  struct ASTNode* else_block;
201 
212 struct ASTNode* ConditionalNode_new (struct ASTNode* condition, struct ASTNode* if_block,
213  struct ASTNode* else_block, int source_line);
214 
218 typedef struct WhileLoopNode {
219  struct ASTNode* condition;
220  struct ASTNode* body;
221 } WhileLoopNode;
222 
231 struct ASTNode* WhileLoopNode_new (struct ASTNode* condition, struct ASTNode* body, int source_line);
232 
238 typedef struct ReturnNode {
239  struct ASTNode* value;
240 } ReturnNode;
241 
249 struct ASTNode* ReturnNode_new (struct ASTNode* value, int source_line);
250 
257 struct ASTNode* BreakNode_new (int source_line);
258 
265 struct ASTNode* ContinueNode_new (int source_line);
266 
270 typedef enum BinaryOpType {
271  OROP, ANDOP, EQOP, NEQOP, LTOP, LEOP, GEOP, GTOP,
272  ADDOP, SUBOP, MULOP, DIVOP, MODOP
273 } BinaryOpType;
274 
281 const char* BinaryOpToString(BinaryOpType op);
282 
286 typedef struct BinaryOpNode {
287  BinaryOpType operator;
288  struct ASTNode* left;
289  struct ASTNode* right;
290 } BinaryOpNode;
291 
301 struct ASTNode* BinaryOpNode_new (BinaryOpType operator,
302  struct ASTNode* left, struct ASTNode* right,
303  int source_line);
304 
308 typedef enum UnaryOpType {
309  NEGOP, NOTOP
310 } UnaryOpType;
311 
318 const char* UnaryOpToString(UnaryOpType op);
319 
323 typedef struct UnaryOpNode {
324  UnaryOpType operator;
325  struct ASTNode* child;
326 } UnaryOpNode;
327 
336 struct ASTNode* UnaryOpNode_new (UnaryOpType operator, struct ASTNode* child, int source_line);
337 
343 typedef struct LocationNode {
344  char name[MAX_ID_LEN];
345  struct ASTNode* index;
346 } LocationNode;
347 
356 struct ASTNode* LocationNode_new (const char* name, struct ASTNode* index, int source_line);
357 
361 typedef struct FuncCallNode {
362  char name[MAX_ID_LEN];
363  struct NodeList* arguments;
364 } FuncCallNode;
365 
373 struct ASTNode* FuncCallNode_new (const char* name, int source_line);
374 
378 typedef struct LiteralNode {
380  union {
381  int integer;
382  bool boolean;
383  char string[MAX_LINE_LEN];
384  };
385 } LiteralNode;
386 
394 struct ASTNode* LiteralNode_new_int (int value, int source_line);
395 
403 struct ASTNode* LiteralNode_new_bool (bool value, int source_line);
404 
412 struct ASTNode* LiteralNode_new_string (const char* value, int source_line);
413 
417 typedef struct Attribute
418 {
419  const char* key;
420  void* value;
426  struct Attribute* next;
427 } Attribute;
428 
465 typedef struct ASTNode
466 {
470  struct ASTNode* next;
472  /* anonymous union of type-specific node data (C polymorphism) */
473  union {
474  struct ProgramNode program;
475  struct VarDeclNode vardecl;
476  struct FuncDeclNode funcdecl;
477  struct BlockNode block;
478  struct AssignmentNode assignment;
479  struct ConditionalNode conditional;
480  struct WhileLoopNode whileloop;
481  struct ReturnNode funcreturn;
482  struct BinaryOpNode binaryop;
483  struct UnaryOpNode unaryop;
484  struct LocationNode location;
485  struct FuncCallNode funccall;
486  struct LiteralNode literal;
487  };
488 } ASTNode;
489 
490 /*
491  * Declare NodeList to be a linked list of ASTNode* elements.
492  */
493 DECL_LIST_TYPE(Node, struct ASTNode*)
494 
495 
511 ASTNode* ASTNode_new (NodeType type, int line);
512 
528 void ASTNode_set_attribute (ASTNode* node, const char* key, void* value, Destructor dtor);
529 
545 void ASTNode_set_printable_attribute (ASTNode* node, const char* key, void* value,
546  AttributeValueDOTPrinter dot_printer, Destructor dtor);
547 
559 void ASTNode_set_int_attribute (ASTNode* node, const char* key, int value);
560 
568 bool ASTNode_has_attribute (ASTNode* node, const char* key);
569 
580 void* ASTNode_get_attribute (ASTNode* node, const char* key);
581 
591 int ASTNode_get_int_attribute (ASTNode* node, const char* key);
592 
604 void ASTNode_free (ASTNode* node);
605 
606 #endif
AssignmentNode::location
struct ASTNode * location
Left-hand side of assignment.
Definition: ast.h:176
LiteralNode
AST literal expression structure.
Definition: ast.h:378
NodeType
NodeType
AST node type tag.
Definition: ast.h:55
Parameter
AST parameter (used in function declarations)
Definition: ast.h:112
FuncDeclNode
AST function structure.
Definition: ast.h:136
ConditionalNode::if_block
struct ASTNode * if_block
Block to be executed if the condition is true.
Definition: ast.h:197
FuncCallNode_new
struct ASTNode * FuncCallNode_new(const char *name, int source_line)
Allocate a new function call expression AST node.
Definition: ast.c:354
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.
Definition: ast.c:320
ProgramNode
struct ProgramNode ProgramNode
AST root structure.
AssignmentNode_new
struct ASTNode * AssignmentNode_new(struct ASTNode *location, struct ASTNode *value, int source_line)
Allocate a new assignment statement AST node.
Definition: ast.c:258
dummy_free
void dummy_free(void *)
Fake "free" function that does nothing.
Definition: ast.c:14
FuncDeclNode::return_type
DecafType return_type
Function return type.
Definition: ast.h:138
FuncCallNode
AST function call expression structure.
Definition: ast.h:361
ASTNode_get_int_attribute
int ASTNode_get_int_attribute(ASTNode *node, const char *key)
Retrieve a particular integer attribute from a node.
Definition: ast.c:133
BlockNode
struct BlockNode BlockNode
AST block structure.
LocationNode
struct LocationNode LocationNode
AST location expression structure.
UnaryOpNode
AST unary operation expression structure.
Definition: ast.h:323
ASTNode::next
struct ASTNode * next
Next node (if stored in a list)
Definition: ast.h:470
ASTNode
Main AST node structure.
Definition: ast.h:465
WhileLoopNode
struct WhileLoopNode WhileLoopNode
AST while loop structure.
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.
Definition: ast.c:240
ASTNode::attributes
Attribute * attributes
Attribute list (not a formal list because of the provided accessor methods)
Definition: ast.h:469
NodeList
Linked list of struct ASTNode* elements.
Definition: ast.h:493
LiteralNode
struct LiteralNode LiteralNode
AST literal expression structure.
LiteralNode_new_string
struct ASTNode * LiteralNode_new_string(const char *value, int source_line)
Allocate a new string literal expression AST node.
Definition: ast.c:378
Attribute::dtor
Destructor dtor
Pointer to destructor function that should be called to deallocate the attribute value (should be NUL...
Definition: ast.h:423
ContinueNode_new
struct ASTNode * ContinueNode_new(int source_line)
Allocate a new continue statement AST node.
Definition: ast.c:295
LocationNode::name
char name[256]
Location/variable name.
Definition: ast.h:344
FuncDeclNode::body
struct ASTNode * body
Function body block.
Definition: ast.h:140
FuncCallNode::arguments
struct NodeList * arguments
List of actual parameters/arguments.
Definition: ast.h:363
ASTNode_get_attribute
void * ASTNode_get_attribute(ASTNode *node, const char *key)
Retrieve a particular attribute from a node.
Definition: ast.c:138
FuncDeclNode::name
char name[256]
Function name.
Definition: ast.h:137
VarDeclNode::name
char name[256]
Variable name.
Definition: ast.h:90
WhileLoopNode_new
struct ASTNode * WhileLoopNode_new(struct ASTNode *condition, struct ASTNode *body, int source_line)
Allocate a new while loop statement AST node.
Definition: ast.c:275
VarDeclNode
struct VarDeclNode VarDeclNode
AST variable structure.
ReturnNode
AST return statement structure.
Definition: ast.h:238
Parameter::name
char name[256]
Parameter formal name.
Definition: ast.h:113
WhileLoopNode::condition
struct ASTNode * condition
Guard condition (expression)
Definition: ast.h:219
Attribute::key
const char * key
Attribute key.
Definition: ast.h:419
ConditionalNode::condition
struct ASTNode * condition
Guard condition (expression)
Definition: ast.h:196
ConditionalNode
AST conditional structure.
Definition: ast.h:195
LocationNode::index
struct ASTNode * index
Index expression (can be NULL for non-array locations)
Definition: ast.h:345
Attribute::value
void * value
Attribute value (integral value or pointer to heap)
Definition: ast.h:420
DecafType
DecafType
Valid Decaf types.
Definition: common.h:66
UnaryOpNode
struct UnaryOpNode UnaryOpNode
AST unary operation expression structure.
WhileLoopNode::body
struct ASTNode * body
Block to be executed while the condition is true.
Definition: ast.h:220
ReturnNode_new
struct ASTNode * ReturnNode_new(struct ASTNode *value, int source_line)
Allocate a new return statement AST node.
Definition: ast.c:283
LocationNode
AST location expression structure.
Definition: ast.h:343
BinaryOpNode::right
struct ASTNode * right
Right operand expression.
Definition: ast.h:289
ProgramNode::variables
struct NodeList * variables
List of global variable declarations.
Definition: ast.h:73
LiteralNode::integer
int integer
Integer value (if type is INT)
Definition: ast.h:381
ReturnNode
struct ReturnNode ReturnNode
AST return statement 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.
Definition: ast.c:70
NodeType_to_string
const char * NodeType_to_string(NodeType type)
Return a string representation of a node type.
Definition: ast.c:19
LiteralNode::type
DecafType type
Literal type (discriminator/tag for the anonymous union)
Definition: ast.h:379
BinaryOpNode
AST binary operation expression structure.
Definition: ast.h:286
LiteralNode_new_int
struct ASTNode * LiteralNode_new_int(int value, int source_line)
Allocate a new integer literal expression AST node.
Definition: ast.c:362
ASTNode::type
NodeType type
Node type (discriminator/tag for the anonymous union)
Definition: ast.h:467
AttributeValueDOTPrinter
void(* AttributeValueDOTPrinter)(void *, FILE *)
Function pointer used to store references to custom DOT output routines.
Definition: ast.h:18
ASTNode::source_line
int source_line
Source code line number.
Definition: ast.h:468
DECL_LIST_TYPE
#define DECL_LIST_TYPE(NAME, ELEMTYPE)
Declare a singly-linked list structure of the given type.
Definition: common.h:122
BlockNode::statements
struct NodeList * statements
List of statements in the block.
Definition: ast.h:161
ProgramNode_new
struct ASTNode * ProgramNode_new()
Allocate a new program AST node.
Definition: ast.c:222
FuncDeclNode::parameters
ParameterList * parameters
List of formal parameters.
Definition: ast.h:139
AssignmentNode
AST assignment structure.
Definition: ast.h:175
LiteralNode::boolean
bool boolean
Boolean value (if type is BOOL)
Definition: ast.h:382
ParameterList
Linked list of struct Parameter* elements.
Definition: ast.h:121
ReturnNode::value
struct ASTNode * value
Return value (can be NULL for void returns)
Definition: ast.h:239
Parameter::next
struct Parameter * next
Pointer to next parameter (if in a list)
Definition: ast.h:115
ProgramNode::functions
struct NodeList * functions
List of function declarations.
Definition: ast.h:74
BlockNode::variables
struct NodeList * variables
List of local variable declarations in the block.
Definition: ast.h:160
AssignmentNode
struct AssignmentNode AssignmentNode
AST assignment structure.
UnaryOpToString
const char * UnaryOpToString(UnaryOpType op)
Convert a UnaryOpType to a string.
Definition: ast.c:329
dummy_print
void dummy_print(void *, FILE *)
Fake "print" function that does nothing.
Definition: ast.c:3
ConditionalNode
struct ConditionalNode ConditionalNode
AST conditional structure.
ConditionalNode::else_block
struct ASTNode * else_block
Block to be executed if the condition is false (can be NULL if there is no else-block)
Definition: ast.h:198
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.
Definition: ast.c:80
Attribute::dot_printer
AttributeValueDOTPrinter dot_printer
Pointer to DOT-printing function (can be NULL if not printable)
Definition: ast.h:421
VarDeclNode::is_array
bool is_array
True if the variable is an array, false if it's a scalar.
Definition: ast.h:92
BinaryOpType
BinaryOpType
Binary operator.
Definition: ast.h:270
ASTNode_has_attribute
bool ASTNode_has_attribute(ASTNode *node, const char *key)
Check to see if a node has a particular attribute.
Definition: ast.c:120
BinaryOpNode
struct BinaryOpNode BinaryOpNode
AST binary operation expression structure.
ASTNode_new
ASTNode * ASTNode_new(NodeType type, int line)
Allocate a new AST node.
Definition: ast.c:59
VarDeclNode
AST variable structure.
Definition: ast.h:89
MAX_LINE_LEN
#define MAX_LINE_LEN
Maximum length (in characters) of any single line of input.
Definition: common.h:42
Attribute
struct Attribute Attribute
AST attribute (basically a key-value store for nodes)
BlockNode
AST block structure.
Definition: ast.h:159
ASTNode
struct ASTNode ASTNode
Main AST node structure.
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.
Definition: ast.c:230
UnaryOpNode::child
struct ASTNode * child
Child operand expression.
Definition: ast.h:325
WhileLoopNode
AST while loop structure.
Definition: ast.h:218
Parameter::type
DecafType type
Parameter type.
Definition: ast.h:114
common.h
Includes, constants, declarations, and macros used across the compiler.
BinaryOpToString
const char * BinaryOpToString(BinaryOpType op)
Convert a BinaryOpType to a string.
Definition: ast.c:300
FuncCallNode::name
char name[256]
Function name.
Definition: ast.h:362
Attribute
AST attribute (basically a key-value store for nodes)
Definition: ast.h:417
VarDeclNode::array_length
int array_length
Length of array (should be 1 if not an array)
Definition: ast.h:93
MAX_ID_LEN
#define MAX_ID_LEN
Maximum length (in characters) of any identifier.
Definition: common.h:57
BreakNode_new
struct ASTNode * BreakNode_new(int source_line)
Allocate a new break statement AST node.
Definition: ast.c:290
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.
Definition: ast.c:75
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.
Definition: ast.c:50
FuncCallNode
struct FuncCallNode FuncCallNode
AST function call expression structure.
BinaryOpNode::left
struct ASTNode * left
Left operand expression.
Definition: ast.h:288
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.
Definition: ast.c:266
LiteralNode_new_bool
struct ASTNode * LiteralNode_new_bool(bool value, int source_line)
Allocate a new boolean literal expression AST node.
Definition: ast.c:370
BlockNode_new
struct ASTNode * BlockNode_new(int source_line)
Allocate a new block declaration AST node.
Definition: ast.c:250
FuncDeclNode
struct FuncDeclNode FuncDeclNode
AST function structure.
LocationNode_new
struct ASTNode * LocationNode_new(const char *name, struct ASTNode *index, int source_line)
Allocate a new location expression AST node.
Definition: ast.c:346
Parameter
struct Parameter Parameter
AST parameter (used in function declarations)
ProgramNode
AST root structure.
Definition: ast.h:72
ASTNode_free
void ASTNode_free(ASTNode *node)
Deallocate an AST node structure.
Definition: ast.c:152
Destructor
void(* Destructor)(void *)
Function pointer used to store references to custom "free" routines.
Definition: ast.h:23
UnaryOpType
UnaryOpType
Unary operator.
Definition: ast.h:308
Attribute::next
struct Attribute * next
Next attribute (if stored in a list)
Definition: ast.h:426
AssignmentNode::value
struct ASTNode * value
Right-hand side of assignment.
Definition: ast.h:177
VarDeclNode::type
DecafType type
Variable type.
Definition: ast.h:91
UnaryOpNode_new
struct ASTNode * UnaryOpNode_new(UnaryOpType operator, struct ASTNode *child, int source_line)
Allocate a new unary operation expression AST node.
Definition: ast.c:338
int_attr_print
void int_attr_print(void *, FILE *)
Simple "print" function that prints an attribute value as an integer.
Definition: ast.c:9