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! And it is genuine. Note that your student number normally just has two digits (63) for the year of first registration, the initial letter of the surname, and a four digit number for the number of applications that had been received when yours was processed. the number is often quoted with a further leading 6 (as in 663T0844), but this is a hangover from the days when we had campus 6 (Grahamstown) and campus 8 (East London). No, I don't know, so don't ask!
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 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 the terms syntax, static semantics, and dynamic semantics, and what distinguishes one from another. [6]
Syntax rules describe the arrangement or form that program source, statements and expressions can take or in which they can be combined (for example, in Java source code a while statement requires a parenthesized expression and another statement to follow the parentheses). Static semantic rules relate to the way in which types, expressions identifiers and so on interact (for example, in a while statement the parenthesized expression must be one composed of operands and operators that not only satisfy syntactic rules, but which also evaluates to a Boolean result). Dynamic semantics describe what happens when the program (or statement) executes (for example, in the case of a while statement the subsidiary statement will be executed, possibly repeatedly, for as long as a re-evaluation of the expression yields a Boolean value of true).
5. A programmer has been set the following task: Read a text file of sentences (one per line) and determine which of them are palindromes (palindromes are sentences that read the same from either end, like "otto sees otto").
The first hack has got as far as this, and the deadline looms.
// Check a file for lines that might contain palindromes
// Ima Boff, Rhodes University, 2011
import java.util.*;
import library.*;
class PalinCheck {
public static void main(String[] args) {
// first check that commandline arguments have been supplied
if (args.length != 2) {
System.out.println("Usage: PalinCheck inputfile outputfile");
System.exit(1);
}
// attempt to open data file
// still have to do this
// attempt to open results file
// still have to do this
// read and process data file
while (true) {
// must find out how to read a string
String s =
results.write(s); // reflect on output
// not sure about this if statement - wonder who can fix it?
if (I did not find a string) break;
String r = reverse(s.toLowerCase()); // should ignore case
if r.equals(s) results.writeLine(" is a palindrome")
}
} // main
static String reverse(String s) {
// returns a string formed by reversing s
// for example if s = "hello world", returns "dlrow olleh"
StringBuilder sb = new StringBuilder();
// Must steal this code from somebody soon!!
return sb.toString();
} // reverse
} // PalinCheck
Show how to complete the program using the routines you should have become familiar with this week. Simply add the missing code - don't write it all out again. [12]
This was not very well done, which was disappointing - it indicated that many people had not studied the sample file handling code given to you, or knew how to make use of the library routines.
Points to note:
// Check a file for lines that might contain palindromes
// Ima Boff, Rhodes University, 2011
import java.util.*;
import library.*;
class PalinCheck {
public static void main(String[] args) {
// first check that commandline arguments have been supplied
if (args.length != 2) {
System.out.println("Usage: PalinCheck inputfile outputfile");
System.exit(1);
}
// attempt to open data file
InFile data = new InFile(args[0]);
if (data.openError()) {
System.out.println("cannot open " + args[0]);
System.exit(1);
}
// attempt to open results file
OutFile results = new OutFile(args[1]);
if (results.openError()) {
System.out.println("cannot open " + args[1]);
System.exit(1);
}
// read and process data file
while (true) {
String s = data.readLine();
results.write(s); // reflect on output
if (data.noMoreData()) break;
s = s.toLowerCase(); // should ignore case
String r = reverse(s);
if (r.equals(s)) results.writeLine(" is a palindrome");
else results.writeLine();
}
} // main
static String reverse(String s) {
// returns a string formed by reversing s
// for example if s = "hello world", returns "dlrow olleh"
/* This is the sort of code I was looking for
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1 ; i >= 0; i--)
sb.append(s.charAt(i));
return sb.toString();
*/
// But this is the simplest way to do it in Java, making use of a method
// that was not mentioned on the original web page summary (no equivalent for C#)
StringBuilder sb = new StringBuilder(s);
return sb.reverse().toString();
} // reverse
} // PalinCheck
6. What is the essential difference between a concrete syntax tree and an abstract syntax tree? [2]
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!
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);
} // b
int i(int n) {
int r = 0;
while (n != 0) {
r = 10 * r + n % 10;
n = n / 10;
}
return r;
} // i
void main() {
int n;
read("Supply n (0 stops) ", n);
while (n != 0) {
write(b(n));
read(n);
}
} // main
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 would this code not compile with the Parva compiler you have been using? [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;
} // reverse
bool isPalindrome(int n) {
// Returns true if and only if n is a decimal palindrome like 123231
return n == reverse(n);
} // isPalindrome
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);
}
} // main
(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. What is the significance of the number 16411 and why? [3]
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.