EXAMINATION PAPER______CS5031___	MONTH____Jan 98_____
	QUESTION NUMBER__________1______	MARKING SCHEME

a.	a  |  b  | !  c  &  d  & ( !  e  |  f  )
	id |  id | !  id &  id & ( !  id |  id )
	not| not | ! not & not & ( ! not | not )
	and| and | _and_ & and & ( _and_ | and )
	 " |  "  |   "   &  "  & (  or   | or  )
	 " |  "  |   "   &  "  & (  exp  | "   )
	 " |  "  |   "   &  "  & (  ___exp___  )
	or |  "  |  or   &  "  & ______not______
	exp| or  |  ____or____ &       and
	___exp___|  __________or__________
	   _________exp_________			4 marks

b.	exps : exp | exps ';' exp ;			2 marks
					(1 mark if use ; as terminator)
c. yacc:

 %token true false				1 mark
 %%
 exp	: or_part | exp '|' or_part ;		1 mark for not messing
 or_part: and_part | or_part '&' and_part ;	up the grammar, except
 and_part: not_part | '!' not_part ;		for 'true' & 'false'
 not_part: id | true | false | '(' exp ')' ;

lex:
 %%
 true			return true;	}	1 mark
 false			return false;	}	+ 1 mark for preceding id
 [a-zA-Z_][a-zA-Z0-9_]*	return id;		1 mark
 [&|!()]		return yytext[0];	1 mark
 [ \t\n]		;			1 mark
 .			/* error */		1 mark - must be last

	IF you make a case for it, you can include true & false
	with id, as it makes no difference to the grammar.

d.
lex:	e.g. yylval.id_val=nextname(yytext); return id;		1 mark
yacc:
 %union {... id_val; ... tree;}				}
 %token <id_val> id					 }	1 mark
 %type <tree> exp or_part and_part not_part		}
 %%
 exp	: or_part		{$$=$1;}
	| exp '|' or_part	{$$=op2node($1,or,$3);}		2 marks
	;							for
 or_part: and_part		{$$=$1;}			reasonable
	| or_part '&' and_part	{$$=op2node($1,and,$3);}	code
	;
 and_part: not_part		{$$=$1;}
	| '!' not_part		{$$=op1node(not,$2);}
	;
 not_part: id			{$$=idnode($1);}
	| true			{$$=constnode(1);}
	| false			{$$=constnode(0);}
	| '(' exp ')'		{$$=$2;}
	;
outline of op2node, op1node, idnode, constnode, nextname	2 marks
(can combine idnode & nextname, or idnode & constnode, etc.)

	EXAMINATION PAPER______CS5031___	MONTH____Jan 98_____
	QUESTION NUMBER__________2______	MARKING SCHEME

lexical: group chars into words
	pairs = syntactic info, semantic info
	discard white space & comments
	put names into dictionary namelist
	e.g. lexemes, e.g. namelist

syntactic: group words into expressions etc.
	represent structure by parse trees
	e.g. parse trees

semantic: declarations -> dictionary property entries
	- deal with scope rules etc.
	- deal with type info
	check id kind (var/const/etc.) used correctly
	add kind, type, position info
	propagate type info thru trees, adding casts
	e.g. modified parse trees, e.g. dictionary

code generation & optimisation: registers used like stack?
	add code addresses for functions etc.
	optimisation of registers or some other simple e.g.

Marks:	1 per point like those above, given some details
	1 per lots of extra detail for a point
	1 per e.g. for given example code
	to maximum 15

5 marks I expect actual ARM code - you should include stack frames, but the
	example doesn't need to put variables on the stack. You can also use
	this as an example of some code optimisations, if you make the point
	explicitly.