% !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{} at16:00. You are asked to implement a parser for the WHILE language andalso an interpreter. The parser needs to use parser combinators. Youcan do the implementation in any programming language you like, butyou need to submit the source code with which you answered thequestions, otherwise a mark of 0\% will be awarded. If you use Scalain your code, a good place to start is the file \texttt{comb1.sc} and\texttt{comb2.sc} uploaded to KEATS. Feel free to use the ``hack''explained during the lectures. This might make your grammarsimpler. However, make sure you understand the code involved in the``hack'' because if you just do ``mix-and-match'' you will receivestrange errors. The main function that will be tested is called\texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a listof tokens as input and generates an AST. The former expects an AST and``runs'' the program. The marks will be distributed such that 6 marksare given for the correct grammar (and parsers); 4 marks for the correct\texttt{eval} function. You should use the lexer from CW2 for theparser - you potentially need to make additions for CW2. \subsection*{Disclaimer\alert}It should be understood that the work you submit represents your owneffort. You have not copied from anyone else. An exception is theScala code I showed during the lectures or uploaded to KEATS, whichyou can both use. You can also use your own code from the CW~1 andCW~2. But do notbe tempted to ask Github Copilot for help or do any othershenanigans like this!\subsection*{Syntax Error in Template File cw03.sc\alert}Apologies, there is a small syntax error in the template file where a variableneeds to be called \texttt{tks} instead of \texttt{tk}. The codein question is at the end of \texttt{cw03.sc} and should be likethis (see lines 5, 6 and 8):\begin{lstlisting}[language=Scala,numbers=left]@maindef 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*{Question 1}Design a grammar for the WHILE language and give the grammarrules. 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}\noindentMake sure the grammar is not left-recursive.\subsection*{Question 2}You should implement a parser for the WHILE language using parsercombinators. Be careful that the parser takes as input a list of\emph{tokens} generated by the tokenizer from the previouscoursework. For this you might want to filter out whitespaces andcomments. Your parser should be able to handle the WHILE programs inthe \texttt{examples} directory. The output of the parser is anabstract syntax tree (AST). A (possibly incomplete) datatype for ASTsof the WHILE language is shown in Figure~\ref{trees}.\begin{figure}[p]\begin{lstlisting}[language=Scala]abstract class Stmtabstract class AExpabstract class BExp type Block = List[Stmt]case object Skip extends Stmtcase class If(a: BExp, bl1: Block, bl2: Block) extends Stmtcase class While(b: BExp, bl: Block) extends Stmtcase class Assign(s: String, a: AExp) extends Stmtcase class Read(s: String) extends Stmtcase class WriteVar(s: String) extends Stmt case class WriteStr(s: String) extends Stmt // for printing variables and stringscase class Var(s: String) extends AExpcase class Num(i: Int) extends AExpcase class Aop(o: String, a1: AExp, a2: AExp) extends AExpcase object True extends BExpcase object False extends BExpcase class Bop(o: String, a1: AExp, a2: AExp) extends BExpcase 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 designedand parsed in Question 1 and 2. This interpreter should takeas input an AST. However be careful because, programscontain variables and variable assignments. This meansyou need to maintain a kind of memory, or environment,where you can look up a value of a variable and alsostore a new value if it is assigned. Therefore anevaluation 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 treeof the program and \pcode{env} is an environmentacting 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 inlines 7 and 8. The program should be interpretedaccording to straightforward rules: for example anif-statement will ``run'' the if-branch if the booleanevaluates 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 commandlineand store the value in the corresponding variable.Programs you should be able to run are given in the\texttt{examples} directory. The outputof the \texttt{primes.while} should look as follows:\begin{figure}[h]{\small\begin{lstlisting}[numbers=none]2357111317192329313741434753596167717379838997Map(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: