CS2112 June 1996 -- Answers and [marks]

Note - my marking scheme always changes as I mark the actual answers given.

Q1.

a. * is prefix, right associative [1]
[ ] postfix (maybe), left associative [1]
priority is ( ) [ ] then * [1]
( ) and [ ] can't clash, so can't really be separated

b. %right '*'

%left '[' ']'	(don't really need ']') [1]
%%
declarator : '*' declarator | id | '(' declarator ')'
	| declarator '[' number ']' | declarator '[' ']' ; [1]
(must merge rules) [1]

c. lex:

%{ #include "y.tab.h" %} [1]
%%
[0-9]+			{return number;} [1]

static			{return STATIC;}
typedef			{return TYPEDEF;}
char			{return CHAR;}
int			{return INT;}
float			{return FLOAT;} [1]

[A-Za-z][A-Za-z_]*	{return id;} [1]

\[			{return '[';}
\]			{return ']';}
[;*()]			{return yytext[0];} [1]

[ \t\n]			;
 .			{yyerror("unenxpected char");} [1]
(keywords must precede identifiers) [1]

yacc:

%token STATIC TYPEDEF CHAR INT FLOAT [1]
%%		(tokens can't be static typedef etc.) [1]
 ...
decl_spec : STATIC | TYPEDEF | ... [1]

d. e.g. "id1 id2 ;" [2]

(1)	id1 -> decl_spec -> decl_specs,
	id2 -> decl_spec + " -> decl_specs   
	';' + " -> declaration [1]

(2)	id1 -> decl_spec -> decl_specs,
	id2 -> direct_decl -> declarator,
	';' + " + " -> declaration [1]
(even if the example is wrong, get 1 mark for correct parse trees)

Q2.

a. array, struct/record, union [1]
nothing for pointer, RDT/list/tree etc.
set, file, etc -> later

pointers: low level, flexible, dangerous [1]
RDTs: high level, safe, hard to use for general graphs

set, file, bag, table etc. (Pascal, LID) [1]
might be useful sometimes, but excess baggage usually [1] (bonus marks for lots of description/discussion)

array: lower bound fixed/not, dynamic/static size, (1 of) sliceable, variable sized parameters, etc. [1]
+/-: flexibility v. cost [1]

union: discriminated/not [1]
+/-: strong type checking, GC [1]

pointer: to all/only anonymous variables, arithmetic, etc. [1]
+/-: flexibility (3 ref trick) v. (as union) [1]

struct: (fixed layout/bit fields/etc. ?) [bonus]

b. dictionary property/type entries:
created at declarations, [1]
e.g. of declaration(s) + dictionary [3]

lookup at use (exec/decl) [1]
e.g./discussion [2]

used for type checking * . [ ] -> etc. [1]
e.g./discussion [2]

Q3.

a. [marks - 1/2 for name, 1/2 for e.g./description]

Sequence: linear (;) [1]
non-linear (goto, call) [1]

Choice: one-way (if-then) [1]
two-way (if-then-else) [1]
multi-way (switch) [1]

Repetition: indeterminate loop (while, until) [1]
determinate loop (for) [1]
recursion [1]

Repeaters & Completers [bonus/see below]

Essential: 1 each of linear, non-linear, choice and repetition e.g. ; call if-then-else while [1]
- everything else can be constructed from them [1]
(or any similar, reasonable choice + explanation)

b.

statement : . . .
	| 'complete' block_name ';'
	| 'repeat' block_name ';'
	;
A block_name can be placed at the head of any control structure (e.g. if, switch, for, while, do) including block {...} [3]

Need name/#levels to get out of multiple structures or e.g. test in a loop - name is more flexible and gives a warning that something unusual is going on [1]

NB maybe want something like: [+1]

('complete'|'repeat') block_name 'on' condition ';'

e.g.	fred: { ... complete fred; ... }
or	bert: while (list)
	      {	 
	        if (list->value==test)
	          complete bert;
	        list= list->next;
	      }
[2]
which also shows how completers & repeaters can be misused to be just as confusing as spaghetti gotos! [+1]

Redundancies: [marks - 1/2 for mention, 1/2 for sensible comment]
goto - can be got rid of without loss of efficiency! [1]
break/continue - superfluous [not in switch!] [1]
return - maybe, but neater to keep it [1]
exit - ditto [1]
for/while/do - ditto [+1]
tail recursion - ditto [+1]

Q4.

a. scope = static/textual/compile-time existance [1/2]
extent = dynamic/run-time existance [1/2]
e.g.
(C) extent: auto, static, heap
(C) scope: global, local to function, to block, to struct/union, etc.
(FORTAN) e.g. common, equiv, save etc.
(COBOL) e.g. linkage, cancel, etc.
[1 each, max 6]
Note: I haven't discussed FORTRAN & COBOL in this much detail this year!

b. anything relevant e.g.
code-generation
tree-walking v. on-the-fly [1]
several variants, depending on CPU<->memory [1]
algorithm(s) (in detail) [3]
example code sequences [1]
code optimisation
tree-walk to label nodes with registers [1]
peephole e.g. don't reload registers [1]
global e.g. keep frequent vars in registers [1]
extra for examples, details etc. [+, max 7]

c. use parse trees for multiple passes e.g. interpret, optimise, complicated analysis [1]
concrete = contains all of source, exactly as grammar [1/2]
abstract = contains enough information to proceed [1/2]
e.g.
drop punctuation
discard spurious nodes with 1 child
need not distinguish similar nodes (e.g. term, exp)
need not forbid impossible trees (e.g. + -> *)
choose recursion
add information e.g. overloading, coercions
[1 per, max 5]

d. ADTs= user-defined types + operations + encapsulation [1]
e.g. [2]
types = struct, operations = functions, encapsulation != .h etc. [1]
advantages = encapsulation, disadvantages = none? [1]
Objects= ADTs + inheritance, dynamic binding, polymorphism [1]
explanations, consequences (e.g. reuse) [1]