Game Programming Language
Phase 5: Expressions

This is the hardest phase of the project.  Students who finish this phase on time usually finish the entire project.  Students who don't finish the project on time rarely catch up.

This phase is due the Thursday (at 1am) after spring break.  I recommend you mostly finish this phase in the 17 days between now and spring break.  If you don't finish before spring break you may spend your entire spring break working on this project (which I do not recommend).

Overview:

Implement a class to hold expressions.  Specifically, you need to implement a class that describes a node in an expression tree.  Since a pointer to the root of an expression tree (which is a node in the tree) is a pointer to an entire expression tree, an expression tree can be stored with a single pointer to the root.  In my implementation and in this document, I named this class Expression.  You may name your class whatever you want.

After you have implemented the expression class, add actions to your gpl.y that build an expression tree when an expression is parsed.  Specifically, you need to implement actions for all rules that have the following non-terminals as their left-hand-side (it will help you design the expression class if you understand the code you will write for these actions):

expression
primary_expression
optional_initializer
math_operator
geometric_operator
variable    // except for the rules that have a T_PERIOD on the right-hand-side, will do them later

Once your parser is building expression trees, add actions to initialize integer, double, and string variables to the value of the given expression.  This is done in the rules that have optional_initializer as their left-hand-side.  When you are done, you will be able to initialize int/double/string variables to any legal expression:

int i = 42;
int j = i * 42;
double x = i * j * 1.42 / (55 + 2 * i); // integers are automatically cast to doubles
string = "hello" + " " + "world";
string = "x = " + x;      // doubles and integers are automatically cast to string

For assignment p4 you changed the rule for declaring arrays:

simple_type T_ID T_LBRACKET expression T_RBRACKET

Was changed to:

simple_type T_ID T_LBRACKET T_INT_CONSTANT T_RBRACKET

For p5, you need to change it back (replace T_INT_CONSTANT to expression) and update your action for creating an array so that the expression is evaluated to get the size of the array.  My code looks like this:

simple_type T_ID T_LBRACKET expression T_RBRACKET
{
     ...
     // check that $4 is of type int
     int array_size = $4->eval_int();  // my Expression class has a function eval_int()
     ...
}

The bulk of this assignment is the creation of the data structure to hold an expression tree.   In many gpl statements expressions are evaluated at run-time, and thus we need a data structure to hold an expression so that we can evaluate it at run time.  In this phase of the assignments you will use expression only in one place: variable initialization.  Since variables are initialize only once it would be possible to avoid building an expression tree and simply calculate the value of the expression like you did in p1.  HOWEVER, since we will need the expression tree in the next phase YOU MUST IMPLEMENT IT NOW and use it for variable declarations.

A small but important part of this assignment is to develop a class that can represent a variable.  I call this class Variable (you can use whatever name you want).  There are three forms of variables in gpl, simple variables (such as the variable i), member variables (such as the member variable x of a rectangle variable:  my_rectangle.x), and array variables (such as i[x*y] and my_rectangle[42].x).  There are two types of operations that are performed on variables, set and get.  Class Variable provides a single interface to the three types of variables (simple, member, and array) and to both types of operations (get and set).  A simple variable contains a pointer to a symbol.  If the variable is a member variable, it contains the name of the field plus a pointer to a symbol.  If the variable is an array, it contains a pointer to the expression used to calculate the index and after the index is calculated at run time the symbol can be looked up in the symbol table.
 

Requirements:

In addition to the requirements from p4,  your interpreter must be able to initializes variable (integers, doubles, strings) using an expression and your parser must handle an expression as the size of and array.

In p4 all variables (integer, double, string) were initialized to the constants 42, 3.145, "Hello world".  In this assignment if an optional initializer is not specified, use the values 0, 0.0, "".  Since gpl arrays can never have initial values, they should always be initialized to these default values.

When an error is discovered in an expression that prevents you from creating an expression, create a constant integer expression with value = 0.  This allows the parse to continue and potentially find additional errors before stopping.  For example:

expression T_DIVIDE expression
{

    if either $1 or $3 is of type STRING, there is an error in the expression
        // create a placeholder expression because we can't create the correct expression
        $$ = new Expression(0);  // In my code this creates a constant int expression node w/value = 0

    else
       // create the correct expression   
       $$ = new Expression(...);

}

Hints:

WARNING: In order to initialize variables you do not need an expression tree.  You could simply evaluate the expression while parsing it.  DO NOT DO THIS.  In order to implement statements you need to be able to represent an expression (using an expression tree).  If you do not build an expression tree in this assignment you will not be able to complete the rest of the project (and you won't have enough time to implement the expression tree when you are implementing statements).  

The variable class is needed for future assignments, make sure you implement the variable class as I describe it.  If you don't understand the variable class, talk to me until you do understand it.

If you do not implement an expression class and a variable class you will not be able to complete future assignments.

Expressions in gpl are strongly typed.  The types are integer, double, string, and animation_block (since you don't need them for this phase, it is easier if you add animation_block to your expressions in a later phase).  Since expressions are strongly typed, you must keep type information in the expression class.  If you don't keep type information you will not be able to perform the required error checking.  Consider the following example:

int i = 42 + "hello world";

This input will match the following rule:

simple_type T_ID optional_initializer

The <int> will match simple_type, the <i> will match T_ID, and the <42 + "hello world"> will match expression (optional_initializer derives expression).  Since integers are automatically converted to strings when in a string expression, the expression <42 + "hello world"> is a valid string expression (it has the value "42hello").  In other words, this legal expression is of type string.   In gpl it is a semantic error to assign a string to an integer and thus the above input should generate an error.

The check for correct type can be made as follows (assume that optional_initializer returns a pointer to an expression) and your expression class has a get_type() function:

simple_type T_ID optional_initializer
{
if ($1 == INT) // the type of my simple_type token is Gpl_type
{
int initial_value = 0;  // 0 is the default value for integers
// if an initializer was specified
if ($3 != NULL)
{
    if ($3->get_type() != INT)
         error -- the initializer is not of the correct type
    else initial_value = $3->eval_int();
}
// now a new symbol can be created using initial_value
}
// do other cases here (e.g. $1 == DOUBLE)
}

There are two primary functions of class Expression.   (1) you need to construct the tree, and (2) you need to be able to evaluate it.

The construction is straight forward.  For each expression and primary_expression rule in the grammar, you create a new node in the expression tree.  Since the parser will match the expression in a bottom up fashion, you just build the tree as you parse the expression.  Consider the example of the addition rule:

expression:
 expression T_PLUS expression
 {
  // check that the type of $1 and $3 are compatible 
         $$ = new Expression(PLUS, $1, $3);
 }

All you have to do is create constructors for Expression that can handle all the different configurations of an expression tree and call them in the appropriate actions.   The constructor shown in the above example is for binary expressions.  It takes an operator (I used an enumerated type Operator_type from gpl_type.h) and pointers to two other expressions.   Expression_grammar shows all the rules used to parse expressions. 

Note: for this assignment you will not be adding an action for the following rule:

expression -> variable geometric_operator variable

The Expression evaluation function recursively evaluates each node in the tree.  The algorithm performs a depth-first traversal of the tree.  When a node's evaluation function is called, if the node has children, it calls evaluate on the left child, then the right child, then applies its operator.  If the node holds a constant (integer, double, string), it returns the value.  If it holds a variable, it evaluates the variable (e.g. my_variable->get_int_value() ) and returns the value.

You will need to add a pointer to your expression class to the union in gpl.y.  This means that you will have to add an include for the expression's .h file in parser.h.

Variable class:

The expression node class has to handle several different basic forms:

These forms handle all expressions that do not contain any variables:

3 + 4
7 * -3
6 * sin(42)

In order to handle expressions that contain variables, the expression node will have to handle all the forms of variables.  Consider the following expressions

a
my_rectangle.x
nums[a + b]
rectangles[i + 2].y

We could implement several expression nodes to handle all these possible

Expression Node Forms	Node contents
a	pointer to a symbol that holds a integer, double, or string variable
my_rectangle.x	pointer to a symbol that holds a game object, AND a string to describe the field
nums[a + b]	a symbol for an array AND an expression for the index of the array
rectangles[i + 2].y	a symbol for an array AND an expression for the index of the array AND a string for the field

Or we could implement a class to encapsulate all the possible variables:

Expression Node Forms	Node contents
a	pointer to a Variable object
my_rectangle.x	pointer to a Variable object
nums[a + b]	pointer to a Variable object
rectangles[i + 2].y	pointer to a Variable object

The variable class simply encapsulate these possible forms of a variable into a single interface. 

Note: for this assignment you will not be implementing variables that have fields (i.e. no game object variables).

An added advantage of the Variable class is that when you implement the assignment statement you will be able to use this class to represent variables on the left-hand-side of the assignment operator.

Turning in and Testing:

See docs/turnin.html for a description of how to turn in assignments.

See docs/testing.html for a description of how to test your program.