This test is intended to check your ability to write attributed Cocol grammars. It should only take you about 15 minutes at the most. Textbooks may be used.
1. Tell me often enough, and I will believe anything. What are your surname (and initials)?
Terry P.D.
2. You thought you had heard the last of those bagpipes, didn't you? Wrong again! The grammar below describes a medley event at a Highland Gathering:
The organisers have decided that this year each band must play at least two jigs.
What would you have to add to this grammar so that the parser could disqualify any band that did not play at least two jigs and would also tell you (a) the total number of bands that had competed in the event (b) the name of the band that played the medley with the greatest number of tunes.
import Library.*; /* so that we have access to the IO library */
COMPILER Event $CN
/* Describe simple pipe band competition event. This simple problem is best handled with
some simple static (global) fields, rather than complex parameter passing */
static int bandCount = 0, longestCount = 0, tuneCount, jigCount;
static String longestBand, nextBand;
IGNORE CASE
IGNORE CHR(1) .. CHR(31)
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".
TOKENS
NameOfBand = letter { letter } .
PRODUCTIONS
Event
= Band { Band } (. IO.WriteLine(bandCount + " bands competed");
IO.Write("Longest medley played by " + longestBand); .)
.
Band (. bandCount++; .)
= NameOfBand (. nextBand = token.str; // must save it here for later .)
Medley (. if (jigCount < 2)
SemError(nextBand + " disqualified - too few jigs");
if (tuneCount > longestCount) {
longestBand = nextBand;
longestCount = tuneCount;
} .)
.
Medley (. jigCount = 0; tuneCount = 0; .)
= OneTune { OneTune }
"break" .
OneTune (. tuneCount ++; // at least one tune played here .)
= "March"
| "SlowMarch"
| "Jig" (. jigCount++; // count these separately .)
| "Hornpipe"
| "Reel"
| "Strathspey"
{ "Strathspey" (. tuneCount++; // we can get several tunes here .)
} "Reel" (. tuneCount++; // and one more tune here too .)
.
END Event.
It was quite alarming to see how badly question 2 was answered. I got the feeling that at least half the class had no clue about adding actions to a grammar, or, worse still, any clue about how and why one would perform the additions and checks needed to solve what is really a very simple problem. Typical points missed were as follows (please look at all of these, even if you did get a partially correct solution):
(a) In a non-recursive problem as simple as this one, the easiest way to ensure that all productions have access to all the variables is to declare them as static fields of the parser. Java does not have proper reference parameter passing (in this respect it is quite awful as a language) so you can either pass values "down" or "up", but not in both directions (which you would really need to do here) unless you pass references to specially created objects of an appropriate class, and that is really overkill for this problem. If you don't know what I am talking about, then that is even more worrying, and you should come to seek clarification. You should have mastered those aspects of Java programming in first year!(b) You have to count the total number of tunes and the total number of jigs separately, and these counts have to be reset to zero for each band.
(c) The OneTune production has a slightly deceptive name. A sequence of strathspeys and the mandatory reel contribute two or more tunes to the total.
(d) NameOfBand is the name of a terminal and is not (and cannot be) followed by <parameters>. It has to be followed immediately by an action to save the value of token.str. Every time you scan for a new token the value of token.str is refreshed - you cannot hope that it will magically stay the same until it is needed later.
(e) The semantic check on the number of jigs can only be applied after the medley is complete. The check for the longest medley can only be applied after the medley is complete. Surely that was obvious, yet many solutions tried applying the check as soon as a jig was detected.
(f) There was no need to use string variables to save strings like "March". You only had to count the tunes!
(g) Don't be tempted to play around with comparisons like if (sym.kind = SYM.BandSym). They require too deep a knowledge of the inner workings of Coco/R and sooner or later will lead you astray.
(h) Most important of all - you cannot just write down some (. random actions .) at arbitrary points in the grammar. Their positioning is crucially important. You were warned about this in lectures, after all!
3. As some of you may know, my brother Peter occasionally brightens up your TV screens with good advice as to how to keep your toilets clean using Domestos and your bathroom walls beautiful with tiles from CTM. (I suspect he may teach you more useful skills than I do!); he also has been known to appear occasionally in "Generations". What you may not know is that he worked for State Theatre in Pretoria, which folded up a few years ago, so he is dependent more than ever before on how the SABC treat him.
The SABC fear that he may be suffering from over-exposure and have asked me to extend/write a system to allow them to check that he never appears in two advertisements in a row (that is, that the Domestos and CTM adverts must be separated by at least one other advert), and that neither of those adverts immediately follows a screening of "Generations".
COMPILER SABCTV $CN
/* "Bob, Bob" - check over-exosure of Peter Terry in TV commercials.
Once again, a very simple problem can be solved in a very simple way */
static boolean justSeenPeter = false;
IGNORE CHR(1) .. CHR(31)
PRODUCTIONS
SABCTV = { Programme } "Closedown" .
Programme = "Announcement" { QualityShow } "Reminder" .
QualityShow
= ( ( "Frasier" | "MyFamily" ) (. justSeenPeter = false; .)
| "Generations" (. justSeenPeter = true; .)
)
{ Advert } .
Advert
= ( "CTMTiles" | "Domestos" ) (. if (justSeenPeter)
SemError("Peter over exposed!");
justSeenPeter = true; .)
| ( "VodaCom" | "Nando's" | "LGDigital" ) (. justSeenPeter = false; .) .
END SABCTV.