% !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+
−
16: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. But do not+
−
be tempted to ask Github Copilot for help or do any other+
−
shenanigans like this!+
−
+
−
+
−
\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{collatz}.  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]{../cwtests/cw03/fib.while}+
−
\caption{Fibonacci program in the WHILE language.\label{fib}}+
−
\end{figure}+
−
+
−
\begin{figure}[h]+
−
\lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/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]{../cwtests/cw03/primes.while}+
−
\caption{Prime number program.\label{primes}}+
−
\end{figure}+
−
+
−
+
−
\begin{figure}[p]+
−
\lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/collatz2.while}+
−
\caption{Collatz series program.\label{collatz}}+
−
\end{figure}+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−