Programming Languages Homework 3 Solution

Description

• Introduction

In this homework you will implement a tool which includes a simple type checker and a very simple optimizer for JISP language. Detailed information about this programming language was given in the second homework document. You can check it for more information. The tool will rst check if a given JISP program has any syntax error, grammatically. It there are no syntax errors, the tool will perform some type checks for simple cases and it will simplify some special cases of expressions. Read the rest of the document for more information.

• Parser and Scanner

The scanner and the parser which you can use to implement this homework is provided to you. The type checks and the simpli cation of expressions will require you to implement an attribute grammar. You can start from the scanner/parser les provided, or of course, you can write your own versions of scanner and parser from scratch.

• Constant Expressions

We are familiar with the type rules of programming languages, such as \a string value cannot be divided into a real number”, or \a boolean value cannot be added to a real number”, etc. Actual implementations of the programming languages perform very complicated checks for this purpose. In this homework, you will write a type checker that will perform a simpli ed version of such checks, where you will only consider expressions having constants.

One reason we restrict ourselves to constant{only expressions is that the type of the expressions can be inferred easily. For example, if you add two constant integers, you get an integer. However, if the expression has a variable in it, in this case you need to know the type of the variable, which may not be statically possible for a language like JISP, which is dynamically typed.

Another good thing about constant{only expressions is that, we can compute

the value of these expressions statically as well. For example a JISP expression like [“+”, 1, [“*”, 2, 3]] is equivalent to [“+”, 1, 6]], which in turn is equivalent to number 7.

Let us now explain all this in a formal way.

• We call an expression a constant expression:

• 1. if it is an integer literal: In this case the value of the constant expression is the integer literal, and type of the constant expression is integer. Examples are: 7, -3, 0, etc.

• 2. if it is a real literal: In this case the value of the constant expression is the

real literal, and type of the constant expression is real. Examples are: 7.1, -03.0520, 0.5, etc.

• 3. if it is a string literal: In this case the value of the constant expression is the string literal, and type of the constant expression is string. Examples are: Hello World! , CS305 , etc.

• 4. if it is addition, subtraction, multiplication, or division of two operands which are constant expressions, where these constant expressions have type either integer or real: Note that the operands do not have to be literals. Examples are: [“*”, 2, 3] (in this example both operands of the multi-plication are literals), [“+”, 1, [“/”, 4, 2.0]] (in this example the rst operand of the addition is a literal, and the second operand is a constant expression which is not a literal), etc. When the type of both operands are integers, then the type of the constant expression is also integer. When the type of at least one operand is real, the type of the constant expression is real. So, type of [“*”, 2, 3] is integer, whereas the type of [“/”, 4, 2.0] and hence the type of [“+”, 1, [“/”, 4, 2.0]] are both real. The value of the constant expression is the operator (i.e. addition, subtraction, multipli-cation, or division) applied to the values of the operands. For example, the value of [“*”, 2, 3] is 6 and the value of [“+”, 1, [“/”, 4, 2.0]] is 3.0. Note that when both operands of the division are integers, we consider an integer division. Therefore, the value of [“/”, 29, 10] is 2.

• 5. if it is addition of two operands which are constant expressions of type string: In this case the type of the constant expression is string and the value of the constant expression is the concatenation of the values of the operands. Note that, the operands do not have to be string literals. Exam-ples are: [“+”, CS , 305 ], [“+”, Hello , [“+”, , World ]]. The value of the example [“+”, CS , 305 ] is CS305 , and the value of the example [“+”, Hello , [“+”, , World ]] is Hello World .

• 6. if it is multiplication of two operands where the rst operand is a constant expression of type integer and the second operand is a constant expression of type string: Note that, the operands do not have to be literals. Examples are: [“*”, 2, 20 ], [“*”, [“+”, 1, 1], [“+”, 2 , 0 ]], etc. For both of these examples the value is the string 2020 .

where LINENO is the line number where the OPERATOR is located, and RESULT is the value the constant expression.

If the value to be printed is a real number, then you have to round the number up to rst decimal point.

For instance, if we have the following program:

[“+”, [“Get”,”X”] , [“+”, 1, 1 ] ] [“/”,[“Get”,”Y”],[“+”, 1, [“Get”,”X”] ] ] [“*”, 2, [“+”, a , [“Get”, “ID”] ] ] [“/”, 2.5, [“+”, a , [“Get”, “ID”] ] ]

Also note that, even though the last line is possibly an erroneous statement, your tool will not report any error for this line since [“+”, a , [“Get”, “ID”] ] is not a constant expression.

• Example Programs and Ouputs

1. If the program is not grammatically correct then like the second homework you have to print ERROR. For example, if we have the below program:

[

[ Invalid Program ]

]

So, make sure that these three commands are enough to produce the executable. If we assume that there is a JISP le named test17.JISP, we will try out your parser by using the following command line:

username-hw3 < test17.JISP

• Notes

• • Important: Name your les as you are told and don’t zip them. [-10 points otherwise]

• • Important: Make sure you include the right le in your scanner and make sure you can compile your parser using the commands given in the section 7. If we are not able to compile your code with those commands your grade will be zero for this homework.

• • Important: Since this homework is evaluated automatically make sure your output is exactly as it is supposed to be. (check sections 4 and 5 for more details).

• • No homework will be accepted if it is not submitted using SUCourse+.

• • You may get help from our TA or from your friends. However, you must im-plement the homework by yourself.

• • Start working on the homework immediately.

• • LATE SUBMISSION POLICY:

Late submission is allowed subject to the following conditions:

{ Your homework grade will be decided by multiplying what you get from the test cases by a \submission time factor (STF)”.

{ If you submit on time (i.e. before the deadline), your STF is 1. So, you don’t lose anything.

{ If you submit late, you will lose 0.01 of your STF for every 5 mins of delay. { We will not accept any homework later than 500 mins after the deadline. { SUCourse+’s timestamp will be used for STF computation.

{ If you submit multiple times, the last submission time will be used.

8