^CSE2304^
Pracs 1(A) and 1(B), CSE2304, CSSE, Monash, Semester 1, 2004
The [on-line] versions of the prac's may
include [links], corrections and supplementary material and
are to be taken as the reference documents.
Check the on-line material regularly.
Candidate:
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 under the [prac' guide],
[on C and code modularity], [missed pracs]
and [plagiarism] links on the
[home page].
It is better to have a program that
does only part of the prac' 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.
Prac's are 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.
NB.
Remember that, from prac1,
each week's prac' groups are set their own specific problems.
Make sure that you do the correct problem for your prac'!
You will get zero marks if you solve the wrong problem.
The exam, and the prac' 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:
Preparing prac's in advance,
revision of trees (here parse-trees) & recursion,
modifying & extending code written by someone else.
(The operations discussed might be useful in an optimizing compiler.)
You are advised to write code to modify
the tree produced by the parser
once the tree is complete, rather than to modify
the tree during its construction.
Prac 1(A), week 3, 15-19 March 2004
- There are several files in
[..../tildeProgLang/C/Tree/].
Some of these files make a parser for simple
arithmetic expressions, e.g.
- a+b*c
| |c---------|
|*---------|
| |b---------|
+---------|
|a---------|
|
- You must modify the data-structure and the code to:
- Give each node in the parse-tree a unique number, e.g.
| |3c---------|
|4*---------|
| |2b---------|
5+---------|
|1a---------|
|
(It does not matter what number a node has
provided that the number is unique.
You may assume that two digits will be sufficient when printing
a node number.)
- Find common sub-expressions, if any, and for
each repeated sub-expression set a pointer to
the sub-tree of the first occurrence of the sub-expression.
Cause the print routine to print out the number of the
pointed-to sub-tree in such cases, e.g.
- a+b+(a+b)/(a+b)-b
|-->2
5----------|
|
| | |-->3
| |6/---------|
| | |-->3
| |
|4+---------|
| | |2b---------|
| |3+---------|
| | |1a---------|
|
- NB. "Repeated sub-expression" means an exact match
of two sub-parse-trees; e.g.
do not try to treat <exp1>*<exp2> as equivalent
to <exp2>*<exp1>, say.
Note that two "complex" subtrees match
if they have the same top operator
and if their corresponding subtrees match.
Marking
Depending on understanding and quality of solution, stage 1 -->3 or 4 marks.
Depending on understanding and quality of solution, stage 2 -->5 or 6 marks.
Prac 1(B), week 4, 22-26 March 2004
- There are several files in
[..../tildeProgLang/C/Tree/].
Some of these files make a parser for simple
arithmetic expressions, e.g.
- a+b*c
| |c---------|
|*---------|
| |b---------|
+---------|
|a---------|
|
- You must modify the code as follows:
-
Some binary operators, such as `+' and `*'
are associative, e.g. a+(b+c) = (a+b)+c, etc..
- Given an expression such as a+(b*(c*d)+e)
the original parser constructs
| |e---------|
|+---------|
| | | |d---------|
| | |*---------|
| | | |c---------|
| |*---------|
| | |b---------|
+---------|
|a---------|
|
Instead make it return the equivalent "left-most" tree for such cases
|e---------|
+---------|
| | |d---------|
| |*---------|
| | | |c---------|
| | |*---------|
| | | |b---------|
|+---------|
| |a---------|
|
- Every sub-tree having a "crown" made up
a single repeated associative operator, <op>,
must be transformed in this way, e.g.
-
.|-------tn
. |
. | etc.
......<op> |
. |-------t2
. |
.|-------t1
|
(where the sub-sub-trees
t1, t2, ..., tn-1, tn do not have <op> at the top)
|
must become
|-------tn
......<op>------|
| |------tn-1
|<op>------|
. .
. etc.
. .
| | |---------t2
| |<op>-----|
| | |---------t1
|
Marking
Depending on understanding and quality of solution, can handle at least one grouping such as
<e1>+(<e2>+(<e3>+<e4>))
-->3 or 4 marks.
Depending on understanding and quality of solution, can handle any number of groupings
-->5 or 6 marks.
© 2004 L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & IRIX)", charset=iso-8859-1