Programming Assignment 2 - Equation Optimization

Advanced Programming II, Spring 2002

Due Date

This assignment is due by 2:00 p.m. on Thursday, 19 February.

See the assignment turn-in page (last modified on 22 January 2002) for instructions on turning in your assignment.

Compilers are principally responsible for translating a source program into a form that can be executed. However, compilers also have many other duties. One of these important other duties, known as optimization, is making sure the executable version of the source program runs as efficiently as possible.

There is a huge number of optimizations a compiler can use. Constant folding and compile-time evaluation are two simple but important optimizations frequently used in compilers.

Constant folding

If a variable is known to contain a constant value at compile time, then references to the variable can be replaced by the constant value, which eliminates the need to access the variable at run time. This is known as constant folding.

For example, given the statements


pi = 3.1415

circumference = 2*pi*radius

the value represented by the variable pi is known to be a constant in the second statement. This means the statements


pi = 3.1415

circumference = 2*3.1415*radius

are equivalent in behavior to the previous statements and are more efficient than the previous statements because they don't need to access the variable pi.

Compile-time evaluation

If the result of evaluating an expression is known at compile time, then the expression can be replaced by its result, eliminating the need to evaluate the expression at execution time. This optimization is known as compile-time evaluation.

To continue the previous example, the statements


pi = 3.1415

circumference = 2*3.1415*radius

contain the expression 2*3.1415, which can be evaluated at compile time to produce the statements


pi = 3.1415

circumference = 6.283*radius

which are equivalent in behavior to the previous statements and are more efficient than the previous statements because they don't need to compute the expression 2*3.1415 at execution time.

Compile-time evaluation can also depend on the arithmetic properties. For example, even if the contents of variable a are unknown, the result of the expression a - a is 0, and the statement


x = b*(a - a)

can be optimized to the statement


x = b*0

using compile-time evaluation. This statement can be further optimized. By the rules of multiplication, anything times zero is zero; even though the contents of the variable b are unknown, the product b*0 is equal to zero, and the previous statement can be optimized to the equivalent but more efficient statement


x = 0

The Problem

Write a program that reads from standard-in statement blocks and writes to standard-out the optimized version of the statement blocks. The program should apply constant folding and compile-time evaluation to the statement blocks. The output statement blocks should be as efficient as possible; it should not be possible to further optimize the output statement blocks.

Input

Input consists of a sequence of statement blocks. Each statement block is separated from the next statement block by a blank line (a line containing nothing but a new line); blank lines in excess of those needed to separate statement blocks should be ignored.

A statement block is a sequence of one or assignment statements; each line contains exactly one assignment statement. An assignment statement has the form

variable = expression

One or more blank characters (as defined by isspace() without newlines) will appear on either side of the equals sign.

An expression can have any of the following forms:

A variable name in the usual C++ syntax.
An integer in the usual C++ syntax for decimal integers.
An expression followed by an operator followed by an expression
expression operator expression
where operator is one of the binary operators +, -, *, /, %, <<, and >>. One or more blank characters will appear on either side of an operator.
A pair of parenthesis surrounding an expression,
( expression )
One or more blank characters will appear on both sides of both parenthesis.

Any equation set not following this syntax is syntactically incorrect.

Each statement block set is independent of the other statement blocks.

Equation Semantics

The operators have the same function as their C++ counterparts. You need not worry about exceptional conditions; you may assume that problems such as overflow and division by zero never occur. Because the only data type is integer, << and >> are always interpreted as bit-shift operators. All operators are left associative, just like their C++ counterparts. However, unlike their C++ counterparts, all operators have the same precedence. For example, the expression


1 + 2 * 3

is equivalent to the expression


( 1 + 2 ) * 3

not the expected


1 + ( 2 * 3 )

as it is in C++.

As indicated by the previous examples, parenthesis can be used to change the precedence of operators bracketed by the parenthesis. The expression bracketed by the parenthesis are evaluated before the expressions outside the parenthesis. Parenthesized expressions at the same level are left associative. For example, the expression


( i + i ) * ( j + j ) * ( k + k )

is equivalent to the expression


( ( i + i ) * ( j + j ) ) * ( k + k )

All variables used in a statement block are defined and initially contain an arbitrary value.

Output

The output should be in the same form as the input: a sequence of statement blocks equations separated by blank lines. Statement blocks should be output in the same order as input. If an input statement block contains syntactically incorrect statement, the output should contain a brief error message describing the problem.

Output statement blocks should be as efficient as possible; it should not be possible to perform further optimizations on output statement blocks.

Testing

I won't be providing any test cases for this problem; you're on your own.

This page last modified on 6 February 2002.