Home | Notes | Languages | Programs | Homework |
Program Assignment 1 |
Problem |
Write a program that evaluates infix arithmetic expressions, including support for parentheses, assignment, and single-letter variables. The following operators must be supported:
+ - * / % (remainder) ( ... ) + (unary) - (unary) = (assignment) X (variable reference, where X is any letter)
Implementation Language |
For this assignment, your program must be written in Pascal. Your solution may only use standard Pascal code, not extensions or special library routines provided with your compiler. Your program must adhere to proper use of the Pascal language as well as good programming style, including embedded routines, scoping, parameter passing, identifier naming, routine length, etc.
Input Format |
Your program should be able to evaluate valid arithmetic expressions of arbitrary length. Your program should read a sequence of zero or more "candidate expressions", one per line, from its standard input (in the sense that this exists in Pascal). For each line of input, your program should attempt to interpret the line's contents as an expression. The "end" of the list of expressions is indicated by EOF on standard input. Blank lines in the input should simply be skipped.
Expressions will be made up of the following tokens:
To be more precise, the following EBNF grammar describes the syntax of allowable expressions:
<expression> --> <variable> = <expression> | <additive_expr> <additive_expr> --> <term> { ( '+' | '-' ) <term> } <term> --> <factor> { ( '*' | '/' | '%' ) <factor> } <factor> --> <integer> | ( '+' | '-' ) <factor> | '(' <expression> ')' | <variable> <variable> --> A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Variables: Think of the 26 variables as local variables that are initialized to 0 at the start of your program, and that retain their values from expression to expression.
Assignment: An assignment expression contains a variable on the left hand side and a value on the right:
X = 2 * 3
The meaning of such a statement is to compute the value on the right, then assign it to the variable on the left. The value of this entire expression is then the new value of the variable.
Precedence: The grammar above reflects the normal arithmetic precedence of the operators it includes, which should be reflected in your solution.
Associativity: As with most languages, the expectation here is that operators at the same precedence level should be left-associative. The only exception here is assignment, which is right-associative. Your solution must implement associativity correctly as well.
Example expressions:
(1 + 2 + 3 + 4 + 5) (1 - 2 - 3 - 4 - 5) (- 1 - 2 - 3 - 4 - 5) (1 * 2 * 3 * 4 * 5) (1 / 2 / 3 / 4 / 5) (- (3 * 2) + (101 - 99) * (999 - 994)) - - - 4 + + 6 (1 + 2 * 3 - 4 / 5 + 6 * 7 - 8 / 9) X = 2 * (3 + 4) A = B = C = D A = (B = 2 * (C = 3 + (D = 20 / 5))) 16 / D 102 % (Z = A / C)
Output Format |
For each input expression (i.e., each line), your program will produce
a "translation" on its standard output. The first line of this
translation should start with "//
" and be followed by
the original expression as it was read in.
If the expression is valid and can be evaluated, the "translation" is a series of "assembly language" instructions for evaluating the expression on an abstract, stack-oriented machine. For this assignment, we will use a simplified subset of the instructions used by the Java Virtual Machine (for complete details, see The JVM Specification).
Our assembly language consists of the following operations:
Opcode | Meaning |
---|---|
iadd |
Removes the top two numeric values off of the stack and places their sum back on the stack. |
isub |
Removes the top two numeric values off of the stack and places their difference (top element subtracted from the next lower element) back on the stack. |
imul |
Removes the top two numeric values off of the stack and places their product back on the stack. |
idiv |
Removes the top two numeric values off of the stack, divides the next lower element by the topmost element, and places the result back on the stack. |
irem |
Removes the top two numeric values off of the stack, divides the next lower element by the topmost element, and places the remainder of the integer division back on the stack. |
ineg |
Removes the top numeric value off of the stack and places its negation back on the stack. |
pop |
Removes the top value off the stack and discards it. |
dup |
Duplicates the top element of the stack by pushing another copy of it. |
swap |
Exchanges the top two elements on the stack. |
iload num |
Pushes the contents of local variable num (where num is a number from 0-25) onto the stack. |
istore num |
Removes the top value off of the stack and stores it in local variable num (where num is a number from 0-25). |
iconst val |
Pushes the literal value val (which can be any integer) onto the stack. |
ireturn |
Returns the top element of the stack as the final value of an expression. |
Computing the "value" of an expression then turns into the process of "generating" the correct instructions for evaluating the expression. For example, consider this expression:
2 + 57 * 3
This expression can be evaluated this way:
// 2 + 57 * 3 iconst 2 iconst 57 iconst 3 imul iadd ireturn
Here is an example using variables and assignment:
X = 2 * A
The corresponding translation is:
// X = 2 * A iconst 2 iload 0 imul dup istore 23 ireturnIn this case, each variable name is mapped to a local variable number (A = 0, B = 1, ... X = 23, Y = 24, Z = 25). The instructions above load the constant 2 onto the stack, push the contents of A onto the stack, and then multiply these values. The result is then duplicated. One copy is stored in X while the other becomes the return result of the expression.
As you may gather from the examples above, every expression
"translation" for each valid expression should end with
ireturn
. Further, use a blank line to separate
translations (i.e., to separate out the "results" produced for each
incoming expression).
For invalid expressions, the first "//" line echoing the expression should instead be followed by an appropriate error message:
Expression contains invalid
token(s).
"
8 +
* 9
), print the error message: "Incorrect expression
syntax.
"
Submitting Your Program |
Your Pascal implementation is to be organized in a single file. All documentation and identifying information should be placed in comments within the single source file. The comments at the beginning of the file should identify the assignment and give your full name. Every Pascal procedure/function should be preceded by comments explaining its purpose, calling sequence, and implementation.
Your program will be submitted electronically through the Curator for automatic grading against a randomly generated test suite. To submit your program, login to the Curator using your PID and password. Be sure to select the 91312-CS 3304 Edwards 2:30-3:45 MW section when logging in. Click on "Submit", choose Pascal1 from the project drop-down list, click "Browse" to specify your solution, and then click "Upload."
In addition, you must also turn in a printed version of your program source in class according to the rules specified in the syllabus, which also describes the late policy. Your hardcopy printout must match the highest-scoring submission sent to the Curator earliest. In other words, you may not submit your program until it works, go back and add comments and documentation, and then make a final submission of the printable version of your program. Once you receive full credit from the Curator on a submission, that is the version you must print and hand in.
Home | Notes | Languages | Programs | Homework |