1.     Syntax

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

Suppose that Fun is to be extended with C-style struct definitions. A struct consists of a collection of fields of arbitrary types; there must be at least one field. The following program illustrates the required extension.

struct date { int day; int month; int year; }

func bool isChristmas(struct date d):

if d.day <> 25:

return false .

if d.month <> 12:

return false .

return true

.

proc main():

struct date theDate = { 0, 0, 0 }

theDate.day = read()

theDate.month = read()

theDate.year = read()

if isChristmas(theDate):

write(1) .

.

The declaration struct date {…} defines a type called struct date. A value of type struct date has integer fields called day, month and year, which can be accessed and modified by using syntax such as d.day. An expression such as {24,2,2015} creates a struct with initial values.

Modify the grammar to allow for the required extension.

The grammar should allow for a series of struct declarations or field accesses. [10]

Box 1  Parts 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.     Concepts

Discuss the  different  categories of  types you  studied  in the  course, by defining  and comparing them with each other.

Use the different categories of types to write a Java program on Polygons, following the guidelines below. Add your own fields and methods to the classes as you see fit to complete the program.

Polygon is an abstract class declaring the following three fields: perimeter, surface and has_diagonal. Other geometric figures such as Triangle, Rectangle, Rhombus etc., extend Polygon and each may declare new fields and define new methods, typical of these figures.

In your program you should:

i.      Use all the categories of types you discussed.

ii.      Comment on each category.

iii.      Define the equationfor the set of objects in the program. [20]

3.     Implementation

(a) Suppose that the Fun language is to be extended with a do-while-command such as the

following:

do :

p = p*2

g = g+1

while p < n

The  syntax  should  allow  any  sequential  command  between  ‘:’  and  ‘while’ .  The semantics should be to execute the sequential command repeatedly until the expression following ‘while’ yields false. (The expression is to be evaluated after the sequential command is executed.)

(i)     Show how the file of Box 2 should be modified to achieve this extension.

(ii)    Give the definition of the method that is needed to carry out contextual analysis

of a do-while-command

(iii)   Give a code template suitable for code generation for a do-while-command.

(iv)   Give the definition of the method that is needed to carry out code generation for

a do-while-command. [16]

Box 2  Outline of an ANTLR grammar file.

(b) Consider the memory configuration below

Stack

Heap

Draw  diagrams  showing  how  the  heap  evolves  after  each  of the  following  four commands is executed

allocate e

e.left = b

e.right = c

deallocate a

Assume e fits into the free space and e has two pointer attributes, left and right. [4]

(c) Consider the memory configuration below

Stack

Heap

By means of diagrams, show step-by-step how the heap is affected by the execution of a mark-sweep garbage collector. [5]

(d) Consider the memory configuration below

Stack

Space 1

Heap

Space 2