Give me the estimate I wasn't happy with the last 2 orders of mine
CSE 340 Spring 2019 – Project 4 Due on April 26 2019 by 11:59 pm Abstract 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. 1 Introduction You will write a small compiler that will read an input program and represent it in an internal data structure. The data structure consists of two parts: (1) a representation of instructions to be executed and (2) a representation of the memory of the program (locations for variables). Instructions are represented by a data structure that includes the operand(s) of the instruction (if any) and that specify the next instruction to be executed. After the data structures are generated by your compiler, your compiler will execute the generated instructions representation 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 figure 1 The remainder of this document is organized as follows: 1. Grammar Defines the programming language syntax including grammar. 2. Execution Semantics Describe statement semantics for if, while, switch and print state- ments. 3. How to generate the intermediate representation Explains step by step how to generate the intermediate representation (data structure). You should read this sequentially and not skip around. 4. Executing the intermediate representation Basically, you have two options: (1) If you are using C/C++, you should use the code we provide to execute the intermediate represen- tation; (2) If you are using Java, this section describes the strict rules to follow in executing the intermediate representation. Those rules will be enforced by inspecting your code. 5. Requirements Lists the programming languages you are allowed to use in your solution (C/C++ or Java) and other requirements. 6. Grading Describes the grading scheme. 7. Second Chance Project Describes the requirements for a bonus project. 2 Grammar The grammar for this project is a simplified form of the grammar from the previous project, but there are a couple extensions. program → var section body 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 | print stmt | while stmt | if stmt | switch stmt | for 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 print stmt → print 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 2 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 Some highlights of the grammar: 1. Expressions are greatly simplified and are not recursive. 2. There is no type declaration section. 3. Division is integer division and the result of the division of two integers is an integer. 4. if statement is introduced. Note that if stmt does not have else. 5. for statement is introduced. Note that for has a very general syntax similar to that of the for loop in the C language 6. A print statement is introduced. Note that the print keyword is in lower case, but other keywords are all upper-case letters. 7. There is no variable declaration list. There is only one id list in the global scope and that contains all the variables. 8. There is no type specified for variables. All variables are int by default. 3 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 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). 3.1 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. 3.2 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. 3 3.3 Boolean Condition A boolean condition takes two operands as parameters and returns a boolean value. It is used to control the execution of while and if 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.="" 3.4="" 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="" these="" semantics="" apply="" recursively="" to="" nested="" if="" stmt.="" 3.5="" 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.="" these="" semantics="" apply="" recursively="" to="" nested="" while="" stmt.="" the="" code="" block:="" while="" condition="" {="" stmt="" list="" }="" is="" equivalent="" to:="" label="" :="" if="" condition="" {="" stmt="" list="" goto="" label="" }="" 4="" note="" that="" goto="" statements="" do="" not="" appear="" in="" the="" input="" program,="" but="" our="" intermediate="" represen-="" tation="" includes="" gotostatement="" which="" is="" used="" in="" conjunction="" with="" ifstatement="" to="" represent="" while="" and="" switch="" statements.="" 3.6="" 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:="" for="" (="" a="0;" a="">< 10;="" a="a" +="" 1;="" )="" {="" print="" a;="" }="" is="" equivalent="" to:="" a="0;" while="" a="">< 10 { print a; a = a + 1; } 3.7 switch statement switch stmt has the following semantics1: 1the switch statement in the c language has different syntax and semantics. it is also dangerous! 5 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, next case is evaluated. 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. these semantics apply recursively to nested switch stmt. 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: 6 if var == n1 { stmt list 1 goto label } ... if var == nk { stmt list k goto label } stmt list default label : 3.8 print statement the statement print a; prints the value of variable a at the time of the execution of the print statement. 4 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. 4.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 assignmentstatement { struct valuenode* left_hand_side; struct valuenode* operand1; struct valuenode* operand2; arithmeticoperatortype op; // operator } for assignment without an expression on the right-hand side, the operator is set to operator none and there is only one operand. to execute an assignment, you need the values of the operand(s), apply the operator, if any, to the operands and assign the resulting value of the right-hand side to the left hand side. 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 7 locations in which constants are stored are value nodes ( struct valuenode), a node that 10="" {="" print="" a;="" a="a" +="" 1;="" }="" 3.7="" switch="" statement="" switch="" stmt="" has="" the="" following="" semantics1:="" 1the="" switch="" statement="" in="" the="" c="" language="" has="" different="" syntax="" and="" semantics.="" it="" is="" also="" dangerous!="" 5="" 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,="" next="" case="" is="" evaluated.="" 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.="" these="" semantics="" apply="" recursively="" to="" nested="" switch="" stmt.="" 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:="" 6="" if="" var="=" n1="" {="" stmt="" list="" 1="" goto="" label="" }="" ...="" if="" var="=" nk="" {="" stmt="" list="" k="" goto="" label="" }="" stmt="" list="" default="" label="" :="" 3.8="" print="" statement="" the="" statement="" print="" a;="" prints="" the="" value="" of="" variable="" a="" at="" the="" time="" of="" the="" execution="" of="" the="" print="" statement.="" 4="" 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.="" 4.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="" assignmentstatement="" {="" struct="" valuenode*="" left_hand_side;="" struct="" valuenode*="" operand1;="" struct="" valuenode*="" operand2;="" arithmeticoperatortype="" op;="" operator="" }="" for="" assignment="" without="" an="" expression="" on="" the="" right-hand="" side,="" the="" operator="" is="" set="" to="" operator="" none="" and="" there="" is="" only="" one="" operand.="" to="" execute="" an="" assignment,="" you="" need="" the="" values="" of="" the="" operand(s),="" apply="" the="" operator,="" if="" any,="" to="" the="" operands="" and="" assign="" the="" resulting="" value="" of="" the="" right-hand="" side="" to="" the="" left="" hand="" side.="" 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="" 7="" locations="" in="" which="" constants="" are="" stored="" are="" value="" nodes="" (="" struct="" valuenode),="" a="" node="">