\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{listings}
\usepackage{xcolor}


\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\begin{document}

\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
  
\lstdefinelanguage{scala}{
  morekeywords={abstract,case,catch,class,def,%
    do,else,extends,false,final,finally,%
    for,if,implicit,import,match,mixin,%
    new,null,object,override,package,%
    private,protected,requires,return,sealed,%
    super,this,throw,trait,true,try,
    type,val,var,while,with,yield},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}

\lstdefinelanguage{while}{
  morekeywords={while, if, then. else, read, write},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}


\lstset{language=Scala,
	basicstyle=\ttfamily,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javagreen},
	commentstyle=\color{javagreen},
	morecomment=[s][\color{javadocblue}]{/**}{*/},
	numbers=left,
	numberstyle=\tiny\color{black},
	stepnumber=1,
	numbersep=10pt,
	tabsize=2,
	showspaces=false,
	showstringspaces=false}



\section*{Coursework 2}

{\bf UPDATE:} There was a typo in Q1 about the regular expressions for comments:
they should, of course, start with $\slash\slash$, as in C for example, not with 
$\backslash\backslash$. (Thanks to Bryan who pointed out this error.)\bigskip\bigskip

\noindent
This coursework is worth 3\% and is due on 29 November at 16:00. You are asked to 

\begin{enumerate}
\item implement a tokeniser for the WHILE language,
\item implement a parser and an evaluator for boolean and arithmetic expressions, and
\item write a WHILE program for printing out prime numbers.
\end{enumerate}

\noindent
You need to submit a document containing the answers for the questions 
below. You can do the implementation in any programming language you like, but you need 
to submit the source code with which you answered the questions. However, the coursework 
will \emph{only} be judged according to the answers. You can submit your answers
in a txt-file or as pdf.\bigskip


\subsection*{Question 1 (marked with 1\%)}

Implement a tokeniser for the WHILE language. You first need to design the appropriate
regular expressions for the following nine syntactic entities:

\begin{enumerate}
\item keywords are

\begin{quote}
\texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}
\texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}
\end{quote} 

\item operators are

\begin{quote}
\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}
\end{quote} 

\item strings are enclosed by \texttt{"\ldots"} 
\item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}
\item there are semicolons \texttt{;}
\item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}
\item comments either start with $\slash\,\slash$ and run to the end of the corresponding line 
(indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by
$\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker
\item identifiers are letters followed by underscores \texttt{\_\!\_}, letters
or digits
\item numbers are \texttt{0}, \text{1}, \ldots
\end{enumerate}

\noindent
Once you have implemented all regular expressions for 1 - 9, then
give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.

\subsection*{Question 2 (marked with 1\%)}

Implement parser combinators and an evaluation function for arithmetic and boolean
expressions.  Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and 
\texttt{\%} (quotient). Boolean
operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and  
\texttt{>}.
 
Using the parser and evaluation function, calculate the values for

\begin{itemize}
\item \texttt{17 < 3 * 3 * 3}
\item \texttt{(29 - 20) * 3}
\item \texttt{79 - 20 * 3}
\item \texttt{2 * 2 != 12 \% 3}
\end{itemize} 
 
\subsection*{Question 3 (marked with 1\%)}

Write a program in the WHILE programming language that prints out all prime numbers between
0 and a fixed number (say 100). A partial grammar of the WHILE language is given below. 

\begin{center}
\begin{tabular}{@{}lcl@{}}
\textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\
              & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
              & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
              & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
              & $|$ & \texttt{read}\;\textit{Id}\\
              & $|$ & \texttt{write}\;\textit{Id}\\
              & $|$ & \texttt{write}\;\textit{String}\medskip\\
\textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
              & $|$ & \textit{Stmt}\medskip\\
\textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
                & $|$ & \textit{Stmt}\medskip\\
\textit{AExp} & $\rightarrow$ & \ldots\\
\textit{BExp} & $\rightarrow$ & \ldots\\
\end{tabular}
\end{center}

\noindent
As another guidance for your program have a look at the Fibonacci program
and ``three-nested-loops'' program shown below in Figures \ref{fib} and \ref{loop}. 


\begin{figure}[h]
\begin{center}
\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
\end{center}
\caption{Fibonacci program in the WHILE language.\label{fib}}
\end{figure}

\begin{figure}[h]
\begin{center}
\mbox{\lstinputlisting[language=while]{../progs/loops.while}}
\end{center}
\caption{The three-nested-loops program in the WHILE language. Usually used for timing measurements.\label{loop}}
\end{figure}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: