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
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
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.
WFF | Group A | Group B | ||||
---|---|---|---|---|---|---|
a or b | LOAD R0 a LOAD R1 b OR R0 R0 R1 | LOAD R0 a OR R0 b | ||||
a and b or not(c and d) | 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 | ||||
a and (b and c) | LOAD R0 a LOAD R1 b LOAD R2 c AND R1 R1 R2 AND R0 R0 R1 |
| ||||
e1 and a or e2 and a (ignoring possible factoring) |
|
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.
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.