COMPSCI 4016 Programming Languages 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Monday 10 May 2021
Programming Languages H
COMPSCI 4016
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]
prog = var-decl * proc_decl+ eof proc_decl = … var-decl = type id ‘=’ expr type = ‘bool’ | ‘int’ com = id ‘=’ expr | ‘if’ expr ‘ : ’ seq-com ‘ . ’ | … seq-com = com * expr = sec-expr ( (‘==’ | ‘<’ | ‘>’ | ‘!=’) sec-expr ) ? sec-expr = prim-expr ( ( ‘+’ | ‘- ’ | ‘*’ | ‘/’ ) prim-expr ) * prim-expr = ‘false’ | ‘true’ | num | id | ‘(’ expr ‘)’ | …
… |
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]
grammar
… |
Fun |
com : ID ASSN expr | IF expr COLON seq_com | … ; seq_com : com* ; |
|
…
IF : ‘if’ ; ID : LETTER+ ; ASSN : ‘=’ ; COLON : ‘:’ ; … |
Box 2 Outline of an ANTLR grammar file.
(b) Consider the memory configuration below
Stack
Heap
a
|
b |
c |
d
|
Free |
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
|
|
|
|
|
|
|
Free |
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
|
|
|||||
|
|
|
|
|
|
Free |
|
|
By means of diagrams, show step-by-step how the heap is affected by the execution of a copying garbage collector. [5]
2023-05-08