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]
Pat Terry, 63T0844. Student name and student number! And it is genuine. Note that your student number normally just has two digits (63) for the year of first registration, the initial letter of the surname, and a four digit number for the number of applications that had been received when yours was processed. the number is often quoted with a further leading 6 (as in 663T0844), but this is a hangover from the days when we had campus 6 (Grahamstown) and campus 8 (East London). No, I don't know, so don't ask!
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]
A point that many missed was that I wanted all nine component marked. Some components have two common names, and you should know them both and not confuse them!
┌─────────────────────────────┐
│ Source Handler │ (produces)
Source ───> │ First Part of Front end ├─────────────────────> Source listing
code │ │
└─────────────────────────────┘
¢
(will call)
│
┌────────────┴──────────────┐ ┌────────────────────────┐
│ Lexical Analyser │ │ Error Handler │
│ Scanner │ │ (Both ends may │
│ Second part of Front end │ (may call) │ have to access it │
│ ├─────────────────────>│ │
│ │ ┌───────────────>│ │
└───────────────────────────┘ │ └────────────────────────┘
¢ │ ¢
(will call) (may call) (may call)
│ │ │
┌────┴────────────────────────────┴─┐ ┌───────┴────────────────┐
│ Syntax Analyser │ (will call) │ Code Generator │
│ Semantic analyser ├─────────────>│ Back end ├───> Object code
│ Parser │ │ │
│ Major part of Front end │ │ │
└───────────────────────────────────┘ └────────────────────────┘
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]
This was very badly done. I can't think why, unless you just never thought about what you were doing?
CSHARP SieveCS.CS Native code, Self-resident compiler - runs on Intel, generates Intel FPC SievePas.pas Native code, Self-resident compiler - runs on Intel, generates Intel BCC SieveC.C Native code, Self-resident compiler - runs on Intel, generates Intel Parva SievePav.Pav Interpretive compiler, Cross compiler - runs on Intel, generates PVM Parva2ToCSharp SievePav.pav High-level compiler - runs on Intel, generates C#
4. What is meant by the concept of a "self-compiling compiler"? (just a short answer!) [2]
A compiler whose source code is expressed or written in the language which the compiler is able to compile in general (and in the special case of compiling its own source to reproduce itself).
5. Why is developing a self-compiling compiler regarded as a worthwhile exercise? [3]
Once you have it, you can free yourself of development of the compiler (and other software) from having to use (for example) the compiler for another language, like the one which you originally used to develop the compiler.
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]
I should really have drawn three Ts. You can't claim to own a self-compiling compiler unless you have access both to its source and its executable. I would guess that FPC, CSHARP, BCC and Java would all be self compiling compilers, but the distributors are unlikely to give you the source; it's too valuable. There is a Free Software Foundation C compiler called "GNU C" where the source is available, and the CoCo compiler that we will be using soon is supplied as an executable and with source (which we have modified and recompled in the past).
┌──────────────────────────┐ ║ ┌──────────────────────────┐ ┌──────────────────────────┐
│ BCC.EXE │ ║ │ CSC.CS │ │ CSC.EXE │
│ C ──────────> Intel│ ║ │ C# ──────────> Intel│ │ C# ──────────> Intel│
│ │ ║ │ │ │ │
└───────┐ ┌───────┘ ║ └───────┐ ┌───────┘ └───────┐ ┌───────┘
│ │ ║ │ │ │ │
have: │ Intel │ ║ want: │ Intel │ Source and Object │ Intel │
│ │ ║ │ │ of the C# compiler │ │
└──────────┘ ║ └──────────┘ └──────────┘
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]
┌──────────────────────────┐ ┌──────────────────────────┐
│ CSC.C │ │ CSC1.EXE │ Step 1 - write the C#
│ C# ──────────> Intel │ │ C# ──────────> Intel │ compiler using C and compile
│ │ │ │ it with the C compiler BCC.EXE
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘ to give the first C# compiler
│ │ BCC.EXE │ │ for Intel machines
write │ C │ C ────────> Intel │ Intel │ first C#
source │ │ │ │ compiler
in C └──────────┴───────┐ ┌───────┴──────────┘
│ │ Intel │ │
│ have │ │ │
│ BCC ├──────────┤ │ use this in the next stage
│ │ │ │
│ │ Intel │ │
│ └──────────┘ │
rewrite CSC.C in C# │
(a new "front end") │ and compile it with the
│ ┌──────────────────┘ first C# compiler
V │
┌──────────────────────────┐ │ ┌──────────────────────────┐
│ CSC.CS │ │ │ CSC.EXE │
│ C# ──────────> Intel │ │ │ C# ──────────> Intel │
│ │ V │ │
└───────┐ ┌───────┴──────────┴───────┐ ┌───────┘
│ │ CSC1.EXE │ │
rewrite │ C# │ C# ────────> Intel │ Intel │
source │ │ │ │
└──────────┴───────┐ ┌───────┴──────────┘
│ Intel │ ^
use first │ │ │ In principle, if you have done it correctly,
C# compiler ├──────────┤ │ these will be the same, or should converge
CSC1.EXE │ │ <────────┘ onto the same if you repeat the process
│ 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
Incidentally, 51 means Friday Dawnie. Clearly some CSC_301 students can't count that far, which is why we prescribe Maths 1C. Do drop in sometime and join me for early morning thrills and spills, and take out an low cost weakly 45 minute Academic Insurance Package.
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_1C1 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.
I was pleased to find that a relatively large number of students saw that all that was needed was to read elements into a set for each course and then to look at the intersection of two sets to find the periods that clash. But I was amused, if not worried, at how complicated some of the solutions were. Learn to use the Library routines provided, and keep things as simple as possible - Golden Rule for work submitted to PDT
using Library;
using System.Collections.Generic;
class TimeTable {
// Simple application of the generic Dictionary class in C#
// Pat Terry, 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;
** IntSet periods = new IntSet();
** int p = IO.ReadInt(); // don't mess about with reading, splitting
** while (p != 0) { // and parsing bits of string - ReadInt
** periods.Incl(p); p = IO.ReadInt(); // does it all for you!
** }
timeTable.Add(course, new Entry(course, periods));
} while (true);
do { // Now check pairs of subjects for clashes
string query1 = IO.ReadWord();
if (query1.Equals("stop")) break;
string query2 = IO.ReadWord();
if (timeTable.ContainsKey(query1) && timeTable.ContainsKey(query2)) {
** IntSet periods1 = timeTable[query1].periods;
** IntSet periods2 = timeTable[query2].periods;
** IntSet clashes = periods1.Intersection(periods2);
** if (clashes.Members() == 0) // or just use "if (clashes.IsEmpty())"
** IO.WriteLine(query1 + " and " + query2 + " do not clash");
** else
** IO.WriteLine(query1 + " and " + query2 + " clash in periods " + clashes);
** }
else
IO.WriteLine("Unknown course(s) - try again or 'stop' to exit");
} while (true);
} // Main
} // TimeTable