% !TEX program = xelatex
\documentclass{article}
\usepackage{../style}
\usepackage{../langs}
\usepackage[normalem]{ulem}

\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. The parser needs to use parser combinators.
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 submit your code to Github by the deadline.

\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 according to your grammar for the statement:

\begin{lstlisting}[language=While,numbers=none]
if (a < b) then skip else a := a * b + 1
\end{lstlisting}

\noindent
The output of the parser is an abstract syntax tree (AST).
A (possibly incomplete) datatype for ASTs of the WHILE language
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 abstract syntax 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 an AST. 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}.
Note also that some programs contain a read-statement,
which means you need to read and integer from the commandline
and store the value in the corresponding variable.
Programs you should be able to run are shown in
Figures \ref{fib} -- \ref{collatz}. The output
of the \texttt{primes.while} should look as follows:

\begin{figure}[h]
{\small
\begin{lstlisting}[numbers=none]
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Map(end -> 100, n -> 100, f -> 4, tmp -> 1)
\end{lstlisting}}
\caption{Sample output for the file \texttt{primes.while}.\label{fib}}
\end{figure}

\noindent
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?

\clearpage

\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}

\clearpage
\newpage
\section*{Answers}

\mbox{}  

\noindent
\textbf{Name:}\uline{\hfill}\bigskip



\noindent
\textbf{Question 1 (Grammar):}\\

\mbox{}\\[9cm]

\newpage
\noindent
\textbf{Question 2 (Parse Tree):}\\

\mbox{}\\[8cm]


\noindent
\textbf{Question 3 (Timings):}\\

\begin{center}
  \def\arraystretch{1.5}
  \begin{tabular}{l|l}
    n & secs\\
    \hline
    100 & \\
    500 & \\
    700 & \\
    1000 & \\
    \\
    \\
    \\
    \\
   \end{tabular} 
\end{center}  

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: