This should take no longer than 25 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. Student name and student number!
2. Very briefly - 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 18 - 21 of the text.
3. Translators can be classified in various ways - for example, compilers, assemblers, decompilers, disassemblers, high level compilers, interpretive compilers, pretty printers. Complete the following table, which classifies various of the tools you (should have!) used in Practical 19. The first row has been done for you. [10]
Considering that you were supposed to have used these tools and that the classification effectively appeared on the prac sheet, this was very badly done. Several people were clearly simply guessing, or writing the first thing that came to mind. What I wanted was something like this:
.-------------------------------------------------------------------------------. | name | translator class | source code | object code | |--------+------------------+----------------------+----------------------------| | javac | compiler | Java source | Java class files | |--------+------------------+----------------------+----------------------------| | bcc | compiler | C or C++ source | Pentium executable | |--------+------------------+----------------------+----------------------------| | jad | decompiler | Java class file | Java source | |--------+------------------+----------------------+----------------------------| | ilasm | assembler | CIL assembler source | .NET Assembly | |--------+------------------+----------------------+----------------------------| | oolong | assembler | JVM assembler | Java class file | |--------+------------------+----------------------+----------------------------| | parva | interpretive | Parva source | PVM pseudo code | | | compiler | | | |--------+------------------+----------------------+----------------------------| | fpc | compiler | Pascal source | Pentium executable | |--------+------------------+----------------------+----------------------------| | gnoloo | disassembler | Java class file | JVM assembler source | |--------+------------------+----------------------+----------------------------| | jikes | compiler | Java source | Java class files | |--------+------------------+----------------------+----------------------------| | ildasm | disassembler | .NET assembly | CIL assembler source | |--------+------------------+----------------------+----------------------------| | xc | high level | Modula-2 source | C source files | | | compiler | | | `-------------------------------------------------------------------------------'
4. Explain very simply what you understand by lexical analysis and what you understand by syntax analysis. [4]
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 18-20 of the text. Most answers here were very confused and suggested that students had simply not read the text at all.
5. What is the significance of the number 16411 and why? [2]
16411 is the smallest prime number for which the first multiple (32822) is outside the range of the 16 bit arithmetic used in Free Pascal (-32768 - 32767). Hence it appears to be the largest prime number that the 16-bit Sieve program can handle. Note that this is not the same as "the largest array" that the 16-bit compiler can handle. In fact one can do better than this - see the prac solution.
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. [4]
.--------------------------. .--------------------------. .--------------------------.
| 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. Consider the silly Modula program below, along with its translation into C performed using the translator X2C. (Even if you are not expert in Modula the intent of this piece of code should be pretty obvious.)
Why do you suppose the X2C translation makes so much of the assignment statement List[I] := I + 10 ? [2]
There are two points - firstly it is doing "range checking" to ensure that the value assigned to List[I-5] is correctly within the range 5 to 15. Those of you who have grown up in the unprotected world of C++ have never learnt how useful this sort of check can be when debugging programs, unfortunately. Secondly, it has had to map the subscripts 5 ... 15 to 0 ... 10.
Why do you suppose the X2C translation has introduced such long-winded variable names? [2]
X2C has done this so as to try to ensure that "name clashes" do not arise in the C++ code that is produced. Each name has been synthesized from the "simple" name and the "module name" - this may make for long identifiers but helps programmers and compilers identify whence they have come (quickly - if I gave you a piece of C++ code with a function call to a function called offsetof, which library does it come from?).
MODULE Silly;
TYPE
SUBSCRIPTS = INTEGER [5 .. 15];
VAR
I, J : SUBSCRIPTS;
List : ARRAY SUBSCRIPTS OF SUBSCRIPTS;
BEGIN
FOR I := 5 TO J DO List[I] := I + 10 END
END Silly.
#include "X2C.h"
typedef X2C_INT16 Silly_SUBSCRIPTS;
static Silly_SUBSCRIPTS Silly_I;
static Silly_SUBSCRIPTS Silly_J;
typedef Silly_SUBSCRIPTS Silly_ANONYM1[11];
static Silly_ANONYM1 Silly_List;
int main(int argc, char **argv) /* translation by X2C */
{ X2C_BEGIN(argc, argv);
static Silly_SUBSCRIPTS Silly_V1;
Silly_I = 5;
Silly_V1 = Silly_J;
if (Silly_I <= Silly_V1) {
for (;;) {
Silly_List[(X2C_INT16) Silly_I - 5] = (X2C_INT16) X2C_CHK((Silly_I + 10), 5, 15);
if (Silly_I == Silly_V1) break;
++Silly_I;
}
}
return 0;
}
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
SHL ; shift left
SBI 12 ; subtract 12
BPZ POS ; if positive output as unsigned number
NEG OTI ; else output as signed number
BRN EXIT ;
POS OTC ;
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, SBI, BPZ and SHL)? [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 SBI : // subtract immediately from accumulator
/* */ cpu.a = (256 + cpu.a - mem[cpu.pc++]) % 256;
/* */ setFlags(cpu.a);
/* */ break;
case BRN : // unconditional branch
cpu.pc = mem[cpu.pc]; break;
/* */ case BPZ : // conditional branch on positive or zero
/* */ if (!cpu.n) cpu.pc = mem[cpu.pc];
/* */ else cpu.pc++;
/* */ break;
/* */ case SHL : // shift accumulator left one bit
/* */ cpu.a = (2 * cpu.a) % 256;
/* */ 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.