--- a/coursework/cw03.tex Tue Sep 01 15:57:55 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,167 +0,0 @@
-% !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: