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, 663T0844. What is yours? [1]
Pat Terry, 663T0844
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. 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 16411 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
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. 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 ShortCareer.MOD
MODULE ShortCareer;
IMPORT EasyIO;
BEGIN
EasyIO.WriteString("Hello Pat, you old fool!")
END ShortCareer.
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 looked at various examples like this, but maybe you didn't come to those lectures?. I never understand why people don't come to lectures or 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?
.--------------------------. .--------------------------. .--------------------------.
| ShortCareer.MOD | | ShortCareer.C | | ShortCareer.EXE |
| | | | | |
| () --------->"hello" | | () --------->"hello" | | () --------->"hello" |
`-------. .--------------------------. .--------------------------. .-------'
| | XC.EXE | | BCC.EXE | |
| Mod-2 | Mod-2 ----------> C | C | C ----------> 8086 | 8086 |
| | | | | |
`------------------. .--------------------------. .------------------'
| | | | .----------.
| 8086 | | 8086 | | 8086 |
| | | | `----------'
`----------' `----------'
.----------. .----------.
| 8086 | | 8086 |
`----------' `----------'
8. A little assembler course is being tutored by a future famous computer scientist in a building not a million kilometres away from Hamilton. The course requires students to be able to write code like the following:
BEG
INI ; read a value into accumulator
SHR ; shift right
SUB EXIT ; subtract value stored at EXIT
BNG NEG ;
POS OTC ; if positive output as unsigned number
BRN EXIT ;
NEG OTI ; else output as signed number
EXIT HLT ; terminate execution
END
but the tutor does not have a real machine on which to run this. So he has been developing a little emulator for the machine, using Java as the host language. He got as far as the following code when he was distracted by the other activities on Wednesday night.
How do you suppose the code should be completed for emulating the missing opcodes (that is, complete the "case" arms for OTI, SUB, BNG and SHR)? [8]
class Processor { // simulated 8-bit processor; two's complement
int
a, // accumulator
pc, // program counter
sp, // stack pointer
ir; // instruction register
boolean
z, // Z flag (last result was zero)
n, // N flag (last result was negative)
running; // running/halted
}
static Processor cpu = new Processor; // the processor itself
static int[] mem = new int[256]; // 256 bytes of simulated memory
static void setFlags(int x); // set condition flags
cpu.z = x == 0;
cpu.n = x >= 128;
} // setFlags
static void interpret () {
cpu.pc = 0;
cpu.a = 0;
cpu.sp = 0;
cpu.running = true;
while (cpu.running) {
cpu.ir = mem[cpu.pc++]; // fetch; bump program counter
switch (cpu.ir) { // dispatch; execute
case HLT : // halt
cpu.running = false; break;
case INI : // read integer from standard input
cpu.a = IO.readInt();
setFlags(cpu.a);
break;
case OTC : // write unsigned integer to standard output
IO.writeInt(cpu.a); break;
/* */ case OTI : // write signed integer to standard output
/* */ if (cpu.a <= 127) IO.writeInt(cpu.a);
/* */ else IO.writeInt(cpu.a - 256);
/* */ break;
case ADI : // add immediately to accumulator
cpu.a = (cpu.a + mem[cpu.pc++]) % 256;
setFlags(cpu.a);
break;
/* */ case SUB : // subtract variable from accumulator
/* */ cpu.a = (256 + cpu.a - mem[mem[cpu.pc++]]) % 256;
/* */ setFlags(cpu.a);
/* */ break;
case BRN : // unconditional branch
cpu.pc = mem[cpu.pc]; break;
/* */ case BNG : // conditional branch on negative
/* */ if (cpu.n) cpu.pc = mem[cpu.pc];
/* */ else cpu.pc++;
/* */ break;
/* */ case SHR : // shift accumulator right one bit
/* */ cpu.a = cpu.a / 2;
/* */ setFlags(cpu.a);
/* */ break;
}
}
} // interpret
It is worth noting that the use of cpu.pc++ in the above code is highly dangerous. If cpu.pc reached the value 255, then cpu.pc++ would take it to 256, which would be "out of range". It is left as an easy exercise to suggest how the code should be modified.