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

\begin{document}

\section*{Coursework 3}

\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 will 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{<}, \pcode{!=} 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 based on parser combinators
for the WHILE language. Be careful that the parser takes
as input a stream of token generated by the tokenizer from
the previous courswork. Your parser should be able to handle
the WHILE programs in Figures~\ref{fib} and \ref{loop}.

Give the parse tree for the statement:

\begin{center}
\code{if (a < b) then skip else a := a * b + 1}
\end{center}

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.}
\end{figure}

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

Implement an interpreter for the WHILE language you
designed and parsed above. 



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