1.

Box 1 shows part of the EBNF grammar of the programming language Fun.

Draw a full syntax tree for the following text, which is an expr .

(1 == 1) == (2 == 2) [4]

Explain why the following text is not an expr .

1 == 1 == 2 == 2 [2]

What simple change to the grammar would allow 1 == 1 == 2 == 2 to be an expr ? [2]

Extend the grammar so that it allows a do-while command, as illustrated by the following program.

proc main():

int x = 10

do

write(x)

x = x – 1

while x > 0 .

.

Your grammar should be flexible enough to allow reasonable programming with this form of loop; you should not limit it to supporting exactly this example program. [2]

Box 1 Part of the EBNF grammar of Fun.

(Here prog is a program, var-decl is a variable declaration,

com is a command, seq-com is a sequential command,

expr is an expression, prim-expr is a primary expression,

sec-expr is a secondary expression, id is an identifier,

and num is a numeral.)

2.

Explain the difference between a compiler and an interpreter. [2]

Give an example of a programming language system which does not fit the straightforward definition of either a compiler or an interpreter. [2]

The manager of a zoo is specifying software to record information about animals. The types Animal, Cage and Zoo are intended to correspond to the following sets of values.

Animal = { LION, ELEPHANT, CROCODILE }

Cage = Animal ×INT ×INT

Zoo = INT => Cage

The two INTs in Cage represent the length and width. The INT in Zoo represents the number of a cage within the sequence of all cages.

Give definitions in C or another programming language for  Animal, Cage and Zoo. [3]

The manager of the zoo is also thinking about using Java, and defines the following classes.

class Lion { boolean king; }

class Elephant { int weight; }

class Crocodile { int length; }

Give a mathematical definition of the set of objects in the program. [3]

Suppose that we have the following Java definitions, each in a separate file, which can be used to represent  abstract syntax trees for a simple language in which integer constants can be added together. Assume that all declarations are public.

abstract class Expr {

}

class Num extends Expr {

int value;

}

class Plus extends Expr {

Expr left, right;

}

Now consider the following method definition:

int evaluate(Expr e) {

if (e instanceof Num) {

Num n = (Num)e;

return n.value;

}

else { // e must be an instance of Plus

Plus p = (Plus)e;

return evaluate(p.left) + evaluate(p.right);

}

}

(i)         Explain what dynamic method dispatch means. [2]

(ii)        Rewrite the above class definitions so that if e is an instance of Expr, the method call

e.evaluate() evaluates it,  by taking advantage of dynamic method dispatch and without using instanceof or casting. [5]

(iii)       Why are the definitions and code in your answer to (ii) an improvement on the version in the

question? [3]

Implementation

(30 Marks)

3.

The front end of a compiler is separated into syntactic analysis and contextual analysis phases, and the         syntactic analysis phase is further separated into lexical analysis and parsing. Explain why it is structured in this way. [6]

What is produced by the syntactic analysis phase of a compiler, assuming that the input is syntactically correct? [1]

The ANTLR framework supports the use of the visitor pattern to implement the contextual analysis and code generation phases of a compiler. Explain how this works for the Fun language, highlighting           similarities and differences between contextual analysis and code generation. [8]

In Box 3a, the syntax of the Fun language has been extended with a repeat-command, which is a form of loop. The following Fun function illustrates a repeat-command.

int s = 0

int i = 1

repeat:

s = s + i

i = i + 1

until i > n .

return s

.

The semantics of the repeat-command is that first, the body of the loop is executed: in this case it is the   sequence of commands s = s + i followed by i = i + 1.  Then the condition, which must be a   boolean expression, is evaluated: in this case it is i > n. If the condition is true then that is the end of the loop. If the condition is false then execution jumps back to the beginning of the loop. The repeat-   command in the example function is equivalent to the following code:

s = s + i

i = i + 1

while i <= n:

s = s + i

i = i + 1

.

(i) Give the definition of the method that is needed to carry out contextual analysis of a repeat-command. [4]

(ii) Suppose that the repeat-command in the definition of the function sum above is incorrectly replaced by the following code.

repeat:

s = s + i

i = i + 1

until i + n .

Explain how the error is detected and reported by the Fun compiler. [2]

(iii) Complete the following definition of the method that is needed to carry out code generation for a repeat-command.

public Void visitRepeat(FunParser.RepeatContext ctx) {

//

// add code here

//

}

The method is part of the class FunEncoderVisitor, which has an instance variable obj. To help you, Box 3b contains a summary of part of the SVM instruction set. [5]

(iv) Assuming that s is a local variable at offset 0 and i is a local variable at offset 1, what is the SVM code generated for the following sequence of Fun commands?

s = s + i

i = i + 1 [4]

Box 3a Outline of an ANTLR grammar file.