afl-material: coursework/cw02.tex@50e8dcd95ae3 (annotated)

178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	1	\documentclass{article}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	2	\usepackage{charter}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	3	\usepackage{hyperref}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	4	\usepackage{amssymb}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	5	\usepackage{amsmath}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	6	\usepackage{listings}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	7	\usepackage{xcolor}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	8
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	9
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	10	\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	11	\begin{document}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	12
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	13	\definecolor{javared}{rgb}{0.6,0,0} % for strings
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	14	\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	15	\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	16	\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	17
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	18	\lstdefinelanguage{scala}{
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	19	morekeywords={abstract,case,catch,class,def,%
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20	do,else,extends,false,final,finally,%
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21	for,if,implicit,import,match,mixin,%
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	22	new,null,object,override,package,%
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	private,protected,requires,return,sealed,%
179 d575895689b5 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 178 diff changeset	24	super,this,throw,trait,true,try,
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	25	type,val,var,while,with,yield},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	26	otherkeywords={=>,<-,<\%,<:,>:,\#,@},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27	sensitive=true,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	28	morecomment=[l]{//},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29	morecomment=[n]{/}{/},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	morestring=[b]",
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	31	morestring=[b]',
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	32	morestring=[b]"""
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	33	}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	34
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	35	\lstdefinelanguage{while}{
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	36	morekeywords={while, if, then. else, read, write},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	37	otherkeywords={=>,<-,<\%,<:,>:,\#,@},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	38	sensitive=true,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	39	morecomment=[l]{//},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	40	morecomment=[n]{/}{/},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	41	morestring=[b]",
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	42	morestring=[b]',
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	43	morestring=[b]"""
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	44	}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	45
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	46
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	47	\lstset{language=Scala,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	48	basicstyle=\ttfamily,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	49	keywordstyle=\color{javapurple}\bfseries,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	50	stringstyle=\color{javagreen},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	51	commentstyle=\color{javagreen},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	52	morecomment=[s][\color{javadocblue}]{/*}{/},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	53	numbers=left,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	54	numberstyle=\tiny\color{black},
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	55	stepnumber=1,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	56	numbersep=10pt,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	57	tabsize=2,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	58	showspaces=false,
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	59	showstringspaces=false}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	60
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	61
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	62
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	63	\section*{Coursework 2}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	64
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	65	This coursework is worth 3\% and is due on 27 November at 16:00. You are asked to
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	66
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	67	\begin{enumerate}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	68	\item implement a tokeniser for the WHILE language,
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	69	\item implement a parser and an evaluator for boolean and arithmetic expressions, and
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	70	\item write a WHILE program for printing out prime numbers.
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	71	\end{enumerate}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	72
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	73	\noindent
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	74	You need to submit a document containing the answers for the questions
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	75	below. You can do the implementation in any programming language you like, but you need
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	76	to submit the source code with which you answered the questions. However, the coursework
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	77	will \emph{only} be judged according to the answers. You can submit your answers
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	78	in a txt-file or as pdf.\bigskip
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	79
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	80
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	81	\subsection*{Question 1 (marked with 1\%)}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	82
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	83	Implement a tokeniser for the WHILE language. You first need to design the appropriate
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	84	regular expressions for the following nine syntactic entities:
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	85
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	86	\begin{enumerate}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	87	\item keywords are
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	88
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	89	\begin{quote}
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	90	\texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	91	\texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	92	\end{quote}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	93
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	94	\item operators are
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	95
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	96	\begin{quote}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	97	\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	98	\end{quote}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	99
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	100	\item strings are enclosed by \texttt{"\ldots"}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	101	\item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	102	\item there are semicolons \texttt{;}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	103	\item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	104	\item comments either start with $\backslash\,\backslash$ and run to the end of the corresponding line
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	105	(indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	106	$\slash\texttt{}$ as the beginning marker and $\texttt{}\slash{}$\smallskip as the end marker
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	107	\item identifiers are letters followed by underscores \texttt{\_\!\_}, letters
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	108	or digits
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	109	\item numbers are \texttt{0}, \text{1}, \ldots
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	110	\end{enumerate}
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	111
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	112	\noindent
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	113	Once you have implemented all regular expressions for 1 - 9, then
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	114	give the token sequence for the Fibonacci program shown below.
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	115
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	116	\subsection*{Question 2 (marked with 1\%)}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	117
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	118	Implement parser combinators and an evaluation function for arithmetic and boolean
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	119	expressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	120	\texttt{\%} (quotient). Boolean
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	121	operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	122	\texttt{>}.
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	123
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	124	Using the parser and evaluation function, calculate the values for
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	125
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	126	\begin{itemize}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	127	\item \texttt{17 < 3 * 3 * 3}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	128	\item \texttt{(29 - 20) * 3}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	129	\item \texttt{79 - 20 * 3}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	130	\item \texttt{2 * 2 != 12 \% 3}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	131	\end{itemize}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	132
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	133	\subsection*{Question 3 (marked with 1\%)}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	134
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	135	Write a program in the WHILE programming language that prints out all prime numbers between
180 50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	136	0 and a fixed number (say 100). Take the grammar of this language from the lectures. As another
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	137	guidance have a look at the Fibonacci program
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	138	and ``three-nested-loops'' program shown below. For example, printing a variable \texttt{x} in the
50e8dcd95ae3 added cw Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 179 diff changeset	139	WHILE language can be done by using the command \mbox{\texttt{write x}}.
178 d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	140
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	141
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	142	\begin{center}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	143	\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	144	\end{center}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	145
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	146	\begin{center}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	147	\mbox{\lstinputlisting[language=while]{../progs/loops.while}}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	148	\end{center}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	149
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	150
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	151	\end{document}
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	152
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	153	%%% Local Variables:
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	154	%%% mode: latex
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	155	%%% TeX-master: t
d36363d648e3 added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	156	%%% End:

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Sun, 03 Nov 2013 11:10:07 +0100
changeset 180	50e8dcd95ae3
parent 179	d575895689b5
child 181	1f98d215df71
permissions	-rw-r--r--