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]
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]