diff -r 4b208d81e002 -r c0bdd4ad69ca cws/cw03.tex --- /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: