\documentclass{article}
\usepackage{../style}
\usepackage{../langs}

\begin{document}

\section*{Coursework 3}

\noindent This coursework is worth 5\% and is due on 23
November at 18:00. You are asked to implement a parser for the
WHILE language and also an interpreter. 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, otherwise a mark of 0\% will be awarded. You should
use the lexer from the previous coursework for the parser. 

\subsection*{Disclaimer}

It should be understood that the work you submit represents
your own effort. You have not copied from anyone else. An
exception is the Scala code I showed during the lectures,
which you can use. You can also use your own code from the
CW~1 and CW~2.


\subsection*{Question 1}

Design a grammar for the WHILE language and give the grammar
rules. The main categories of non-terminals should be:

\begin{itemize}
\item arithmetic expressions (with the operations from the
  previous coursework, such as \pcode{+}, \pcode{*} and so on)
\item boolean expressions (such as \pcode{<}, \code{!=} and 
  so on)
\item single statements (such as \pcode{skip}, assignments, \pcode{if}s,
  \pcode{while}-loops and so on)
\item compound statements separated by semicolons
\item blocks which are enclosed in curly parentheses
\end{itemize}

\subsection*{Question 2}

You should implement a parser for the WHILE language using
parser combinators. Be careful that the parser takes as input
a stream, or list, of tokens generated by the tokenizer from
the previous coursework. For this you might want to filter out 
whitespaces and comments. Your parser should be able to handle
the WHILE programs in Figures~\ref{fib} and \ref{loop}.
In addition give the parse tree for the statement:

\begin{lstlisting}[language=While,numbers=none]
if (a < b) then skip else a := a * b + 1
\end{lstlisting}

\noindent
A (possibly incomplete) datatype for parse trees in Scala would
look as in Figure~\ref{trees}.

\begin{figure}
\begin{lstlisting}[language=Scala]
abstract class Stmt
abstract class AExp
abstract class BExp 

type Block = List[Stmt]

case object Skip extends Stmt
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
case class While(b: BExp, bl: Block) extends Stmt
case class Assign(s: String, a: AExp) extends Stmt

case class Var(s: String) extends AExp
case class Num(i: Int) extends AExp
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp

case object True extends BExp
case object False extends BExp
case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
\end{lstlisting}
\caption{The datatype for parse trees in Scala.\label{trees}}
\end{figure}

\subsection*{Question 3}

Implement an interpreter for the WHILE language you designed
and parsed in Question 1 and 2. This interpreter should take
as input a parse tree. However be careful because, programs
contain variables and variable assignments. This means
you need to maintain a kind of memory, or environment,
where you can look up a value of a variable and also
store a new value if it is assigned. Therefore an
evaluation function (interpreter) needs to look roughly as 
follows 

\begin{lstlisting}[numbers=none]
eval_stmt(stmt, env)
\end{lstlisting}

\noindent 
where \pcode{stmt} corresponds to the parse tree
of the program and \pcode{env} is an environment
acting as a store for variable values. 
Consider the Fibonacci program in Figure~\ref{fib}.
At the beginning of the program this store will be 
empty, but needs to be extended in line 3 and 4 where 
the variables \pcode{minus1} and \pcode{minus2}
are assigned values. These values need to be reassigned in
lines 7 and 8. The program should  be interpreted
according to straightforward rules: for example an
if-statement will ``run'' the if-branch if the boolean
evaluates to \pcode{true}, otherwise the else-branch.
Loops should be run as long as the boolean is \pcode{true}.

Give some time measurements for your interpreter
and the loop program in Figure~\ref{loop}. For example
how long does your interpreter take when \pcode{start}
is initialised with 100, 500 and so on. How far can
you scale this value if you are willing to wait, say
1 Minute?

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

\begin{figure}[p]
\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: