This should take no longer than 30 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).
1. You should get this right! Mine is Pat Terry, 63T0844. What is yours? [1]
Pat Terry, 63T0844
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. How might a concrete syntax tree differ from an abstract syntax tree? Illustrate by suggesting what these trees might look like for the statement [5]
if (i > 10) i = 10;
A concrete syntax tree contains all the tokens of each statement in its leaves. An abstract syntax tree discards all but the essential information needed for the back end to be able to synthesize object code. There isn't a huge amount of difference!
Concrete: Abstract:
IfStatement IfStatement
| |
.--------------+---------------------. .---------------------.
| | | | | | |
if ( Expression ) Statement Expression Statement
| | | |
.---+---. | .---+---. |
| | | | | |
Assignment Assignment
Term < Term | i < 10 |
| | .----------------------. .------------------.
| | | | | |
Target Assign Expression
i 10 Target = Expression ; |
| | | |
i Term i 10
|
10
5. Suggest, with brief reasons, three features of Java syntax that you suggest have been defined in the way they are so as to make the compilation of Java programs simpler than it might otherwise be. [3]
(a) variables must be declared before use
Some submissions confused "make life easier for the compiler" with "make it easier to develop and
debug programs". It's not quite the same thing. In fact, it probably complicates a compiler to arrange
for it to insert run-time error checks and so on. But there are definite little quircks of Java (and,
indeed of any language) that make the parsing process simpler. For example:
(b) each statement ends with a semicolon
(c) key words
(d) case sensitive identifiers
(e) while and do-while and if statements parenthesize their Boolean expressions
(f) no goto statements other than break
(g) operators like ++, += and so on suggest particularly efficient code sequences
(h) source code requires white space to appear between "word" tokens like "public static void main"
where there are no other recognizable delimiters.
6. Some C compilers achieve their goals by compiling first to assembly code and then using a complementary assembler to finish the job. (GCC can work in this way, I understand). Complete the T diagram representation of how such an arrangement would handle the compilation of a simple program. [5]
.--------------------------. .--------------------------. .--------------------------.
| Simple.C | | Simple.ASM | | Simple.EXE |
| | | | | |
| Input --------> Output | | Input --------> Output | | Input --------> Output |
`-------. .--------------------------. .--------------------------. .-------'
| | CtoASM.EXE | | ASMto8086.EXE | |
| | | | | |
| C | C ---------> ASM | ASM | ASM ---------> 8086 | 8086 |
`------------------. .--------------------------. .------------------'
| | | |
| 8086 | | 8086 |
| | | |
`----------' `----------'
.----------. .----------.
| 8086 | | 8086 |
`----------' `----------'
7. Here's a really simple Parva program - the sort you might find a first year student writing:
bool b(int n) {
return n == i(n);
}
int i(int n) {
int r = 0;
while (n != 0) {
r = 10 * r + n % 10;
n = n / 10;
}
return r;
}
void main() {
int n;
read("Supply n (0 stops) ", n);
while (n != 0) {
write(b(n));
read(n);
}
}
Simplicity is sometimes deceptive!
So it appeared! It was depressing how few people could "decode" this simple algorithm. Have you not learned how to "play computer".
(a) What do you suppose the program is meant to achieve? [2]
It reads a list of integers and tells you whether each is a palindrome (like 12321 or 44 or 686)
(b) Suggest better names for the identifiers used for the functions/methods. [2]
Function b would be better named isPalindrome
Function i would be better named reverse
(c) Why will this code not compile? [2]
Because in Parva all identifiers, even methods, must be declared before use, and because there is no
% operator - as you should have discovered in the recent prac. In fact many submissions recognized
this, but I don't know that anyone spotted that the "declare before use" requirement" had not been
met. Surely you knew this from the Parva programs you had been asked to write? There were some
interesting wrong answers (guesses). One does not need parentheses around the expression in a
return statement, for example.
(d) How could you correct it so that it would compile and execute satisfactorily? No, you don't have to rewrite it completely. The answer is very simple! [2]
int reverse(int n) {
// Returns the number formed by reversing the decimal digits of n
int r = 0;
while (n != 0) {
r = 10 * r + n - n / 10 * 10; // order important!
n = n / 10;
}
return r;
}
bool isPalindrome(int n) {
// Returns true if and only if n is a decimal palindrome like 123231
return n == reverse(n);
}
void main() {
// Examines a list of integers to see which are palindromes
int n;
read("Supply n (0 stops) ", n);
while (n != 0) {
write(isPalindrome(n));
read(n);
}
}
(e) What do you suppose is the Big Idea I am trying to get across to you in this question? [1]
That all programs should have adequate commentary and well chosen identifiers. I am sure that had
I added commentary and given the methods decent names you would immediately have "understood"
what was intended.
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
SUB AGE ; subtract value stored at AGE
BZE EXIT ;
OTI ; if non-zero, output as unsigned number
EXIT HLT ; terminate execution
AGE DC 64 ; now you know
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, and BZE and correct the arm for INI which may look correct, but is not) [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();
/* */ cpu.a = (cpu.a % 256 + 256) % 256; // force into range (including negative)
setFlags(cpu.a);
break;
case OTC : // write unsigned integer to standard output
IO.write(cpu.a);
break;
case OTI : // write signed integer to standard output
/* */ if (cpu.a <= 127) IO.writeInt(cpu.a);
/* */ else IO.write(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 BZE : // conditional branch on zero
/* */ if (cpu.z) cpu.pc = mem[cpu.pc];
/* */ else cpu.pc++;
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.
This question was very badly answered, which was disappointing, considering that we had discussed the little machine briefly in class. Several people confused it with a stack machine, for example.
Admittedly the tricks one needs to ensure that the value of CPU.A remains on the range 0..255, and that the range 128..255 represents "negative" values, are a little obtuse. Study the solution carefully, and if you don't understand any of it, come to ask. Many submissions had SUB badly wrong - they were close to SBI not to SUB, and I don't know that anyone had worked out how to get the negative result properly mapped. The code for SBI would have been
case SBI : // subtract variable from accumulator
/* */ cpu.a = (256 + cpu.a - mem[cpu.pc++]) % 256;
setFlags(cpu.a);
break;
Another common mistake was to write
case BZE : // conditional branch on zero
/* */ if (cpu.a == 0) cpu.pc = mem[cpu.pc];
else cpu.pc++;
break;
But in this system BZE acts on the value of the last calculation, not on the value in the accumulator (which does not always hold the value of the last calculation - remember the DEX and CMP opcodes for example?