[SOLVED] Cse 340 project 3!!

AbstractThe 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.You will write a small compiler that will read an input program and represent in a linked list as a sequence of instruction. A node of the linked list represents one instruction. A instruction node specifies: (1) the type of the instructions, (2) the operand(s) of the instruction (if any) and, for jump instructions, the next instruction to be executed (the default is that the next instruction in the list is executed). 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 deciding what is the next instruction to execute (program counter). The output of your compiler is the output that the input program should produce. These steps are illustrated in the following figureThe remainder of this document is organized into the following sections:The grammar for this project is the following:inputstmt input ID SEMICOLON while stmt WHILE condition bodySome highlights of the grammar: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.The list of input values is called inputs and appears as the last section of an input program. This list must be read by your compiler and stored in an inputs array, which is simply a vector of integers.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 and switch 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 statementsInput statements get their input from the sequence of inputs. We refer to ith value that appears in inputs as ith input. The execution of the ith input statement in the program of the form input a is equivalent to:mem[location(a)] = inputs[input_index] input_index = input_index + 1where 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).The statement output a; prints the value of variable a at the time of the execution of the output 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.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.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.if stmt has the standard semantics:while stmt has the standard semantics.The code block:is equivalent to:Jump. In the code above, a goto statement is similar to the goto statement in the C language. 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).The for stmt is very similar to the for statement in the C language. The semantics are defined by giving an equivalent construct.is equivalent to:assign stmt 1WHILE condition{stmt list assign stmt 2 }For example, the following snippet of code:is equivalent to:switch stmt has the following semantics:The code block:is equivalent to:And for switch statements with default case, the code block:is equivalent to:Note that the switch statement in the C language has different syntax and semantics. It is also dangerous!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.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 righthand-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 programa, b;{a = 3; b = 5;}1 2 3 4The 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 NoteThis is simple enough, but does not help with executing other kinds of statements. We consider them one at a time.The output statement is straightforward. It can be represented asstruct 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, OUTunion { 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 listinst = 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 RBRACEreturn instl;}More complications occur with if and while statements. These statements would need to be implemented using the conditional jump (CJMP) and the jump (JMP) instructions. The conditional jump struct would have the following fieldsstruct 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_indexinst->next = parse_body(); // parse_body returns a pointer to a sequence of instructionscreate no-op node // this is a node that does not result// in any action being taken.// make sure to set the next field to nullptrappend 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 pointersset inst->cjmp_inst.target to point to no-op node return inst;} else }The following diagram shows the desired structure for the if statement:Sequence of instructions for body of if stmtThe stmt list code should be modified because the code presented above for a stmt list assumed that each statement is represented with one instruction but we have just seen that parsing an if list returns a sequence of instructions. The modification is as follows:struct InstructionNode* parse_stmt_list(){ struct InstructionNode* instl1; // instruction list for stmt struct InstructionNode* instl2; // instruction list for stmt listinstl1 = parse_stmt(); if (nextToken == start of a statement list){instl2 = parse_stmt_list();append instl2 to instl1// instl1// |// V // .// .// .// last node in// sequence staring// with instl1// |// V// instl2return instl1;} else { ungetToken(); return instl1;}}Handling while statement is similar. Here is the outline for parsing a while statement and creating the data structure for it:create instruction node inst if next token is WHILE{inst->type = CJMP; // handling WHILE using if and goto nodesparse the condition and set inst->cjmp_inst.condition_op, inst->cjmp_inst.operand1 and inst->cjmp_inst.condition_operand2set jmp->jmp_inst.target to inst append jmp node to end of body of whilecreate no-op node and attach it to the list of instruction after the jmp node set inst->cjmp_target.target to point to no-op node return inst;} The following diagram shows the desired structure for the while statement:Sequence of instructions for body of while stmtYou can handle the switch and for statements similarly, but you should figure that yourself. Use a combination of JMP and CJMP to support the semantics of the switch and for statements. See sections 5.8 and 5.7 for the semantics of the switch and for statements.After the graph data structure is built, it needs to be executed. Execution starts with the first node in the list. Depending on the type of the node, the next node to execute is determined. The general form for execution is illustrated in the following pseudo-code.pc = first node while (pc != nullptr){ switch (pc->type){// or// pc = pc->next (if condition is true)}}We have provided you with the data structures and the code to execute the graph and you must use it. When you submit your code, you will not submit compiler.cc and compiler.h, we will provide them automatically for your submission, so if you modify them, your submission will not compile and run.. There are two files compiler.h and compiler.cc, you need to write your code in separate file(s) and #includecompiler.h. The entry point of your code is a function declaredin compiler.h: struct InstructionNode* parse_generate_intermediate_representation();You need to implement this function. The main() function is provided in compiler.cc:int main(){ struct InstructionNode * program;program = parse_generate_intermediate_representation(); execute_program(program); return 0;}It calls the function that you will implement which is supposed to parse the program and generate the intermediate representation, then it calls the execute program function to execute the program. You should not modify any of the given code. In fact, you should not submit compiler.cc and compiler.h; we will provide them when you submit your code.