This extended prac is designed to take you the best part of two weeks. Hand in your solutions before lunch time on Monday 1 November, correctly packaged in a transparent folder with your cover sheets. Since the practical will have been done on a group basis, please hand in one copy of the cover sheet for each member of the group. Your solutions will be returned to you as soon as possible after that.
The reason for requiring all submissions by 1 November is to free you up during swot week to prepare for the final examinations. I shall try to get the marking done as soon as possible after that.
In this practical you are to
You will need this prac sheet and your text book. As usual, copies of the prac sheet are also available at http://www.cs.ru.ac.za/CSc301/Translators/trans.htm.
When you have completed this practical you should understand
Hopefully after doing these exercises (and studying the attributed grammar and the various other support modules carefully) you will find you have learned a lot more about compilers and programming languages than you ever did before (and, I suspect, a lot more than undergraduates at any other university in this country). I also hope that you will have begun to appreciate how useful it is to be able to base a really large and successful project on a clear formalism - namely the use of attributed context-free grammars - and will have learned to appreciate the use of sophisticated tools like Coco/R.
By the hand-in date you are required to hand in, besides the cover sheets (one per group member):
I do NOT require listings of any Java or C# code produced by Coco/R.
Keep the prac sheet and your solutions until the end of the semester. Check carefully that your mark has been entered into the Departmental Records.
You are referred to the rules for practical submission which are clearly stated on page 15 of our Departmental Handbook. However, for this course pracs must be posted in the "hand-in" box outside the laboratory and not given to demonstrators.
A rule not stated there, but which should be obvious, is that you are not allowed to hand in another student's work as your own. Attempts to do this will result in (at best) a mark of zero and (at worst) severe disciplinary action and the loss of your DP. You are allowed - even encouraged - to work and study with other students, but if you do this you are asked to acknowledge that you have done so. You are expected to be familiar with the University Policy on Plagiarism, which you can consult at:
http://www.scifac.ru.ac.za/plag.htm
The tasks are presented below in an order which, if followed, should make the practical an enjoyable and enriching experience. Please do not try to leave everything to the last few hours, or you will come horribly short. You must work consistently, and with a view to getting an overview of the entire project, as the various components and tasks all interact in ways that will probably not at first be apparent. Please take the opportunity of coming to consult with me at any stage if you are in doubt as how best to continue. By all means experiment in other ways and with other extensions if you feel so inclined.
This version of Parva uses a grammar for expressions similar to that in Java and C# and in the grammar you used in Practical 24. It has been restricted so as not to include functions. This means that there will be no practical work set on chapter 14 of the text. Because of the timing of our courses this is unavoidable, if highly regrettable. You should be warned that some of the material of that chapter may be "examinable".
You are also advised that it is in your best interests to take this opportunity of really studying the code in the Parva grammar and its support files. The exercises have been designed to try to force you to do that, but it is always tempting just to guess and to hack. With a program of this size that often leads to wasting more time than it saves. Finally, remember the advice given in an earlier lecture:
Keep it as simple as you can, but no simpler.
Throughout this project you will need to ensure that the features you explore are correctly implemented. This means that you will have to get a feel for understanding code sequences produced by the compiler. The best way to do this is usually to write some very minimal programs, that do not necessarily do anything useful, but simply have one, or maybe two or three statements, the object code for which is easily predicted and understood.
When the Parva compiler has finished compiling a program, say SILLY.PAV, you will find that it creates a file SILLY.COD in which the stack machine assembler code appears. Studying this is often very enlightening.
Useful test programs are small ones like the following. There are some specimen test programs in the kit, but these are deliberately incomplete, wrong in places, too large in some cases and so on. Get a feel for developing some of your own.
$D+ // Turn on debugging mode
void main (void) {
int i;
int[] List = new int[10];
while (true) { // infinite loop, can generate an index error
read(i);
List[i] = 100;
}
}
The debugging pragma
It is useful when writing a compiler to be able to produce debugging output - but sometimes this just clutters up a production quality compiler. The Parva.atg grammar makes use of the PRAGMAS option of Coco/R (see text, page 128) to allow pragmas like those shown to have the desired effect.
$D+ /* Turn debugging mode on */
$D- /* Turn debugging mode off */
There are several files that you need, zipped up in the file PRAC25.ZIP (Java) or PRAC25C.ZIP (C#).
J:
md prac25
cd prac25
copy i:\csc301\trans\prac25.zip
unzip prac25.zip
You will find the executable version of Coco/R and batch files for running it, frame files, and various sample data, code and grammars, contained in files with extensions like
*.ATG, *.PAV
We have already commented on the $D+ pragma. At present it is only used to request the printout of a symbol table. How would you change the system so that one would have to use a similar pragma or command line option if one wanted to obtain the assembler code file - so that the ".COD" file of assembler code would only be produced when it is really needed?
$C+ /* Request that the .COD file be produced */
$C- /* Request that the .COD file not be produced */
Another useful (run-time) debugging aid is the undocumented stackdump statement. Compilation of this is also controlled by the $D pragma (in other words, the stack dumping code is only generated when in debug mode - much of the time you are testing your compiler you will probably be working in "debugging" mode, I expect).
Hint: This addition is almost trivially easy. You will also need to look at (and probably modify) the Parva.frame file, which is used as the basis for constructing the compiler proper (see page 139).
If, like me, you first learned programming in languages other than Java, you may persist in making silly mistakes when writing Parva programs. For example, Pascal programmers easily confuse the roles played by ==, != and = with the similar operators in Pascal denoted by =, <> and :=, and are prone to introduce words like then into IfStatements, giving rise to code like
if (a = b) then c := d;
if (x <> y) then p := q;
instead of
if (a == b) c = d;
if (x != y) p = q;
Can you think of (and implement) ways to handle these errors sympathetically - that is to say, to report them but then to "recover" from them without further ado?
(Confusing = with == in Boolean expressions is something C, C++ and Java programs can easily do as well. It is particularly nasty in C/C++, where a perfectly legal statement like
if (a = b) x = y;
does not compare a and b, but assigns b to a, as you probably know).
In Parva, the key word const is not used in the sense that it is used in C# and the word final is used in Java, namely as a modifier in a variable declaration that indicates that when a variable is declared it can be given a value which can then not be modified later. If you check the grammar for Parva you will come across the productions
Statement = Block | ConstDeclarations | VarDeclarations | ...
ConstDeclarations = "const" OneConst { "," OneConst } ";" .
OneConst = identifier "=" Constant .
Constant = number | charLit | "true" | "false" | "null" .
VarDeclarations = Type OneVar { "," OneVar } ";" .
OneVar = identifier [ "=" Expression ] .
which will not handle code of the form some people might prefer, like
const int max = 2;
int i = 5;
const int iPlusMax = i + max;
const int[] list = new int[iPlusMax];
Hint: there may be side effects of making the "obvious" changes which you might not at first realize.
Suppose we extend Parva to adopt an idea used in Pascal, where a statement like
write (X : 5, X + A : 12, X - Y : 2 * N);
will write the values of X, X+A and X-Y in fields of widths 5, 12 and 2*N respectively.
Ho Hum. Things are hotting up, and there is a sting in the tail. Statements like this
write (3 + 4, A < B);
should produce numeric output for the first element, and Boolean output for the second one.
But a statement like this
write (3 + 4 : A < B)
should not be allowed, because the (optional) formatting expression is meaningless unless it is numeric.
Hint: This is best handled by modifying the PRNI and PRNB actions in the interpreter. Once you have thought about it you will see that the extension is very easily implemented.
A very easy one: add the Pascal-like Repeat loop to Parva, as exemplified by
repeat a = b; c = c + 10; until (c > 100);
At last! Let's really make Parva useful and turn it into Parva++ by adding the increment and decrement statement forms exemplified by
int parva;
int [] list = new int[10];
...
parva++;
list[10]--;
Suggestions for doing this - specifically by introducing new operations into the PVM - are made in section 13.5.1 of the text. Remember that only integer variables can be handled in this way. The PVM operations are already handled for you in the interpreter, just to make the upgrade easy.
Add an else option to the IfStatement. Oh, yes, it is trivial to add it to the grammar. But be careful. Some IfStatements will have else parts, others may not, and the code generator has to be able to produce the correct code for whatever form is actually to be compiled. The following silly examples are all valid.
if (a == 1) { c = d; }
if (a == 1) {}
if (a == 1) {} else {}
if (a == 1) {} else { b = 1; }
In an earlier practical we suggested that an IfStatement might incorporate optional elsif clauses - the grammar for this simply being on the lines of
IfStatement = "if" "(" Condition ")" Statement
{ "elsif" "(" Condition ")" Statement }
[ "else" Statement ] .
Implement this extension (make sure all the branches are correctly set up).
The BreakStatement is syntactically simple, but takes a bit of thought. Give it some! The points to watch are that breaks can only come inside loops, there might be several break statements inside a single loop, and loops can be nested inside one another.
The GoToStatement is also syntactically simple. If we allow statements to be labelled with simple integer labels we will be able to write real fun code like
i = 0;
10 if (i > 10) goto 20;
i++;
goto 10;
20 write("loop finished");
Extend Parva to allow the GoToStatement. To do this you will need to construct a label table of some sort. To help you in this regard, the kit contains a support class that does exactly that. You might like to modify the Label class and the code generation to make use of the newly discovered Duff's Device, and to take a careful look at Chapter 11.5.
Health warning - this one will require a lot of careful thought, although once you have given it that thought, the solution is quite simple.
Way back in Practical 20 we added the specialized opcodes LDL and STL to the PVM. They are still there in the version of the PVM emulator supplied with the kit. Seems a shame not to use them, so modify the code generation in the compiler to do so.