Hand in this prac sheet before lunch time on your next practical day, correctly packaged in a transparent folder with your solutions and the "cover sheets". Please do NOT come to a practical and spend the first hour printing or completing solutions from the previous week's exercises. 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. These will be returned to you in due course, signed by the marker.
Ja, well, no, fine. All you folks who thought this was a bit of a jorl so far, think again. 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
This week you are required to hand in, besides the cover sheets (one per group member):
I do NOT require listings of any Java 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 13 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
There are several files that you need, zipped up this week in the file PRAC24.ZIP.
l:
md prac24
cd prac24
copy i:\csc301\trans\prac24.zip
unzip prac24.zip
This will create several other directories "below" the prac24 directory:
L:\prac24
L:\prac24\coco
L:\prac24\frames
L:\prac24\Library
L:\prac24\Assem
L:\prac24\Parva
containing the Java classes for the Java version of the Coco/R compiler generator. You will also find various sample programs and grammars, contained in files with extensions like
*.ATG, *.PAV, *.TXT *.BAD
In the kit you will find CALC.ATG. This is an attributed grammar for a simple four function calculator that can store values in any of 26 memory locations, inspiringly named A through Z.
import Library.*;
import java.util.*;
COMPILER Calc $CN
/* Simple four function calculator with 26 memory cells
P.D. Terry, Rhodes University, 2003 */
static double[] mem = new double[26];
CHARACTERS
digit = "0123456789" .
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" .
IGNORE CHR(1) .. CHR(31)
TOKENS
Number = digit { digit } [ "." { digit } ] .
Variable = letter .
PRODUCTIONS
Calc (. int index = 0; double value = 0.0;
for (int i = 0; i < 26; i++) mem[i] = 0.0; .)
= { Variable (. index = token.str.charAt(0) - 'A'; .)
"=" Expression<^value> (. mem[index] = value;
IO.writeLine(value); .)
} EOF .
Expression<^double expVal> (. double expVal1 = 0.0; .)
= Term<^expVal>
{ "+" Term<^expVal1> (. expVal += expVal1; .)
| "-" Term<^expVal1> (. expVal -= expVal1; .)
} .
Term<^double termVal> (. double termVal1 = 0.0; .)
= Factor<^termVal>
{ "*" Factor<^termVal1> (. termVal *= termVal1; .)
| "/" Factor<^termVal1> (. termVal /= termVal1; .)
} .
Factor<^double factVal> (. factVal = 0.0; .)
= Number (. try {
factVal = Float.parseFloat(token.str);
} catch (NumberFormatException e) {
factVal = 0; SemError("number out of range");
} .)
| Variable (. int index = token.str.charAt(0) - 'A';
factVal = mem[index]; .)
| "(" Expression<^factVal> ")" .
END Calc.
Use Coco/R to generate and then compile source for a complete calculator. You do this most simply by
cmake CALC
A command like
crun Calc calc.txt
will run the program Calc and try to parse the file calc.txt, sending error messages to the screen. Giving the command in the form
crun Calc calc.bad -L
will send an error listing to the file listing.txt, which might be more convenient. Try this out.
Study the grammar carefully. If there are any aspects of it that you do not understand, please ask one of the tutors to explain them.
Make the following extensions to the system:
Calc = { Variable "=" Expression | "print" Expression } EOF .
that is, introduce two "statement" forms, one that assigns (without displaying the answer) and one that prints the value of an expression (without assigning it to a variable).
Test your system out thoroughly - give it both correct and incorrect data.
The file TRAINS.ATG contains a simple grammar describing trains, as discussed in prac 21, though devoid of the "safety" regulations, which gave you such trouble a few weeks back. The file TRAINS.TXT has some simple train patterns.
COMPILER Trains $CN
/* Grammar for simple railway trains
P.D. Terry, Rhodes University, 2003 */
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
COMMENTS FROM "(*" TO "*)" NESTED
PRODUCTIONS
Trains = { OneTrain } EOF .
OneTrain = LocoPart [ GoodsPart ] HumanPart SYNC "." .
LocoPart = "loco" { "loco" } .
GoodsPart = Truck { Truck } .
HumanPart = "guard" | { "coach" } "brake" .
Truck = "coal" | "open" | "cattle" | "fuel" .
END Trains.
In Prac 21 you were at pains to check the regulations syntactically. It may be easier sometimes to check quasi- syntactic features semantically. This is a good example. Without making any significant changes to the grammar, go on to add actions and attributes to the grammar so that it will
Hints: For a problem as simple as this one does not really need to parameterise the parsing routines - it will suffice to store the "semantic state" in a few static fields in the parser class, which can be introduced at the start of the ATG file. Take particular care with the way in which you add the actions - it is easy to put them in slightly wrong places, and then to wonder why the system does not give the results you expect. You may wish to explore the use of the SemError and Warning facilities (see page 165) for placing error and other messages in the listing file at the point where you detect that safety regulations have been disobeyed, or where you want to report on the numbers of locos, trucks and coaches.
On pages 181 - 185 of the text you will find a discussion of how Coco/R can be used to write a simple assembler for PVM code that allows for named labels to be introduced and then used as the targets of branch instructions (don't you wish you had been able to use this when you did Practical 20?)
The code for such a system is supplied in the prac kit. This includes an interpreter that is invoked after successful assembly and which handles the extended opcode set from Prac 20. You can build it with the command
cmake Assem
A command like
crun Assem fact1.pvm
will then execute the assembler/interpreter. (There are several simple PVM programs in the prac kit).
Extend this system so that it will allow you to
Hints: Before trying to hack out a solution, spend some time studying the grammar as supplied and the source of the support classes that you can find in the Assem\Table.java file.
This system makes us of the ArrayList class, a useful one for building simple lists of objects of any convenient type in an array-like structure which will adjust its size as appropriate. The appendix at the end of this prac sheet demonstrates another simple application using ArrayList. It is suggested that you use the ArrayList class to construct the list of identifiers found in the programme.
You can incorporate the necessary code into the ATG file as the "arbitrary text" that precedes the scanner specification, rather like the way in which support code has been added to the calculator grammar in task 1.
Do test your system out thoroughly. There are simple variations on the factorial program that you met in an earlier prac in files named fact1.pvm through fact4.pvm, and it is easy to invent further examples of your own.
You can limit your escape sequence handling to \n \t \f \" and \'.
Something to think about (you do not have to code it up): Suppose someone were to suggest to you that a more sophisticated assembler system might try automatically to substitute one-word opcodes like LDC_3 for the two- word opcodes like LDC 3 that a user might have used. Would this be a good idea? How could it be implemented?
In the prac kit you will find (in Parva.atg) an unattributed grammar for the Parva language as you extended it in Prac 21, and some simple Parva pograms with names like voter.pav and voter.bad. You can build a Parva parser quite easily and try it out immediately.
A cross reference generator for Parva is a program that analyses a Parva program and prints a list of the identifiers in it, along with the line numbers where the identifiers were found. A cross reference listing can be extremely useful when you are asked to maintain very big programs. Such a listing, for the voter.pav program in the kit, might look like this (where negative numbes denote the lines where the identifier was "declared"):
main -1 votingAge -2 8 age -3 6 7 8 11 15 eligible -3 11 12 12 13 17 17 total -3 13 13 17 allEligible -4 9 9 18 voters -5 11 13 canVote -8 9 10
Modify the Parva grammar and provide the necessary support routines (essentially add a simple symbol table handler) to be able to generate such a listing.
Hints: Hopefully this will turn out to be a lot easier than it at first appears. You will notice that the Parva grammar has been organised so that all the references to identifiers are directed through a non-terminal Ident, so with a bit of thought you should be able to see that there are in fact very few places where the grammar has to be attributed. When you have thought about the implications of that hint, check out your ideas with a tutor, so as not to spend fruitless hours writing far more code than you need.
You will, however, have to develop a symbol table handler. This can make use of the ArrayList class in two ways. You will need a list of records of the identifiers. For each of these records you will also need a list of records of the line numbers. Classes like the following might be useful ones for this purpose:
class LineRef {
public int lineNo;
public LineRef(int lineNo) {
this.lineNo = lineNo;
}
}
class Entry {
public String name;
public ArrayList refs;
public Entry(String name) {
this.name = name;
this.refs = new ArrayList();
}
}
and your Table class (a skeleton of which is supplied in the file Parva\Table.java) could be developed from the following ideas:
class Table {
public static void clearTable() {
// Reset the table
public static void addRef(String name, boolean declared, int lineRef) {
// Enters ident if not already there, adds another line reference
public static void printTable() {
// Prints out all references in the table
}
You will be relieved to hear that each of these methods can be implemented in only a few lines of code, provided you think clearly about what you are doing.
The following program shows how the ArrayList class can be used to construct a list of records of people's names and ages, and then to display this list and interrogate it. Note the use of casting operations!
import Library.*;
import java.util.*;
class ShowArrayList {
// Demonstrate simple application of the ArrayList class
static class Entry {
public String name;
public int age; // other fields could be added
public Entry(String name, int age) { // constructor
this.name = name;
this.age = age;
}
}
static ArrayList list = new ArrayList(); // global for simplicity here!
public static int position(String name) {
// Finds position of entry with search key name in list, or -1 if not found
int i = list.size() - 1; // index of last entry
while (i >= 0 && // short-circuit protection
!name.equals(((Entry)list.get(i)).name)) // must cast before extracting field
i--; // will reach -1 if no match
return i;
}
public static void main (String[] args) {
// Build a list of people's names and ages
do {
String name = IO.readWord();
int age = IO.readInt();
IO.readln();
if (!IO.eof()) list.add(new Entry(name, age)); // add to end of list
} while (!IO.eof());
IO.writeLine(list.size() + " items stored"); // interrogate size of list
for (int i = 0; i < list.size(); i++) { // display each entry
Entry e = (Entry) list.get(i); // retrieve (via a cast) an item at position i
IO.write(e.name, -16); IO.writeLine(e.age); // -16 means "left justify"
}
IO.writeLine();
int where = position("Pat"); // find the silly fellow!
if (where < 0) IO.writeLine("Pat not found")
else {
Entry pat = (Entry) list.get(where);
IO.writeLine("Pat found at position " + where + ". He is " + pat.age + " years old");
}
}
}