This should take no longer than 20 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 questions sheet (3 sides).
1. You should get this right! Mine is Pat Terry, 663T0184. What is yours? [1]
Pat Terry, 663T0184
2. Some translators are called assemblers, some are called compilers. How are they distinguished? [2]
Assemblers translate low level (assembler) code to machine code. Compilers generally translate high-level code to machine code. See page 8 of the text.
3. What happens in the front end of a compiler, and what happens in the back end of a compiler? [2]
The front end performs "analysis" - lexical, syntactic, semantic. It generally results in the production of an implicit or explicit decorated tree representation of the program. The back end uses performs "synthesis" - it uses this representation to generate object code for the program. See pages 10 - 14 of the text.
4. Explain very simply what you understand by lexical analysis and what you understand by syntax analysis. [2]
Lexical analysis is the phase responsible for grouping the characters of the source text into tokens. Syntax analysis is the phase of discerning syntactic structure from these tokens. Many people seemed to want to confuse lexical analysis with semantic or constraint analysis, but they are completely different in what they set out to achieve. See pages 11-12 of the text.
5. The following Parva program was submitted by a student who had been asked to print out a hailstone sequence. The program prints out a sequence, but not a correct sequence. What changes must be made to fix the problem (just mark them on the code, don't write it all out again). [3]
void main () {
// Produce a hailstone sequence
int term;
read("What is the first term? ", term);
write("\nSequence is ", term);
while (term != 1) {
if (term / 2 * 2 != term) term = 3 * term + 1;
if (term / 2 * 2 == term) term = term / 2;
write(term);
}
}
Given that you were supposed to have written code to generate such a sequence in the associated practical, the answers received were quite remarkably bad. Some people even suggested using an "else" which made me wonder whether they had done the practical at all (there is no "else" in Parva)! Here is one correct solution, using an intermediate variable:
void main () {
// Produce a hailstone sequence
int term, next;
read("What is the first term? ", term);
write("\nSequence is ", term);
while (term != 1) {
if (term / 2 * 2 != term) next = 3 * term + 1;
if (term / 2 * 2 == term) next = term / 2;
term = next;
write(term);
}
}
Here is another loop that "works", but is not terribly robust:
while (term != 1) {
if (term / 2 * 2 != term) {
term = 3 * term + 1; write(term);
}
if (term / 2 * 2 == term) {
term = term / 2; write(term);
}
}
It would not have worked had the order of the tests been interchanged:
while (term != 1) {
if (term / 2 * 2 == term) {
term = term / 2; write(term);
}
if (term / 2 * 2 != term) {
term = 3 * term + 1; write(term);
}
}
(Consider the case where the data supplied was the number 2. We would generate the sequence 2 3 10 .... Do you see why this is? If not, come and ask, or experiment until you find out.)
Here is another one which, while it achieves the effect, is a bit clumsy. In particular it uses an int as a boolean, which is always a rather bad way of doing things:
int flag = 1;
while (term != 1) {
if (term / 2 * 2 != term) {
term = 3 * term + 1; flag = 0;
}
if ((term / 2 * 2) == term) && (flag == 1)) term = term / 2;
write(term);
flag = 1;
}
6. The code below shows a Java version of a Sieve program for counting the number of primes below a limit read in as data. Show how it could be modified to make use of the SymSet class used in another exercise, in place of the Boolean array it currently uses. It will suffice to mark the changes on the code; there is no need to write out all the code again. [4]
import Library.*;
class Sieve {
public static void main (String [] args) {
final int Max = 4000;
boolean [] Uncrossed = new boolean [Max];
IO.write("Supply largest number to be tested ");
int n = IO.readInt();
int primes = 0;
for (int i = 2; i <= n; i++) {
Uncrossed[i] = true;
}
for (int i = 2; i <= n; i++) {
if (Uncrossed[i]) {
primes++;
int k = i;
do {
Uncrossed[k] = false;
k += i;
} while (k <= n);
}
}
IO.write(primes + " primes between 1 and " + n);
}
}
A reminder of the methods in the SymSet class appears below.
public class SymSet {
public SymSet()
public SymSet(BitSet s)
public SymSet(int[] members)
public void incl(int i)
public void excl(int i)
public boolean contains(int i)
public boolean isEmpty()
public int members()
public SymSet union(SymSet otherSet)
public SymSet intersection(SymSet otherSet)
public SymSet difference(SymSet otherSet)
public void write()
public String toString()
} // SymSet
Those of you who had really understood the last question in the prac had, as expected, no trouble with this whatsoever. A "set" is really very like an "array of Boolean". The correct solution follows (note that we had only to count the primes, not display the list of them):
import Library.*;
class Sieve {
public static void main (String [] args) {
Symset Uncrossed = new SymSet(); // +++++++++
IO.write("Supply largest number to be tested ");
int n = IO.readInt();
int primes = 0;
for (int i = 2; i <= n; i++) {
Uncrossed.incl(i); // +++++++++
}
for (int i = 2; i <= n; i++) {
if (Uncrossed.contains(i)) { // +++++++++
primes++;
int k = i;
do {
Uncrossed.excl(k); // +++++++++
k += i;
} while (k <= n);
}
}
IO.write(primes + " primes between 1 and " + n);
}
}
7. When experimenting with the Sieve program last week you should have discovered that the Pascal compilers allowed you to declare a sieve array of about 65000 elements, but attempts to look for prime numbers larger than about 16400 did not succeed. Give a reasonable explanation of why this should be. [2]
This was very badly done (only one or two people came close). Several suggested that it was because a 16 bit compiler could represent numbers in the range 0 ... 216 (which is why we can set up a sieve of very nearly this size; not quite 216, because we need some space for the other simple variables). Their argument then went that 16 bit integers can represent numbers in the range -215 ... 215 - 1 and that this explained it all. Unfortunately this range is -32768 ... 32767, so one is left with an unconvincing argument.
To understand the problem we have to look at the algorithm. The part of it that reads
int k = i;
do {
Uncrossed[k] = false;
k += i;
} while (k <= n);
deserves careful analysis. When we find a large enough prime (16411) in the range 0 .. 32767 (which itself causes no problem) we shall start the loop with a number that when added to itself produces a number greater than 32767, and which then appears to be negative. Of course, this negative number is less than n, so the loop executes again and promptly crashes with an attempt to use a negative subscript in an indexing operation.
Bizarre as it may seem, better performance is achieved by coding the loop on the lines of
int k = i;
do {
Uncrossed[k] = false;
k = k + i;
} while (k <= n && k > 0); // +++ handle overflow in k
8. In the prac you should have made use of the Xtacy system. Suppose you had the endearing program below, written in His Excellency's favourite language and stored in a file Career.MOD
MODULE Career;
IMPORT EasyIO;
BEGIN
EasyIO.WriteString("Hello Pat, you old fool!")
END Career.
Illustrate the process of making use of the Xtacy system to run this program by completing the diagram below [4]
Oh dear! And we had just done a tutorial on this and various other examples. I never understand why people find any difficulty with these diagrams, but year after year completely wrong answers are submitted that just look as though many of you write random words into the blocks in the hope that you might get a few right. Here is the correct solution. Xtacy translates Modula-2 code to the equivalent C code, which then has to be compiled with a C compiler to produce an executable. Surely that was obvious from doing the prac?
.--------------------------. .--------------------------. .--------------------------.
| Career.MOD | | Career.C | | Career.EXE |
| | | | | |
| () --------->"hello" | | () --------->"hello" | | () --------->"hello" |
`-------. .--------------------------. .--------------------------. .-------'
| | XC.EXE | | BCC.EXE | |
| Mod-2 | Mod-2 ----------> C | C | C ----------> 8086 | 8086 |
| | | | | |
`------------------. .--------------------------. .------------------'
| | | | .----------.
| 8086 | | 8086 | | 8086 |
| | | | `----------'
`----------' `----------'
.----------. .----------.
| 8086 | | 8086 |
`----------' `----------'