% !TEX program = xelatex

\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\begin{document}

\section*{Coursework 3}

\noindent This coursework is worth 5\% and is due on 22 

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, that is \pcode{+}, \pcode{-}, \pcode{*},

  \pcode{/} and \pcode{\%})

\item boolean expressions (with the operations \pcode{==}, \pcode{<}, \pcode{>},

  \code{>=}, \code{<=}, 

  \code{!=}, \pcode{&&}, \pcode{||}, \pcode{true} and \pcode{false})

\item single statements (that is \pcode{skip}, assignments, \pcode{if}s,

  \pcode{while}-loops, \pcode{read} and \pcode{write})

\item compound statements separated by semicolons

\item blocks which are enclosed in curly parentheses

\end{itemize}

\noindent

Make sure the grammar is not left-recursive.

\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}, \ref{loop} and \ref{primes} (if your lexer cannot

deal with comments you can delete them from the prime number program).

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

case class Lop(o: String, b1: BExp, b2: BExp) 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]

\lstinputlisting[language=while,xleftmargin=20mm]{../progs/fib.while}

\caption{Fibonacci program in the WHILE language.\label{fib}}

\end{figure}

\begin{figure}[p]

\lstinputlisting[language=while,xleftmargin=20mm]{../progs/loops.while}

\caption{The three-nested-loops program in the WHILE language. 

Usually used for timing measurements.\label{loop}}

\end{figure}

\begin{figure}[p]

\lstinputlisting[language=while,xleftmargin=0mm]{../progs/primes.while}

\caption{Prime number program.\label{primes}}

\end{figure}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: