an interpreter. You should use the lexer from the previous

coursework for the parser. 

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}

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}

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}