Home  |   Notes  |   Languages  |   Programs  |   Homework
Program Assignment 1

100 Points
Due: 9/26/01 at the start of class


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:

White space may be used for clarity or to separate tokens in expressions, but no white space is required within an expression.

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:

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

Here is an example using variables and assignment:

    X = 2 * A

The corresponding translation is:

    // X = 2 * A
    iconst 2
    iload 0
    istore 23

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

 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

copyright © 2001 Virginia Tech, ALL RIGHTS RESERVED
Last modified: November 26, 2001, 11:15:04 EST, by Stephen H. Edwards <edwards@cs.vt.edu>