This should take no longer than 45 minutes and is simply intended to probe whether you have understood the material in the prac questions and the early part of the course. Answer on the question sheet (4 sides).
"The purpose of computing is insight, not numbers" (Richard Hamming)
1. You should get this right! Mine is Pat Terry, 63T0844. What is yours - in the same format? [1]
2. Important components of a compiler are often called the source handler, code generator, parser, semantic analyser, syntax analyser, scanner, error handler, front end, back end and so on. Add each of these components to the diagram below to indicate the relationships between them. [9]
┌─────────────────────────────┐
│ │ (produces)
Source ───> │ ├─────────────────────> Source listing
code │ │
│ │
└─────────────────────────────┘
¢
(will call)
│
┌─────────────┴─────────────┐ ┌────────────────────────┐
│ │ │ │
│ │ │ │
│ │ (may call) │ │
│ ├─────────────────────>│ │
│ │ ┌───────────────>│ │
└───────────────────────────┘ │ └────────────────────────┘
¢ │ ¢
(will call) (may call) (may call)
│ │ │
┌────┴────────────────────────────┴─┐ ┌───────┴────────────────┐
│ │ (will call) │ │
│ ├─────────────>│ ├───> Object code
│ │ │ │
│ │ │ │
│ │ │ │
└───────────────────────────────────┘ └────────────────────────┘
3. Compilers can be classified in many ways - assemblers, high level compilers, native-code compilers, interpretive compilers, self-compiling compilers, cross-compilers, self-resident compilers etc. What kind of compiler were you using in the practicals when you gave the following commands? [5]
CSHARP SieveCS.CS
FPC SievePas.pas
BCC SieveC.C
Parva SievePav.Pav
Parva2ToCSharp SievePav.pav
4. What is meant by the concept of a "self-compiling compiler"? (just a short answer!) [2]
5. Why is developing a self-compiling compiler regarded as a worthwhile exercise? [3]
6. Suppose in your first job as a professional compiler writer you are provided with (a) a compiler for the C language that can run on the PC and (b) you are asked to write a self-compiling compiler for C# that can run directly on the PC. Represent these tools as T diagrams: [4]
┌──────────────────────────┐ ║ ┌──────────────────────────┐ ┌──────────────────────────┐
│ │ ║ │ │ │ │
│ ──────────> │ ║ │ ──────────> │ │ ──────────> │
│ │ ║ │ │ │ │
└───────┐ ┌───────┘ ║ └───────┐ ┌───────┘ └───────┐ ┌───────┘
│ │ ║ │ │ │ │
(a) │ │ ║ (b) │ │ │ │
│ │ ║ │ │ │ │
└──────────┘ ║ └──────────┘ └──────────┘
7. How could you develop this self-compiling compiler? Answer this by drawing T diagrams showing what you decide to do (the first diagram is partially filled in for you). [6]
┌──────────────────────────┐ ┌──────────────────────────┐
│ │ │ │
│ ──────────> │ │ ──────────> │
│ │ │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ │ │
│ C │ ────────> │ Intel │
│ │ │ │
└──────────┴───────┐ ┌───────┴──────────┘
│ │
│ │
├──────────┤
│ │
│ Intel │
└──────────┘
┌──────────────────────────┐ ┌──────────────────────────┐
│ │ │ │
│ ──────────> │ │ ──────────> │
│ │ │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ │ │
│ │ ────────> │ │
│ │ │ │
└──────────┴───────┐ ┌───────┴──────────┘
│ │
│ │
├──────────┤
│ │
│ │
└──────────┘
8. This week's tutorial sheet outlined a simple use of a dictionary class for building up a list of courses and their lecture venues and then allowing this to be interrogated. A more interesting program can be written in much the same way to store a table of courses and their lecture times and then interrogating this to see whether two courses have one or more lecture clashes. For example, some of the Rhodes timetable might be represented in textual form as follows, where a number like 34 means Wednesday period 4, 11 means Monday dawnie etc
CSC_101 11 22 33 44 55 0
CSC_201 13 24 35 41 52 0
CSC_301 12 23 34 45 46 51 0
DRAMA_1 22 33 44 0
DRAMA_3 13 24 35 52 0
MAT_1C2 16 26 36 46 56 0
#######
For this timetable, although CSC_201 and CSC_301 do not clash, DRAMA_1 and CSC_101 clash in periods 22, 33 and 44.
Quite a bit of the code for a simple version of such a system is given below. Show how the use of the IntSet class can be used to complete the system (keep it simple; you only need a very few lines to do the job).
using Library;
using System.Collections.Generic;
class TimeTable {
// Check for lecture clashes
// Always add your name, Rhodes University, 2017
class Entry {
public string course;
public IntSet periods;
public Entry(string course, IntSet periods) {
this.course = course;
this.periods = periods;
} // constructor
public override string ToString() {
return course + " is held in " + periods;
} // ToString
} // Entry
static Dictionary<string, Entry> timeTable = new Dictionary<string, Entry>();
public static void Main (string[] args) {
do {
string course = IO.ReadWord();
if (course.Equals("#######")) break;
// now read and handle the lecture times
// and add the details into the timeTable
timeTable.Add(course, new Entry(course, periods));
} while (true);
do { // Now check pairs of subjects for clashes
string subject1 = IO.ReadWord();
if (subject1.Equals("stop")) break;
string subject2 = IO.ReadWord();
if (timeTable.ContainsKey(subject1) && timeTable.ContainsKey(subject2)) {
// can now check for clashes
else
IO.WriteLine("Unknown course(s) - try again or 'stop' to exit");
} while (true);
} // Main
} // TimeTable
A reminder of the methods in the IntSet class appears below, as does the code for the program on the Tutorial sheet.
public class IntSet {
public IntSet()
public IntSet(params int[] members)
public void Incl(int i)
public void Excl(int i)
public bool Contains(int i)
public bool IsEmpty()
public int Members()
public IntSet Union(IntSet otherSet)
public IntSet Intersection(IntSet otherSet)
public IntSet Difference(IntSet otherSet)
public void Write()
public string ToString()
} // IntSet
_________________________________________________________________
using Library;
using System.Collections.Generic;
class Venues {
// Simple application of the generic Dictionary class in C#
// Pat Terry, Rhodes University, 2017
class Entry {
public string course;
public string venue;
public Entry(string course, string venue) {
this.course = course;
this.venue = venue;
} // constructor
public override string ToString() {
return course + " is held in " + venue;
} // ToString
} // Entry
static Dictionary<string, Entry> venueTable = new Dictionary<string, Entry>();
public static void Main (string[] args) {
do { // Store the timetable
string course = IO.ReadWord();
if (course.Equals("#######")) break;
string venue = IO.ReadWord();
venueTable.Add(course, new Entry(course, venue));
} while (true);
do { // Now lookup some venues
string query = IO.ReadWord();
if (query.Equals("stop")) break;
if (venueTable.ContainsKey(query))
IO.WriteLine(query + " is held in " + venueTable[query].venue);
else
IO.WriteLine(query + " not found - stop to exit");
} while (true);
} // Main
} // Venues
PROGRAM Sieve (Input, Output);
(* Sieve of Eratosthenes for finding primes 2 <= N <= Max
P.D. Terry, Rhodes University, 2017 *)
CONST
Max = 32000 (* largest number allowed *);
TYPE
SIEVES = ARRAY [0 .. Max] OF BOOLEAN;
VAR
I, N, K, Primes : INTEGER (* counters *);
Uncrossed : SIEVES (* the sieve *);
BEGIN
Write('Supply largest number to be tested '); Read(Input, N);
IF N > Max THEN BEGIN
WriteLn(Output, 'N too large, sorry'); HALT
END;
Primes := 0; (* no primes yet found *);
FOR I := 0 TO N DO (* clear sieve *)
Uncrossed[I] := TRUE;
I := 2;
WHILE I <= N DO BEGIN (* the passes over the sieve *)
IF Uncrossed[I] THEN BEGIN
Primes := Primes + 1;
K := I; (* now cross out multiples of I *)
REPEAT
Uncrossed[K] := FALSE;
K := K + I
UNTIL (K > N) OR (K < 0); (* strange line 1 *)
I := I + 1; (* strange line 2 *)
END (* if uncrossed *);
I := I + 1; (* strange line 3 *)
END (* while i <= n *);
Write(Primes:4, ' primes')
END.
class Entry {
public string course;
public IntSet periods;
public Entry(string course, IntSet periods) {
this.course = course;
this.periods = periods;
} // constructor
public override string ToString() {
return course + " is held in " + periods;
} // ToString
} // Entry
static Dictionary<string, Entry> timeTable = new Dictionary<string, Entry>();
public static void Main (string[] args) {
do {
string course = IO.ReadWord();
if (course.Equals("#######")) break;
IntSet periods = new IntSet(); // read snd store the lecture times
int p = IO.ReadInt();
while (p != 0) {
periods.Incl(p); p = IO.ReadInt();
}
timeTable.Add(course, new Entry(course, periods));
} while (true);
do { // Now check pairs of subjects for clashes
string subject1 = IO.ReadWord();
if (subject1.Equals("stop")) break;
string subject2 = IO.ReadWord();
if (timeTable.ContainsKey(subject1) && timeTable.ContainsKey(subject2)) {
// can now check for clashes
IntSet periods1 = timeTable[subject1].periods;
IntSet periods2 = timeTable[subject2].periods;
IntSet clashes = periods1.Intersection(periods2);
if (clashes.Members() == 0)
IO.WriteLine(subject1 + " and " + subject2 + " do not clash");
else
IO.WriteLine(subject1 + " and " + subject2 + " clash in periods " + clashes);
}
else
IO.WriteLine(" not found - stop to exit");
} while (true);
} // Main
} // TimeTable