You may use your notes, or refer to material on the website if you like. Keep your solutions as simple as possible! Answer on the question sheet (4 sides)
1. Some people never remember, no matter how often you remind them - What are your first name and surname? [1]
Pat Terry
1. The simple grammar below describes a freight train, which is headed by one or more locomotives. Sometimes the locomotives move around without pulling a load of trucks, but more usually they pull a number of freight trucks, the last of which is followed by a brake truck. Freight trucks come in three varieties - open (for transporting coal), closed (for transporting perishable goods) and fuel (for transporting petrol or diesel).
(a) The manager of TransNet has a problem. He has been told that he cannot put a fuel truck immediately behind a loco, or immediately in front of the brake van, because of the risk of explosion to the people who drive the loco or drink coffee in the brake van. He has found that the CS department produce very employable graduates, and asks that one of them attribute the grammar below to enforce these regulations. You all rise to the challenge and complete the grammar spread out on the accompanying page.
Maybe you can rise to the Board of TransNet once you get bored of my humour.
(b) Is it possible to write another simple grammar that describes the restricted form that trains may assume without resorting to adding attributes to the first grammar - that is, imposes the safety constraints "in syntax"? Of course you can! Show me what the second grammar looks like and then tell me whether or not the two grammars are syntactically "equivalent" (and why or why not).
(c) What is the significance of the word SYNC in this grammar, and what is the significance of IGNORECASE?
COMPILER Trains $CN
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains = { Train } EOF .
Train = SYNC "loco" { "loco" } [ Load ] SYNC "."
Load = { "open" | "closed" | "fuel" } "brake" .
END Trains.
This is very simple - we just have to be able to "look behind" each item of rolling stock!
COMPILER Trains1 $CN
/* Describe possible freight trains, with the restrictions:
no fuel immediately behind a loco or in front of brake */
static string last = null;
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains1 = { Train } EOF .
Train = SYNC
"loco" { "loco" } (. last = "loco"; .)
[ Load ]
SYNC "." .
Load = { ( "fuel" (. if (last.Equals("loco"))
SemError("fuel may not follow loco");
last = "fuel"; .)
| "open" (. last = "open"; .)
| "closed" (. last = "closed"; .)
)
}
"brake" (. if (last.Equals("fuel"))
SemError("brake may not follow fuel"); .) .
END Trains1.
This might be regrouped and shortened slightly, maaing use of token.val:
COMPILER Trains3 $CN
/* Describe possible freight trains, with the restrictions:
no fuel immediately behind a loco or in front of brake */
static string last = null;
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains3 = { Train } EOF .
Train = SYNC
"loco" { "loco" } (. last = "loco"; .)
[ Load ]
SYNC "." .
Load = { ( "fuel" (. if (last.Equals("loco"))
SemError("fuel may not follow loco"); .)
| "open"
| "closed"
) (. last = token.val; .)
}
"brake" (. if (last.Equals("fuel"))
SemError("brake may not follow fuel"); .) .
END Trains3.
Alternative productions that require no semantic actions are easy enough
COMPILER Trains2 $CN
/* Describe possible freight trains, with the restrictions:
no fuel immediately behind a loco or in front of brake */
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains2 = { Train } EOF .
Train = SYNC "loco" { "loco" } [ Load ] SYNC "." .
Load = [ SafeTruck { { "fuel" } SafeTruck } ] "brake" .
SafeTruck = "open" | "closed" .
END Trains2.
Are these grammars syntactically equivalent? Why/why not?
A case could be made either way, I suppose. If by "syntactically equivalent" you understand "equivalence in the absence of contest sensitive constraints" then these grammars are not equivalent, as the first one (as in the question) allows trains (sentences!) in which fuel trucks can appear in places which the second grammar forbids. So the two grammars do not define exactly the same languages. But parsers derived by Coco from either grammar will accept or reject exactly the same trains - so the parsers are "equivalent" in that sense. I had expected the "not equivalent" answer, because equivalence is supposed to refer to syntax only, but you would have gained credit for a well argued contrary opinion.
What are the significance of SYNC and IGNORECASE?
SYNC is used to mark points in the productions where a significant terminal (or one of a set of such terminals) should be expected, failing which the scanner should read and ignore tokens until such a terminal is discovered (or EOF, of course). This provides a way for the parser to attempt error recovery. If the SYNC points are carefully thought out, it can work very well, although, like any error recovery technique, it is not perfect.
IGNORECASE stipulates that the key words used in the grammar are insensitive to case, so that (for example) WHILE, while, While and wHiLe would be treated in the same way. It does not, however, apply to identifiers - if you want to make them case-insensitive you have use something like token.val.ToLower() (I did not expect you to know about identifiers being exempt.)
2. The grammar below attempts to describe your present hard-working lifestyle.
COMPILER Prac $CN
/* Describe progress of a compiler practical */
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
TOKENS
name = letter { letter } .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Prac = Handouts { Task } "Submit" .
Handouts = "CoverSheet" { "TaskSheet" } .
Task = "Attempt" { ConsultTutor "Attempt" } .
ConsultTutor = name .
END Prac.
As you know, we sometimes have trouble finding tutors. As you may not know, we are going to have problem paying them, because they have recently told me that they want to be paid a fee for each occasion they are consulted. So what I need now is a list of tutors with a count of such occasions for each one. What must I add to the grammar to produce me such a list? A typical list might be as follows:
Darryl 12
JayCee 10
Simon 11
Pat 70
Once again, this is simple. Simple enough that we can get away with a tutor list declared "global" to the other parsing routines.
using Library;
using System.Collections.Generic;
COMPILER Prac $CN
/* Determine how often each tutor has been consulted during a practical
P.D. Terry, Rhodes University, 2015 */
class Tutor {
public String name;
public int count;
public Tutor(String name, int count) {
this.name = name; this.count = count;
}
public void writeTutor() {
IO.Write(this.name, -14);
IO.WriteLine(this.count);
}
} // Tutor
static List<Tutor> list = new List<Tutor>(); // global for simplicity here!
static int Position(String name) {
// Finds position of entry with search key name in list, or -1 if not found
int i = list.Count - 1; // index of last entry
while (i >= 0 && !name.Equals(list[i].name)) // short-circuit protection
i--; // will reach -1 if no match
return i;
} // Position
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
TOKENS
name = letter { letter } .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Prac
= Handouts { Task }
"Submit" (. for (int i = 0; i < list.Count; i++)
list[i].writeTutor(); .) .
Handouts
= "PracSheet" { "HintSheet" } .
Task
= "Attempt" { ConsultTutor "Attempt" } .
ConsultTutor
= name (. int pos = Position(token.val);
if (pos >= 0) list[pos].count++;
else list.Add(new Tutor(token.val, 1)); .) .
END Prac.
Here are some other submitted attempts to find a Train grammar
COMPILER BadTrains $TF
/* Attempts to describe possible freight trains, with the restrictions:
no fuel immediately behind a loco or in front of the brake */
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
BadTrains = { Train } EOF .
Train = SYNC "loco" { "loco" } [ Load ] SYNC "." .
Safe = "open" | "closed" .
// Comment out the productions you do not want to use to define Load so that
// you can submit the code to Coco for test purposes
Load = [ Safe [ "fuel" ] ] "brake" .
Load = { "open" | "closed" | { Safe } "fuel" { Safe } } "brake" .
Load = [ Safe [ { Safe | "fuel" } Safe ] ] "brake" .
Load = Safe [ { Safe | "fuel" } Safe ] "brake" .
Load = { Safe [ "fuel" Safe ] } "brake" .
Load = [ Safe { [ "fuel" ] Safe } ] "brake" .
Load = { Safe | "fuel" Safe } "brake" .
Load = { { Safe } { "fuel" } Safe } "brake" .
Load = [ Safe { { "fuel" } Safe } ] "brake" .
Load = [ Safe { Safe | ( "fuel" { "fuel" } Safe ) } ] "brake" .
Load = ( HasFuel | NoFuel ) "brake" .
HasFuel = Safe { "fuel" | Safe } Safe .
NoFuel = { Safe } .
Load = { "open" [ FUEL ] | "closed" [ FUEL ] } "brake" .
FUEL = { "open" | "closed" | "fuel" } Safe .
END BadTrains.