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]
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.
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
For your convenience these grammars have been spread out on the following pages.
using Library;
COMPILER Prac $CN
/* Determine how often each tutor has been consulted during a practical */
class Tutor { // add features as needed
public string name;
}
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.Size - 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;
}
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.
COMPILER Trains $CN
/* Describe a possible freight train - with restrictions */
IGNORECASE
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Trains
= { Train
} EOF
.
Train
= SYNC
"loco"
{ "loco"
}
[ Load
] SYNC "."
.
Load
= {
"open"
| "closed"
| "fuel"
}
"brake"
.
END Trains.
Alternative productiona that require no semantic actions
PRODUCTIONS
Trains = { Train } EOF .
Train = SYNC "loco" { "loco" } [ Load ] SYNC "." .
Load =
END Trains.
Are these grammars syntactically equivalent? Why/why not?
What are the significance of SYNC and IGNORECASE?
Home © P.D. Terry