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

\begin{document}

\section*{Coursework 3 (Strand 1)}

\noindent
This coursework is worth 5\% and is due on 26 November at 16:00. You 
are asked to implement a parser for the WHILE language and also 
an interpreter. You should use the lexer from the previous
coursework for the parser. 



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

Design a grammar for the WHILE language and give the grammar 
rules. The main categories of non-terminal 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 (marked with 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 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 (marked with 2\%)}

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: