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

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:

• integers (operands)
• * / + - % (binary math operators)
• + and - (unary versions of both)
• Left and Right parentheses
• = (assignment operator)
• letters (26 individual variables)

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:

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
    ireturn

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:

• If one or more invalid token(s) appear in the expression, print the error message: "Expression contains invalid token(s)."

• If the expression is not syntactically correct (such as 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