diff -r 02bc5af1c5f2 -r 1f1a293549c1 coursework/cw03.tex --- 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: