% !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. If you use Scala

in your code, a good place to start is the file \texttt{comb1.sc} and

\texttt{comb2.sc} uploaded to KEATS. Make sure your parser combinators 

process list of tokens as input, not strings. Feel free to use the ``hack''

explained during the lectures. This might make your grammar

simpler. However, make sure you understand the code involved in the

``hack'' because if you just do ``mix-and-match'' you will receive

strange errors.  The main function that will be tested is called

\texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a list

of tokens as input and generates an AST. The former expects an AST and

``runs'' the program. The marks will be distributed such that 6 marks

are given for the correct grammar (and parsers); 4 marks for the correct

\texttt{eval} function.  You should use the lexer from CW2 for the

parser - you potentially need to make additions for CW3.  

\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*{Syntax Error in Template File cw03.sc\alert}

%

%Apologies, there is a small syntax error in the template file where a variable

%needs to be called \texttt{tks} instead of \texttt{tk}. The code

%in question is at the end of \texttt{cw03.sc} and should be like

%this (see lines 5, 6 and 8):

%

%\begin{lstlisting}[language=Scala,numbers=left]

%@main

%def test(file: String) = {

%  val contents = os.read(os.pwd / "examples" / file)

%  println(s"Lex $file: ")

%  val tks = tokenise(contents)

%  println(tks.mkString(","))

%  println(s"Parse $file: ")

%  val ast = Stmts.parse_all(tks).head

%  println(ast)

%  println(s"Eval $file: ")

%  println(eval(ast))

%}

%\end{lstlisting}  

\subsection*{Task 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*{Task 2}

You should implement a parser for the WHILE language using parser

combinators. Be careful that the parser takes as input a 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

the \texttt{examples} directory.  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*{Task 3}

In addition to the simple assignments of the form \code{... := ...} 

from Task 1, parse the assignments of the form

\begin{quote}

\texttt{... += ...} \;\;and\;\; \texttt{... *= ...}

\end{quote}

and translate them into simple assignments. For example

\begin{quote}

\texttt{cnt += 1}

\end{quote}

should give the assignment \texttt{cnt := cnt + 1}. Similarly

for \texttt{*=}.

\subsection*{Task 4}

Implement an interpreter for the WHILE language you designed

and parsed in Tasks 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 an integer from the commandline

and store the value in the corresponding variable.

Programs you should be able to run are given in  the

\texttt{examples} directory. 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}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: