\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\begin{document}

\section*{Coursework 3 (Strand 1)}

\noindent

This coursework is worth 5\% and is due on 28 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: