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, 2013
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, 2013
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();
} // while
} // 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 below is an even simpler 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#, I think)
StringBuilder sb = new StringBuilder(s);
return sb.reverse().toString();
} // reverse
} // PalinCheck
6. 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 INTEGER arithmetic used in Free Pascal (-32768 - 32767). Hence it appears to be the largest prime number that a 16-bit Sieve program can handle. Note that this is not the same as "the largest array" that a 16-bit Pascal compiler can handle. In fact one can do better than this - see the prac solution.
7. The program below gives (most of) the code for a simple interpreter that can react to a sequence of commands given to a "turtle" - for example the sequence
MOVE 10 TURNLEFT MOVE 10 TURNLEFT MOVE 10 TURNLEFT MOVE 10 TURNLEFT WHERE QUIT
will have the effect of tracing out a square of side 10, reporting that the turtle was back at (0, 0) and then stopping.
(a) Which lines of code can be said to perform "lexical analysis". Simply give the line number(s) (for example 17 - 18) but then briefly explain your choice. [3]
Lexical analysis is the phase where characters are assembled into tokens. In this program this happens in lines 21 and 24, where the IO method calls effectively do exactly that.
(b) Which lines of code can be said to perform "syntax analysis". Give the line number(s) (for example 17 - 18) but then briefly explain your choice. [3]
Syntax analysis is where tokens are combined to form recognizable sentences. In this program that effectively happens in lines 22 - 24 where the potential tokens read by the IO methods are compared with the key words to see whether they syntactically match the allowed commands for the turtle (and for interpretation).
(c) Fill in suitable code for the LEFT, RIGHT and MOVE operations. [3+3+6]
See below - lines 33 - 51. Notice that this code uses the names associated with the code wherever possible, and not some "magic numbers" directly. Note also that we are assuming a normal coordinate system with x and y measured positive to the right and up, respectively.
1 import library.*;
2
3 public class Turtle {
4 // Simple turtle interpreter
5
6 public static void main(String[] args) {
7 final int
8 East = 0, North = 1, West = 2, South = 3, // directions
9
10 Bad = 0,
11 Left = 1, Right = 2, Move = 3, Home = 4, Where = 5, Quit = 6; // operations
12
13 boolean running = true;
14
15 String[] code = { "", "turnleft", "turnright", "move", "home", "where", "quit" };
16
17 int direction = East;
18 double x = 0.0, y = 0.0, step = 0.0;
19
20 while (running) {
21 code[0] = IO.readWord().toLowerCase().trim();
22 int operation = Quit;
23 while (!code[0].equals(code[operation])) operation--;
24 if (operation == Move) step = IO.readDouble();
25 switch (operation) {
26 case Quit :
27 running = false; break;
28 case Where:
29 IO.write("Now at (x, y) = ("); IO.writeFixed(x, 1, 2);
30 IO.write(" , "); IO.writeFixed(y, 1, 2);
31 IO.writeLine(")");
32 break;
33 case Left :
34 if (direction == South) direction = East; else direction++;
35 // or, more neatly direction = (direction + 1) % 4;
36 break;
37 case Right :
38 if (direction == East) direction = South; else direction--;
39 // or, more neatly: direction = (direction + 3) % 4;
40 break;
41 case Move :
42 // we must now choose which coordinate to alter
43
44 switch (direction) {
45 case East : x += step; break;
46 case North: y += step; break;
47 case West : x -= step; break;
48 case South: y -= step; break;
49 } // switch
50
51 break;
52 case Home:
53 x = 0.0; y = 0.0; direction = East; break;
54 } // switch (operation)
55 } // while (running)
56 } // main
57
58 } // Turtle
(d) Look for simplicity, look for elegance - can you suggest a better way of recording the state of the turtle, and what impact would this have on the interpreter? (Full details are not required - nor is a whole OOP approach!) Hint: Consider how you might extend the possibilities for turning. [4]
The insight I was looking for is that, rather than have an enumeration of possible directions (which does not generalize without fairly major surgery to the code every time you have a New Idea), it is simpler to record the direction as an angle, measured in the usual way anticlockwise from the +x axis. School trigonometry then does the rest very easily. The code below shows this idea, as well as a few more enumerated special cases. Remember that you have to convert from the familiar "degrees" into "radians" before you can use the sine and cosine functions.
The "state" of the turtle is recorded in the three double variables x, y and direction. An improvement might be to package these into a struct or class type - but not, as some people suggested, an array. Why not?
import library.*;
public class Turtle3 {
// Simple turtle interpreter
// P.D. Terry, Rhodes University, 2013
public static void main(String[] args) {
final double
East = 0.0, // directions
deg90 = Math.PI / 2.0,
deg45 = Math.PI / 4.0;
final int
Bad = 0, // turtle operations
HalfLeft = 1, Left = 2, HalfRight = 3, Right = 4,
Turn = 5, Move = 6, Home = 7, Where = 8, Quit = 9;
boolean running = true;
String[] code = { "", "halfleft", "turnleft", "halfright", "turnright", "turn",
"move", "home", "where", "quit" } ;
double direction = East;
double x = 0.0, y = 0.0, step = 0.0;
while (running) {
code[0] = IO.readWord().toLowerCase().trim();
int operation = Quit;
while (!code[0].equals(code[operation])) operation--;
if (operation == Move) step = IO.readDouble();
if (operation == Turn) step = IO.readDouble() * Math.PI / 180.0;
switch (operation) {
case Quit :
running = false; break;
case Where:
IO.write("Now at (x, y) = ("); IO.writeFixed(x, 1, 2);
IO.write(" , "); IO.writeFixed(y, 1, 2);
IO.write(") Direction = ");
IO.writeFixed(direction * 180.0 / Math.PI, 1, 2); IO.writeLine();
break;
case HalfLeft :
direction += deg45; break;
case HalfRight :
direction -= deg45; break;
case Left :
direction += deg90; break;
case Right :
direction -= deg90; break;
case Turn :
direction += step; break;
case Move :
x += step * Math.cos(direction);
y += step * Math.sin(direction);
break;
case Home:
x = 0.0; y = 0.0; direction = East; break;
} // switch (operation)
} // while (running)
} // main
} // Turtle3