^CSE2304/2006 ^

Practical 1, CSE2304, Monash, Semester 1, 2006

The practical problems are available online via the unit home page for this year. The [on-line] practical problems may include [links], corrections and supplementary material and are to be taken as the reference documents. Check the on-line material regularly.

Class: You must prepare your solution to this programming exercise in advance (a 6pt subject => 12-hours work per week, every week). The designated platform, on which your solution must be demonstrated and on which it will be marked, is the `gcc' compiler running on `Linux'. If you develop a solution on another platform, it is your responsibility to ensure that it works correctly on the designated platform. Read the information on the practical-work guide, C and code modularity, missed practicals and plagiarism on the unit [home page]. It is generally better to have a program that solves only part of the problem but compiles and runs rather than to have a more complex program that crashes or, even worse, does not compile. So keep copies of old working partial solutions.
    Practical work is marked on the performance of your program and also on your understanding of the program. I.e. Perfect program with zero understanding => zero marks! "Forgetting" is not an acceptable explanation for lack of understanding. Unless otherwise noted, you must write all the code yourself, and may not use any external library routines, the usual I/O (e.g. printf) and mathematical (e.g. log) routines excepted.
    The exam, and the practical work, are both hurdles (half-marks) for the subject. If you fail one, or the other, or both, the highest mark that you can get for the subject is 44%(N).

Demonstrators are not obliged to mark programs that do not compile or that crash. Time allowing, they will try to help in tracking down errors, but they are not required to mark programs in such a state, particularly those that do not compile. Therefore keep backup copies of working partial-solutions (also see above).

Objectives: This prac is to develop skills in trees, recursion, traversal and other tree operations. It uses trees in a new problem: compiling machine code from the parse-tree of an arithmetic expression. Note that parsing is not examinable in this unit which is why you have been given an existing parser. It is also an important exercise, very typical in industry, to modify or extend an existing program rather than to write a new program from scratch.

Practical 1, week 4, begins 20 March

In [..../tildeProgLang/C/Tree/] are several files that make up a parser for arithmetic expressions. There are also other routines which may or may not be useful to you.

If the program is compiled as prac1.out, it can be used thus:
ne> prac1.out
Simple Parser Demonstration, L.Allison, Monash University, .au
Type simple expression e.g. a+b*c
x+y*z 
          |          |z---------|
          |*---------|
          |          |y---------|
+---------|
          |x---------|
prefix:  + x * y z
infix:   x + y * z
postfix: x y z * +
The root of the tree (+) is on the left because this orientation takes up less space.
 
Here are the arithmetic machine instructions of a simple computer: 
<reg>  = <addr>     i.e. load contents of address into <reg>
<reg>  = <lit>      i.e. load literal
<addr> = <reg>      i.e. store
<reg>  = <reg'>     register to register transfer
<reg> += <addr>     similarly -=, *=, /=
<reg> += <lit>      similarly -=, *=, /=
<reg> += <reg'>     similarly -=, *=, /=
where
<reg>   can be R0, R1, R2, ...
<lit>   can be 1, -17, 103, etc..
<addr>   can be a symbolic name such as x, y, fred, etc..
E.g. the expression above can be compiled as
R0 = x
R1 = y
R1 *= z
R0 += R1   --result left in R0
You will notice that the first instruction corresponds to the left sub-tree, and the second and third to the right sub-tree. This suggests that a variation on tree-traversal can be used to compile code for an arbitrary expression.
Also note that the expression p*q+r, which also contains three variables and two operators, can be compiled to just three machine instructions.
 
Problem:
  1. Do not modify the parser.
  2. Write a new routine 'compile(Tree t)', in a new file 'compile.c' of its own, which prints the machine instructions for a given parse Tree t.
  3. Add a call to your 'compile(Tree t)' in the driver main program. (Delete the calls to the three traversal routines.)

Marking

Does not compile, crashes, or makes no real attempt at generating machine instructions --> 2/6 or less.
Appropriate tree-traversal strategy for generating machine instructions --> 3/6 marks.
Works correctly on simple expressions such as 'anne-bill+carol-dave' --> 4/6 to 5/6 marks.
Works correctly for arbitrary expressions, particularly with complex right sub-trees, with evidence of appropriate testing --> 6/6 marks.
These marks are conditional on elegant, general code and full understanding of your solution.

© 2006 L. Allison, Faculty of Information Technology (Clayton), was School of Computer Science and Software Engineering, Monash University, Australia 3800.
Created with "vi (Linux & IRIX)",   charset=iso-8859-1

More examples

x x+y x*y+z x+y+z x+y*z x*y+z*w 
R0 = x

R0 = x
R0 += y

R0 = x
R0 *= y
R0 += z

R0 = x
R0 += y
R0 += z
R0 = x 
R1 = y
R1 *= z
R0 += R1 
R0 = x
R0 *= y

R1 = z
R1 *= w
R0 += R1