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]
Note that student number are 7 characters long. Sometimes they have a 6 prefix, to denote
"Grahamstown" as in 612A5345, or a G, as in G12A5345, to confuse the issue.
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 (executable) 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 in this example. We shall discuss such trees again in the weeks ahead.
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 might 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 (This is more of a "semantic" restriction, not syntactic.)
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 quirks of Java (and,
indeed of any language) that make the parsing process simpler. For example:
(b) each statement ends with a semicolon, and most start witha a key word;
(c) key words like while and for are reserved (unlike some other languages. believe it or not);
(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. 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;
VAR
Age, Loop : CARDINAL;
BEGIN
EasyIO.WriteString("Care to divulge your age?");
EasyIO.ReadCard(Age);
IF Age > 60 THEN
FOR Loop := Age TO 1 BY -3 DO
EasyIO.WriteString("Hello Pat, you old fool!")
END
END
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 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?
.--------------------------. .--------------------------. .--------------------------.
| ShortCareer.MOD | | | | |
| | | | | |
| Age --------->"hello" | | Age --------->"hello" | | Age --------->"hello" |
`-------. .--------------------------. .--------------------------. .-------'
| | XC.EXE | | BCC.EXE | |
| Mod-2 | Mod-2 ----------> C | C | C ----------> 8086 | 8086 |
| | | | | |
`------------------. .--------------------------. .------------------'
| | | | .----------.
| 8086 | | 8086 | | 8086 |
| | | | `----------'
`----------' `----------'
.----------. .----------.
| 8086 | | 8086 |
`----------' `----------'
7. The Modula program above was translated into C using the translator X2C, and produced the following:
#include "X2C.h"
#include "EasyIO.h"
static X2C_CARD16 ShortCareer_Age;
static X2C_CARD16 ShortCareer_Loop;
int main(int argc, char **argv) {
X2C_BEGIN(argc,argv);
EasyIO_BEGIN();
EasyIO_WriteString("Care to divulge your age?",26);
EasyIO_ReadCard(&ShortCareer_Age);
if ((ShortCareer_Age > 60U)) { /* FOR */
static X2C_CARD16 ShortCareer_V1;
ShortCareer_Loop = ShortCareer_Age;
if (ShortCareer_Loop >= 1U) {
ShortCareer_V1 = ((ShortCareer_Loop - 1U)) / 3;
for (;;) {
EasyIO_WriteString("Hello Pat, you old fool!", 25);
if (ShortCareer_V1 == 0) break;
--ShortCareer_V1;
ShortCareer_Loop -= 3;
}
}
} /* END FOR */
return 0;
}
Why do you suppose the X2C translation does not generate a much simple for loop than this? [2]
X2C has done this because the semantics of a FOR loop in Modula are subtly different from the semantics of the for loop in the C family of languages. We shall explore this in more detail in a later tutorial, perhaps, but for the moment note that X2C is obliged to translate the FOR loop in such a way that these semantics are rigidly copied - note, for example, the introduction of the "hidden" variable Short_Career_V1, which does not appear to correspond to any declared variable in the Modula-2 code.
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?).
Why do you suppose the X2C translation has introduced constants like 1U and 60U? [2]
X2C has done this because the CARDINAL type - an unsigned int in the C family - must be introduced, and, what is more, must be range checked (although this is not, perhaps, apparent in this silly example.
8. A reminder of the methods in the IntSet class appears below.
public class IntSet {
public IntSet()
public IntSet(BitSet s)
public IntSet(int ... members)
public void incl(int i)
public void excl(int i)
public boolean contains(int i)
public boolean isEmpty()
public int members()
public IntSet union(IntSet otherSet)
public IntSet intersection(IntSet otherSet)
public IntSet difference(IntSet otherSet)
public void write()
public String toString()
} // IntSet
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 IntSet class, 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. (Treat this as C# code if you would prefer, the two are virtually identical.) [5]
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);
}
}
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) {
IntSet Uncrossed = new IntSet(); // +++++++++
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);
}
}