Prac 1, CSE2304, CSSE, Monash, Semester 1, 2002

Group A: week 3, 18-22 March,
Group B: week 4, 25-28 March (Good Friday lab' 29th --> 12 April)

Candidate: You must prepare your solution to this programming exercise in advance. 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 under the [prac' guide], [on C and code modularity] and [plagiarism] links on the subject home page.

Groups: Note that different prac'-groups might be set different tasks. Make sure that you do your task. You will get zero marks if you solve the wrong problem.

The objectives of this exercise are to

1. experience adding-to and/or modifying an existing program, which is more common than writing a new program from scratch,
2. renew your familiarity with the tree abstract data-type, and
3. design a new tree-processing algorithm for an unfamiliar problem.

The task is to generate assembly-code for a hypothetical target computer from `well-formed formulae' (WFF) in propositional logic (boolean algebra). This might form a small part of a compiler. There is an existing program in [.../~lloyd/tildeProgLang/C/Wff/] which reads a WFF, parses it, and builds a parse-tree. Take a copy of the program files, compile the program, run it, read the code and understand it. You should not need to alter the existing code, apart from adding new routines of your own, and changing the main program to call them.

Task: Add new routines to the program to generate simple assembly-code (for your group's hypothetical computer) so that the assembly-code would calculate the value of the WFF and leave the result in register R0 when executed.

All: Your machine does not have an `implies' (=>) instruction, so all instances of   `<exp₁> => <exp₂>'   must first be transformed to   `not <exp₁> or <exp₂>'   in the parse-tree.

The task can be performed by one or more new routines that traverse the WFF's parse-tree in a suitable way and generate the assembly-code. For simplicity you may assume that your target computer has an unlimited number of registers, but do not waste registers.

Group A

Your hypothetical target computer has instructions of the following forms:

LOAD <register_i> <operand>

<op> <register_i> <register_j> <register_k>     where <op> is one of `AND', `OR',

the effect is that <register_i> := <register_j> <op> <register_k>

NOT <register_i> <register_j>

the effect is that <register_i> := not <register_j>

where <register_i> (etc.) is one of R0, R1, R2, R3, ...etc. and <operand> is an identifier such as `x', `fred', etc.

Group B

Your hypothetical target computer has instructions of the following forms:

LOAD <register_i> <operand>

<op> <register_i> <operand>     where <op> is one of `AND', `OR'

the effect is <register_i> := <register_i> <op> <operand>

<op> <register_i> <register_j>     where <op> is one of `AND', `OR'

the effect is <register_i> := <register_i> <op> <register_j>

NOT <register_i>

the effect is that <register_i> := not <register_i>

where <register_i> (etc.) is one of R0, R1, R2, R3, ...etc. and <operand> is an identifier such as `x', `fred', etc.

e.g.

LOAD R0 a
LOAD R1 b
OR R0 R0 R1

LOAD R0 a
OR   R0 b

LOAD R0 a
LOAD R1 b
AND  R0 R0 R1
LOAD R1 c
LOAD R2 d
AND  R1 R1 R2
NOT  R1 R1
OR   R0 R0 R1

LOAD R0 a
AND  R0 b
LOAD R1 c
AND  R1 d
NOT  R1
OR   R0 R1

LOAD R0 a
LOAD R1 b
LOAD R2 c
AND  R1 R1 R2
AND  R0 R0 R1

LOAD R0 a
LOAD R1 b
AND  R2* c
AND  R0 R1

LOAD R0 a
AND  R0 b
AND  R0 c

LOAD R0 e1
LOAD R1 a
AND  R0 R0 R1
LOAD R1 e2
LOAD R2 a
AND  R1 R1 R2
OR   R0 R0 R1

LOAD R0 e1
LOAD R1 a
AND  R0 R0 R1
LOAD R2 e2
AND  R2 R2 R1
OR   R0 R0 R2

LOAD R0 e1
AND  R0 a
LOAD R1 e2
AND  R1 a
OR   R0 R1

NB. It is not necessary to generate the "harder", optimized code which is shown for interest.

Assessment (out of 6)

appropriate parse-tree traversal strategy	2
transforms all instances of implies (=>)	1
generates correct code	3

NB. If submission fails to compile then less than half-marks, perhaps much less. If fails to run correctly on straightforward data then less than 60%. Candidate must demonstrate full understanding of submitted program.