CSE340 Fall 2023 – Project 3

The goal of this project  is to give you some hands-on experience with  implementing  a small compiler.  You will write a compiler for a simple language.  You will not be generating assembly code.   Instead, you will generate an intermediate representation  (a data structure that represents the program). The execution of the program will be done after compilation by interpreting the generated intermediate representation using an interpreter that we provide.

1 Introduction

You will write a small compiler that will read an input program and represent it as a linked list. A node of the linked list represents one instruction.  An instruction node speciies:  (1) the type of the instruction, (2) the operand(s) of the instruction (if any) and, for jump instructions, the next instruction to be executed (the default is to execute instructions consecutively in the list order). After the list of instructions is generated by your compiler, your compiler will execute the generated list of instructions by interpreting it.  This means that the program will traverse the data structure and, at every node it visits, it will “execute” the node by changing the content of memory locations corresponding to operands and then proceeds to execute the next instruction after determining what that instruction should be.  This process continues until there is no next instruction to execute. We have provided the code to execute the intermediate representation, so you don’t have to worry about writing it, but you should understand what the provided code expects from your intermediate representation.

These steps are illustrated in the following igure

The remainder of this document is organized into the following sections:

1. Grammar.  Deines the programming language syntax by providing a grammar for it.  The terminals for the grammar are not described in this section, but are provided in the provided lexer iles.

Some highlights of the grammar:

1.  The if stmt does not have else.

2.  The for stmt has a very general syntax similar to that of the for loop in the C language 3.  The input and output keywords are lowercase, but other keywords are all uppercase.

4.  condition has no parentheses.

3 Variables and Locations

The var section contains a list of all variable names that can be used by the program.  There is no type speciied for variables. All variables are int by default. For each variable name, we associate a unique locations that will hold the value of the variable.  This association between a variable name and its location is assumed to be implemented using a function location() that takes a variable name (string) as input and returns an integer value.  The locations where variables will be stored is called mem which is an array of integers.  Each variable in the program should have a unique entry (index) in the mem array.  This association between variable names and locations can be implemented with a location table.

As your parser parses the input program, it allocates locations to variables that are listed in the var section . You can assume that all variable names listed in the var section are unique. For each variable name, a new location needs to be associated with it and the mapping from the variable name to the location needs to be added to the location table.  To associate a location with a variable, you can simply keep a counter that tells you how many locations have been used (associated with variable names).  Initially the counter is 0.  The irst variable to be allocated a location will get the location whose index is 0 (mem[0]) and the counter will be incremented to become 1. The next variable to be associated a location will get the location whose index is 1 and the counter will be incremented to become 2 and so on.

4 Inputs

The list of input values is called inputs and appears as the last section of the input to your compiler. This list must be read by your compiler and stored in an inputs array, which is simply a vector of integers.

5 Execution Semantics

All statements in a statement list are executed sequentially according to the order in which they appear.  Exception is made for some statements in the bodies of if stmt , while stmt , switch stmt , and for stmt as explained below.  In what follows, I will assume that all values of variables as well as constants are stored in locations.  This assumption is used by the execution procedure that we provide. This is not a restrictive assumption.  For variables, you will have locations associated with them. For constants, you can reserve a location in which you store the constant (this is like having an unnamed immutable variable).

5.0.1    Input statements

Input statements get their input from the sequence of inputs. We refer to i’th value that appears in inputs as thte i’th  input.  The execution of the i’th input statement in the program of the form ‘input  a’ is equivalent to:

mem[location("a")]  =  inputs[input_index]

input_index  =  input_index  +  1

where location("a") is an integer index value that is calculated at compile time as we have seen above. Note that the execution of an input statement advances an input index which keeps track (at runtime) of the next value to read.

5.1 Output statement

The statement

output  a;

prints the value of variable a at the time of the execution of the output statement.  That value is stored in mem[location("a")].

5.2 Assignment Statement

To execute an assignment statement, the expression on the righthand side of the equal sign is evaluated and the result is stored in the location associated with the lefthand side of the expression.

5.3 Expression

To evaluate an expression, the values in the locations associated with the two operands are obtained and the expression operator is applied to these values resulting in a value for the expression.

5.4 Boolean Condition

A boolean condition takes two operands as parameters and returns a boolean value.  It is used to control the execution of while, if and for statements.  To evaluate a condition, the values in the locations associated with the operands are obtained and the relational operator is applied to these values resulting in a true or false value. For example, if the values of the two operands a and b are 3 and 4 respectively, a  < b evaluates to true.

5.5    If statement

if stmt has the standard semantics:

1.  The condition is evaluated.

2. If the condition evaluates to true, the body of the if stmt is executed, then the next statement (if any) following the if stmt in the stmt  list is executed .

3. If the condition evaluates to false,  the statement following the  if stmt  in the  stmt  list  is executed.

5.6 While statement

while stmt has the standard semantics .

1.  The condition is evaluated.

2. If the condition evaluates to true, the body of the while  stmt is executed.  The next statement to execute is the while stmt itself.

3. If the condition evaluates to false, the body of the  while stmt is not executed .   The next statement to execute is the next statement (if any) following the while  stmt in the stmt list .

The code block:

WHILE condition

{

stmt list

}

is equivalent to:

label : IF condition

{

stmt list

goto label

}

Jump:  In the code above, a goto statement is similar to the goto statement in the C lan- guage.  Note that goto statements are not part of the grammar and cannot appear in a program (input to your compiler), but our intermediate representation includes jump which is used in the implementation of if, while, for, and switch  statements (jump is discussed later in this document).

5.7 For statement

The for stmt is very similar to the for statement in the C language.  The semantics are deined by giving an equivalent construct.

FOR ( assign stmt 1 condition ; assign stmt 2 )

{

stmt list

}

is equivalent to:

assign stmt 1

WHILE condition

{

stmt list

assign stmt 2

}

For example, the following snippet of code:

FOR  (  a  =  0;  a  < 10; a = a + 1; )

{

output  a;

}

is equivalent to:

a  =  0;

WHILE  a  < 10

{

output  a;

a  =  a  +  1;

}

5.8 Switch statement

switch stmt has the following semantics:

1.  The value of the switch variable is checked against each case number in order.

2. If the value matches the number, the body of the case is executed, then the statement following the switch stmt in the stmt list is executed .

3.  If the value does not match the number, the next case number is checked.

4.  If a default case is provided and the value does not match any of the case numbers, then the body of the default case is executed and then the statement following the switch  stmt in the stmt list is executed .

5.  If there is no default case and the value does not match any of the case numbers, then the statement following the switch stmt in the stmt list is executed .

The code block:

SWITCH var {

CASE n1  :  { stmt list 1 }

...

CASE nk  :  { stmt list k }

}

is equivalent to:

IF var == n1  {

stmt list 1

goto label

}

...

IF var == nk  {

stmt list k

goto label

}

label :

And for switch statements with default case, the code block:

SWITCH var {

CASE n1  :  { stmt list 1 }

...

CASE nk  :  { stmt list k }

DEFAULT : { stmt list default }

}

is equivalent to:

IF var == n1  {

stmt list 1

goto label

}

...

IF var == nk  {

stmt list k

goto label

}

stmt list default

label :

The provided intermediate representation does not have a test for equality.  You are supposed to implement the switch statement with the provided intermediate representation.

Note that the switch statement in the C language has diferent syntax and semantics. It is also dangerous!

6 How to generate the code

The intermediate code will be a data structure (a graph) that is easy to interpret and execute.  I will start by describing how this graph looks for simple assignments then I will explain how to deal with while statements.

Note that, in the explanation below, I start with incomplete data structures then I explain what is missing and make them more complete. You should read the whole explanation.

6.1 Handling simple assignments

A simple assignment is fully determined by: the operator (if any), the id on the left-hand side, and the operand(s). A simple assignment can be represented as a node:

struct  AssignmentInstruction  {

int    left_hand_side_index;

int    opernd1_index;

int    opernd2_index;

ArithmeticOperatorType  op;  //  operator

}

For assignment without an operator on the right-hand side, the operator is set to OPERATOR NONE and there is only one operand.  To execute an assignment, you need calculate the value of the right- hand-side and assign it to the left-hand-side.  If there is an operator, the value of the right-hand-side is calculated by applying the operator to the values of the operands.  If there is no operator, the value of the right-hand-side is the value of the single operand:  for literals (NUM), the value is the value of the number; for variables, the value is the last value stored in the location associated with the variable. Initially, all variables are initialized to 0.  In this representation, the locations associated with variables as well as the locations in which constants are stored are in the mem[] array mentioned above.  In the statement, the index (address) of the location where the value of the variable or the value of the constant is stored is given.  The actual values in mem[] can be fetched or modiied (for variables) at runtime.

Multiple assignments are executed one after another.  So, we need to allow multiple assignment nodes to be linked together. This can be achieved as follows:

struct  AssignmentInstruction  {

int    left_hand_side_index;

int    opernd1_index;

int    opernd2_index;

ArithmeticOperatorType  op;  //  operator

struct  AssignmentStatement*  next;

}

Remember that the data structure represents operands with their indices.  So, you should make sure that you store constant values (NUM) in mem[] at compile time and use the index of the constant as the operand. You cannot use the constant value directly in the data structure.

This data structure will now allow us to execute a sequence of assignment statements represented as a linked-list of assignment instructions: we start with the head of the list, then we execute every assignment in the list one after the other.

Begin  Note It is important to distinguish between compile-time initialization and runtime execution. For example, consider the program

a,  b;

{

a  =  3;

b  =  5;

}

1  2  3  4

The intermediate representation for this program will have have two assignment instructions: one to copy the value in the location that contains the value 3 to the location associated with a and one to copy the value in the location that contains the value 5 to the location associated with b (also, your program should read the inputs and store them in the inputs vector, but this is not the point of this example).   The values 3 and 5 will not be copied to the locations of a and b at compile-time.  The values 3 and 5 will be copied during execution by the interpreter that we provided.  I highly recommend that you read the code of the interpreter that we provided as well as the code in demo.cc.  In demo.cc, a hardcoded data structure is shown for an example input program, which can be very useful in understanding what the data structure your program will generate will look like. End Note

This is simple enough, but does not help with executing other kinds of statements.  We consider them one at a time.