3. How to generate the linked list of instructions Explains how to generate the interme- diate representation (data structure). You should read this sequentially and not skip around.

4. Requirements Lists other requirements.

5. Grading Describes the grading scheme.

2 Grammar

The grammar for this project is the following:

program              →      var section    body   inputs

var section         →      id list   SEMICOLON

id list                   →     ID   COMMA   id list   |   ID

body                     →     LBRACE   stmt list   RBRACE

stmt list              →      stmt   stmt list   |   stmt

stmt                     →      assign stmt   |   while stmt   | if stmt   |   switch stmt   |  for stmt

stmt                     →      output stmt   |   input stmt

assign stmt        →     ID   EQUAL   primary   SEMICOLON

assign stmt        →     ID   EQUAL   expr   SEMICOLON

expr                     →     primary   op   primary

primary              →     ID   |   NUM

op                         →     PLUS   |   MINUS   |   MULT   |   DIV

output stmt        → output ID   SEMICOLON

input stmt          → input ID   SEMICOLON

while stmt          →     WHILE   condition    body

if stmt                 →     IF   condition    body

condition            →     primary   relop   primary

relop                    →      GREATER   |   LESS   |   NOTEQUAL

switch stmt        →      SWITCH   ID   LBRACE   case list   RBRACE

switch stmt        →      SWITCH   ID   LBRACE   case list   default case   RBRACE

for stmt              →     FOR  LPAREN   assign stmt  condition  SEMICOLON   assign stmt   RPAREN   body

case list              →      case    case list   |   case

case                      →      CASE   NUM   COLON   body

default case       →     DEFAULT   COLON   body

inputs                  →      num list

num list              →     NUM

num list              →     NUM num list

Some highlights of the grammar:

1.  Division is integer division and the result of the division of two integers is an integer.

2.  Note that if stmt does not have else.

3.  Note that for has a very general syntax similar to that of the for loop in the C language

4.  Note that the input and output keywords are lowercase, but other keywords are all upper- case.

5.  condition has no parentheses.

6.  There is no type specified for variables. All variables are int by default.

3 Variables and Locations

The var section contains a list of all variable names that can be used by the program.  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 with 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 to variable names).  Initially the counter is 0.  The first variable to be associated 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 body 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 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 (like in project 1).

5.1 Output statement

The statement

output  a;

prints the value of variable a at the time of the execution of the output statement.

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

F0R  (  -  =  o;  -  < 1o; - = - ＋ 1; )

(

output  -;

)

is equivalent to:

-  =  o;

wHILE  -  < 1o

(

output  -;

-  =  -  ＋  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 different 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 ex-

plain 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    operand1_index;

int    operand2_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 in the mem[] array mentioned above. In the statement, the index (address) of the location where the value of the variable or the constant is stored is given.  The actual values in mem[] can be fetched or modified (for variables) at runtime.

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

struct  AssignmentInstruction  {

int    left_hand_side_index;

int    operand1_index;

int    operand2_index;

ArithmeticOperatorType  op;  //  operator

struct  AssignmentStatement*  next;

}

This structure only accepts indices (addresses) as operands. To handle literal constants (NUM), you need to store their values in mem[] at compile time and use the index of the constant as the operant.

This data structure will now allow us to execute a sequence of assignment statements represented in 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.

6.2 Handling output statements

The output statement is straightforward. It can be represented as

struct  OutputInstruction

{

int  var_index;

}

where the operand is the index of the location of the variable to be printed.

Now, we ask:  how can we execute a sequence of statements that are either  assign or  output statement  (or other types of statements)?   We need to put the instructions for both kinds of statements in a list.  So, we introduce a new kind of node:  an instruction node.  The instruction node has a field that indicates which type of instruction it is.  It also has fields to accommodate instructions for the remaining types of statements. It looks like this:

struct  InstructionNode  {

InstructionType  type;    //  NOOP,  ASSIGN,  JMP,  CJMP  (conditional  jump),  IN,  OUT

union  {

struct  {

int    left_hand_side_index;

int    operand1_index;

int    operand2_index;

ArithmeticOperatorType  op;

}  assign_inst;

struct  {

//  details  below

}  jmp_inst;

struct    {

//  details  below

}  cjmp_inst;

struct  {

int  var_index;

}  input_inst  ;

struct    {

int  var_index;

}  output_inst;

};

struct  InstructionNode*  next;

}

This way we can go through a list of instructions and execute one after the other or, if an instruction is a jump instruction, execute the target of the jump after the instruction. To execute a particular instruction node, we check its type. Depending on its type, we can access the appropriate fields in one of the structures of the union. If the type is OUT (output), for example, we access the field var index in the output inst struct to execute the instruction.  Similarly for the IN (input) instruction.  if the type is ASSIGN, we access the appropriate fields in the assign inst struct to execute the instruction and so on.

With this combination of various instructions types in one struct, note how the next field is now part of the InstructionNode to line up all instructions in a sequence one after another.

This is all fine, but we do not yet know how to generate the list of instructions to execute later. The idea is to have the functions that parses non-terminals return the code that corresponds to the non-terminals, the code being a sequence of instructions. For example for a statement list, we have the following pseudocode (missing many checks):

struct  InstructionNode*  parse_stmt_list()

{

struct  InstructionNode*  inst;      //  instruction  for  one  statement

struct  InstructionNode*  instl;    //  instruction  list  for  statement  list

inst  =  parse_stmt();

if  (nextToken  ==  start  of  a  statement  list)

{

instl  =  parse_stmt_list();

append  instl  to  inst;                        //  this  is  pseudocode

return  inst;

}

else

{

ungetToken();

return  inst;

}

}

And to parse body we have the following pseudocode:

struct  InstructionNode*  parse_body()

{

struct  InstructionNode*  instl;

match  LBRACE

instl  =  parse_stmt_list();

match  RBRACE

return  instl;

}

6.3 Handling if and while statements

More complications occur with if and while statements. These statements would need to be imple- mented using the conditional jump (CJMP) and the jump (JMP) instructions. The conditional jump struct would have the following fields

struct  CJMP  {

ConditionalOperatorType  condition_op;

int  operand1_index;

int  operand2_index;

struct  InstructionNode  *  target;

}

The condition op, operand1 index and operand2 index fields are the operator and operands of the condition of the conditional jump (CJMP) instruction. The target field is the next instruction to execute if the condition evaluate to false. If the condition evaluates to true, the next instruction to execute will be the next instruction in the sequence of instructions.

To generate code for the while and if statements, we need to put a few things together. The outline given above for stmt list, needs to be modified as follows (this is missing details and shows only the main steps):

struct  InstructionNode*  parse_stmt()

{

...

InstructionNode  *  inst  =  new  InstructionNode;

if  next  token  is  IF

{

inst->type  =  CJMP;

parse  the  condition  and  set  inst->cjmp_inst .condition_op,

inst->cjmp_inst .operand1_index  and

inst->cjmp_inst .operand2_index

inst->next  =  parse_body();                                                   //  parse_body  returns  a  pointer  to  a  sequence  of  instructions

create  no-op  node                                                                     //  this  is  a  node  that  does  not  result //  in  any  action  being  taken .

//  make  sure  to  set  the  next  field  to  nullptr

append  no-op  node  to  the  body  of  the  if                        //  this  requires  a  loop  to  get  to  the  end  of

//  true_branch  by  following  the  next  field                       //  you  know  you  reached  the  end  when  next  is  nullptr  //  it  is  very  important  that  you  always  appropriately //  initialize  fields  of  any  data  structures                     //  do  not  use  uninitialized  pointers

set  inst->cjmp_inst .target  to  point  to  no-op  node

...

return  inst;

}  else  . . .

}