\documentclass{article}

\usepackage{hyperref}

\usepackage{amssymb}

\usepackage{amsmath}

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

\begin{document}

\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: