This always changes as I mark the actual answers given.
Q1.(a)
',' is left-associative
but doesn't matter in a list of params in a decl [1]
%left ',' %% paramlist: paramlist ',' paramlist | type params ; params: params ',' params | id ;[1 for basic idea, +1 for exactly right]
(b) lex:
%{ #include "y.tab.h" %} [1]
%%
function {return FUNCTION;}
char {return CHAR;}
int {return INT;}
float {return FLOAT;}
OR return TYPE (& set yylval in part c) [1]
keywords must precede identifiers [1]
[A-Za-z][A-Za-z_]* {return id;}
[;,()] {return yytext[0];} [1]
[ \t\n] ;
. {yyerror("unenxpected char");} [1]
yacc:
%token id FUNCTION CHAR INT FLOAT [1]
%%
(tokens can't be: char int float !) [1]
declaration: FUNCTION type id '(' paramlist ')' ';'
(etc.) [1]
(c) lex:
... {yylval.an_id=savename(yytext); return id;} [1]
yacc:
%union {... a_node; ... an_id; ... a_type;} [1]
%type <an_id> id [1]
%type <a_node> declaration paramlist params
%type <a_type> type
... {$$= make_function ($2, $3, $5);} [1]
... {$$= make_paramlist ($1, $3);}
... {$$= add_type ($1, $2);}
... {$$= make_params ($1, $3);}
... {$$= $1;} /* can be omitted */
tree for example, EITHER sensible OR matching the code [1]
(d) LR(1) only looks 1 symbol ahead, so can't tell if a "type" (paramlist) or an "id" (param) follows a ',' [2]
replace ',' in paramlist by ';' + grammar [2]
OR forbid recursion in param + grammar
OR plist = type id | plist ',' id | plist ',' type id
Q2.(a)
scope = ... [1] extent = ... [1]
(b)
extents: lifetime of function (e.g. recursion), lifetime of program, malloc
to free/garbage collect
scopes: of program/file, of function, of block, record fieldnames,
modules - private v. public, start at block v. start at declaration
[each: basic .5, details .5, example .5, max 10]
(c) struct, typedef, fieldname, label [2]
Anything rational e.g. I think it is a bad idea because it makes programs hard to read and compile, but most languages overload fieldnames, and label/goto is distinct, and struct is needed in C for recursive definitions and is clear because of the extra keyword. [2]
(d)
If only one scope, each name has only 1 declaration
- at declaration, check no previous declaration
- at use, check for previous declaration
If multiple/nested scopes, each name may have many declarations
- at declaration, check no previous in same scope [1]
- at use, find most recent declaration [1]
- at end of scope, discard declaration [1]
If multiple declarations,
- at declaration, check no previous declaration of same kind in same scope [.5]
- at use, find most recent declaration of correct kind [.5]
Q3. Mainly bookwork, but brings together ideas from four or more separate lecture topics, and requires some insight into how they fit together and what the costs & payoffs are. e.g:
permitted index types: integer, other lower bounds: 0, 1, other permitted element types e.g. multi-D = many scalars, or vectors of vectors of ... initialisation literals, named constants, expressions, variables array assignment array comparison slicing are bounds part of type e.g. generic matrix functions how many dimensions may be varied bound checking possible, forced, optional call by value - is array copied? strings of characters, bits, ...? strings have fixed/user-defined/no maximum size string[0]==length, string[length]==0, etc. arrays static/dynamic size, bounds etc. size = #elements * element size access = origin + stride*index etc. multi-dimensional size, access, bound-checking extra information needed for e.g. flex array params, slicing, boundchecking
Marks: for each point .5=basic description, .5=extra details, .5=example, .5=implementation, .5=pros & cons etc., up to maximum 20
Q4.(a)
Dijkstra: concatenation i.e. ... [1] choice i.e. ... [1]
repetition i.e. ... [1] sufficient because ... [1]
others: function call [only worth 1 by itself]
completers & repeaters i.e. ... [2]
advantages & disadvantages [1]
(b)
infix/prefix/postfix [1] monadic/dyadic/... [1]
overloading e.g. - minus/sub, int/real [1]
precedence [1] left/right/non-associative [1]
lazy/eager [1] order of evaluation of operands [1]
(c)
strong typing [1] weak typing [1]
name equivalence [1] structure equivalence [1]
type coercions [1] widening [1] narrowing [1]
(d)
repetition: + * left/right recursion [1:lex, 1:yacc]
choice: | [ ] multiple BNF rules [1:lex, 1:yacc]
e.g. number = [0-9]+ -> BNF [1]
yacc more powerful because has call [1]
compiler grammar analysers = lexical + syntactic [1]