Problem 6: Compiler Optimizations

Background:

In this advanced day and age, compilers do a lot of work. One of the things compilers are expected to do is some sort of optimization. In this problem, you get to apply two such optimizations. The first is copy propagation, and the second is dead code elimination.

A copy statement is of the form f := g. In other words, a single variable is being assigned the value of another variable. No other statements are copies.

The Dragon Book (well, ok, it's real title is Compilers: Principles, Techniques and Tools by Aho, Sethi and Ullman. However, it's got a quick sketch of a dragon on the front, so everyone calls it the Dragon Book. It's even got an entry in the Jargon File) says this about copy propagation:

The idea behind the copy-propagation transformation is to use g for f wherever possible after the copy statement f:=g.

In other words, whenever f appears on the right hand side of an assignment, we put g in it's place. We can do this so long as g and f do *not* get assigned anywhere else (in compiler techno-babble that assignment is known as a "kill") Kills always take place *after* the statement. So, if given the statements:

f:=g
f:=f * 2;

We can replace f with g on the right hand side of statement 2 to get f:=g * 2. If you're wondering, copies like f:=g can arise because of other optimizations. We care about copy propagation because of the following:

Dead code elimination is the ability of the compiler to remove statements that it knows are `dead'. A statement is dead if it computes values that are never going to be used. For our purposes, dead code can only be copies whose left hand side is not used again (ie, because of copy propagation, the copy is now dead).

Copy propagation needs only be done with one pass through the code. Dead code elimination may have to be repeated multiple times to catch all the dead copies. Essentially, dead code elimination should be repeated until it finds nothing to remove.

Input:

In this problem, you will be given a small program and will have to output the program after copy propagation and dead code elimination have been applied. Each program will be no more than 50 lines. Each line will be no more than 80 characters, and will have exactly one statement. There will always be one program given to you. That program will be syntactically correct according to the rules below. There are no blank lines in the input. There may be an arbitrary amount of white space appearing on a line though.

We'll use the language SILLY as our programming language. In SILLY, there are no function calls, nor any declarations. Instead, all variables are single, lower case letters. Upper case letters are used for constants or operations. Assignment statements are of the form v:=val, where v is the variable and val is the value assigned to v. val can be any expression at all. The statement #val prints the value of the expression val out. val can be any legal SILLY expression. A `%' starts the beginning of a comment. Comments can appear anywhere in the code and always extend to the end of line (ie, they don't cross lines).

Statements in SILLY may or may not end in a ;. For simplicity, we'll assume that all copy statements do not have a ; at the end.

Output:

The output is the program after copy propagation and dead code elimination have been performed. No blank lines should appear in the output. All spacing should be preserved from the input. (ie, if two spaces appear after an := and that statement makes it through the optimization, then two spaces should appear after the := in the output). All comments should also appear unaltered.

Sample Input:

a   :=     c + 10 % blah blah blah
c := a MOD 10
z := c
c := z MOD 1506
#z
t := z
z := t * 10 + 30 * 15 - 30040 / 10.3;
c:= 10

Sample Output:

a   :=     c + 10 % blah blah blah
c := a MOD 10
z := c
c := c MOD 1506
#z
z := z * 10 + 30 * 15 - 30040 / 10.3;
c:= 10