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 sheet". 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.
In this practical you are to
You will need this prac sheet and your text book. Copies of the prac sheet and of the Parva report 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 sheet:
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 PRAC21.ZIP.
l:
md prac21
cd prac21
copy i:\csc301\trans\prac21.zip
unzip prac21.zip
This will create several other directories "below" the prac21 directory:
L:\prac21
L:\prac21\coco
L:\prac21\frames
L:\prac21\library
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 essentially the calculator grammar from section 5.9.5 of the text, with a slight (cosmetic) change of name.
Use Coco/R to generate a parser for data for this calculator. You do this most simply by giving the command
cmake CALC
Used like this, Coco/R will simply generate three important components of a calculator program - the parser, scanner, and main driver program. Cocol specifications can be programmed to generate a complete calculator too (ie one that will evaluate the expressions, rather than simply check them for syntactic correctness), but that will have to wait for the early hours of another day.
(Wow! Have you ever written a program so fast in your life before?)
Of course, having Coco/R write you a program is one thing. But it might also be fun and interesting to run the program and see that it works.
A command like
crun Calc DATA.TXT
will run the program Calc and try to parse the file DATA.TXT, sending error messages to the screen. Giving the command in the form
crun Calc calc.txt -L
will send an error listing to the file listing.txt, which might be more convenient. Try this out on the calculator:
Well, you did all that. Well done. What next?
For some light relief and interest you might like to look at the code the system generated for you (four .java files are created in a subdirectory CALC) - you don't have to comment this week, simply gaze in awe. Don't take too long over this, because now you have the chance to be more creative!
Wait - we have not finished yet. Modify the grammar so that you can use parentheses in your expressions, can raise quantities to a "power" (as in 12^2 + 5^6, meaning 122 + 56) and also give the calculator a square- root capability (as in 4 + sqrt(5 * 12)).
Well, of course, it does not have any real "calculator" capability - it cannot calculate anything (yet). It only has the ability to recognise or reject expressions at this stage. Try it out with some expressions that use the new features, and some that use them incorrectly.
Warning. Language design and grammar design is easy to get wrong. Think hard about these problems before you begin, and while you are doing them.
Now that you know all about Ceol Mor and how it was handed on (quickly, what was that strange word for the notation used?), you will be intrigued to learn that Scottish pipe bands often compete at events called Highland Gatherings where three forms of competition are traditionally mounted. There is the so-called "Slow into Quick March" competition, in which each band plays a single Slow March followed by a single Quick March. There is the so-called "March, Strathspey and Reel" competition, where each band plays a single Quick March, followed by a single Strathspey, and then by a single Reel; this set may optionally be followed by a further Quick March. And there is also the "Medley", in which a band plays a selection of tunes in almost any order. Each tune falls into one of the categories of March, Strathspey, Reel, Slow March, Jig and Hornpipe but, by tradition, a group of one or more Strathspeys within such a medley is always followed by a group of one or more Reels.
Develop a grammar to describe the activity at a Highland Gathering at which a number of competitions are held, and in each of which at least one band performs. Competitions are held in one category at a time, with a short break between competitors, and between events, and with a suitable announcement being made to introduce tha category of competition and the name of each band to the audience. Regard concepts like "March", "Reel", "AnnounceCompetition", "break" and so on as terminals - in fact there are many different possible tunes of each sort, of course, but you may have to be a piper to recognize one tune from another!
(Incidentally, the classical music of the Highland Pipe is almost never played by bands. It is a very refined form of solo music; admittedly an acquired taste.)
The file EBNF.ATG contains a Cocol grammar that describes EBNF using EBNF conventions, which might be familiar from lectures. Try this out "as is" to begin with, for example:
cmake EBNF
crun EBNF EBNF.TXT
crun EBNF EBNF.BAD -L
Next, use the grammar as a guide to develop a new system that will recognise or reject a set of productions like those in EBNF.TXT, but with your Cocol grammar written in such a way that it does not itself use any of the Wirth "meta brackets". As a hint, you will have to set up an equivalent grammar, using right-recursive production rules.
In the prac kit you will find the grammar for the first level of Parva taken from page 108. Generate a program from this that will recognise or reject simple Parva programs, and verify that the program behaves correctly with the two sample programs in the kit, namely VOTER.PAV and VORED.BAD.
cmake parva
crun Parva voter.pav
and
crun Parva voter.bad
Parva really is a horrid little language, isn't it? But its simplicity means that it is easy to devise Terry Torture on the lines of "extend it".
Specifically, add:
Here are some examples of code that should give you some ideas.
void main () {
// Demonstrate syntax for various loops
// (not supposed to do anything useful!)
int i = 1, k = 0;
while (i < 10) {
do {
k = k + 1;
} while (k < i);
i = i + 1;
}
for (i = 1; i <= 10; i = i + 1) {
read(k);
write(i, i * k);
}
i = 0;
for (bool b = true; b || i < 10; b = ! b) i = i + 1;
}
void main () {
// Demonstrate the dreaded goto statement
int limit;
read(limit);
if (limit <= 0) goto 40;
int i = 1, k = 0;
10:
if (i > 10) goto 30;
20:
k = k + 1;
if ( i <= k) goto 20;
i = i + 1;
goto 10;
30:
40: return;
50: goto 50;
}
There are some little programs like this in the kit, but you can easily write some of your own.
Note: Read that phrase again: "which should give you some ideas". And again. And again. Don't just rush in and write a grammar that will recognise only some restricted forms of statement. Think hard about what sorts of things you can see there, and think hard about how you could make your grammar fairly general.
Derive a grammar to describe a mixed passenger and goods train, with one (or more) locomotives, then one or more goods trucks, followed either by a guard's van, or by one or more passenger coaches, the last of which should be a passenger brake van. In the interests of safety, try to build in a regulation to the effect that fuel trucks may not be marshalled immediately behind the locomotives, or immediately in front of a passenger coach.
Some sample trains may be found in the file TRAINS in the kit. See if you can generate a parser that will either accept or reject these trains.
UltraEdit can be configured to link to Coco/R by using options in the "advanced" pull down menu - one invokes Coco/R on the file in the "current window".
It is easy enough to set up an option to invoke Coco/R. Use the Advanced ->; Tool Configuration pull down, and set up an option to read as in the example below
Unfortunately UltraEdit does not seem to remember these local additions. You will need to do this each time you log in.
You can run the Java version of Coco/R free standing with a command like:
cmake GRAM
Like that, error messages are a little cryptic. In the form
cmake GRAM -M
in which case the system will produce you a listing of the grammar file and the associated error messages, if any, in the file LISTING.TXT.
Finally, the form
cmake GRAM -M ErrorFile
is useful for redirecting the error messages from the Java compiler to a listing file ErrorFile.
For ease of use with the Java file and directory naming conventions, please
Make sure that the grammar includes the "pragma" $CN. The COMPILER line of your grammar description should thus always read something like
COMPILER Name $NC
Error checking by Coco/R takes place in various stages. The first of these relates to simple syntactic errors - like leaving off a period at the end of a production. These are usually easily fixed. The second stage consists of ensuring that all non-terminals have been defined with right hand sides, that all non-terminals are "reachable", that there are no cyclic productions, no useless productions, and in particular that the productions satisfy what are known as LL(1) constraints.
We shall discuss LL(1) constraints in class in the next week, and so for this prac we shall simply hope that they do not become tiresome. The most common way of violating the LL(1) constraints is to have alternatives for a nonterminal that start with the same piece of string. This means that a so-called LL(1) parser (which is what Coco/R generates for you) cannot easily decide which alternative to take - and in fact will run the risk of going badly astray. Here is an example of a rule that violates the LL(1) constraints:
assignment = variableName ":=" expression
| variableName index ":=" expression.
index = "[" subscript "]" .
Both alternatives for assignment start with a variableName. However, we can easily write production rules that does not have this snag:
assignment = variableName [ index ] ":=" expression .
index = "[" subscript "]" .
A moment's thought will show that the various expression grammars that we have discussed in class - the left recursive rules like
expression = term | expression "-" term .
also violate the LL(1) constraints, and so have to be recast (see the CLANG.ATG file) as
expression = term { "-" term } .
to get around the problem.
For the moment, if you encounter LL(1) problems, please speak to the long suffering demonstrators, who will (hopefully) be able to help you resolve them.