--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw03.tex Tue Sep 01 16:00:37 2020 +0100
@@ -0,0 +1,167 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+
+\begin{document}
+
+\section*{Coursework 3}
+
+
+
+\noindent This coursework is worth 10\% and is due on \cwTHREE{} 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. Please package everything(!) in a zip-file that creates a
+directory with the name \texttt{YournameYourFamilyname} on my end.
+
+\subsection*{Disclaimer\alert}
+
+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 or uploaded to KEATS, which
+you can both 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 \emph{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}. 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 is shown
+in Figure~\ref{trees}.
+
+\begin{figure}[p]
+\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 Read(s: String) extends Stmt
+case class WriteVar(s: String) extends Stmt
+case class WriteStr(s: String) extends Stmt
+ // for printing variables and strings
+
+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
+ // logical operations: and, or
+\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}.
+Programs you should be able to run are shown in
+Figures \ref{fib} -- \ref{collatz}.
+
+
+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}[h]
+\lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/fib.while}
+\caption{Fibonacci program in the WHILE language.\label{fib}}
+\end{figure}
+
+\begin{figure}[h]
+\lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/loops.while}
+\caption{The three-nested-loops program in the WHILE language.
+Usually used for timing measurements.\label{loop}}
+\end{figure}
+
+\begin{figure}[h]
+\lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/primes.while}
+\caption{Prime number program.\label{primes}}
+\end{figure}
+
+
+\begin{figure}[p]
+\lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/collatz2.while}
+\caption{Collatz series program.\label{collatz}}
+\end{figure}
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End: