% !TEX program = xelatex\documentclass{article}\usepackage{../style}\usepackage{../langs}\begin{document}\section*{Coursework 3}\noindent This coursework is worth 5\% and is due on 22 November at 18:00. You are asked to implement a parser for theWHILE language and also an interpreter. You can do theimplementation in any programming language you like, but youneed to submit the source code with which you answered thequestions, otherwise a mark of 0\% will be awarded. You shoulduse the lexer from the previous coursework for the parser. \subsection*{Disclaimer}It should be understood that the work you submit representsyour own effort. You have not copied from anyone else. Anexception is the Scala code I showed during the lectures,which you can use. You can also use your own code from theCW~1 and CW~2.\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, such as \pcode{+}, \pcode{*} and so on)\item boolean expressions (such as \pcode{<}, \code{!=} and so on)\item single statements (such as \pcode{skip}, assignments, \pcode{if}s, \pcode{while}-loops and so on)\item compound statements separated by semicolons\item blocks which are enclosed in curly parentheses\end{itemize}\subsection*{Question 2}You should implement a parser for the WHILE language usingparser combinators. Be careful that the parser takes as inputa stream, or list, of tokens generated by the tokenizer fromthe previous coursework. For this you might want to filter out whitespaces and comments. Your parser should be able to handlethe WHILE programs in Figures~\ref{fib} and \ref{loop}.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}\noindentA (possibly incomplete) datatype for parse trees in Scala wouldlook as in Figure~\ref{trees}.\begin{figure}\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 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 BExp\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 designedand parsed in Question 1 and 2. This interpreter should takeas input a parse tree. 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}.Give some time measurements for your interpreterand the loop program in Figure~\ref{loop}. For examplehow long does your interpreter take when \pcode{start}is initialised with 100, 500 and so on. How far canyou scale this value if you are willing to wait, say1 Minute?\begin{figure}[p]\begin{center}\mbox{\lstinputlisting[language=while]{../progs/fib.while}}\end{center}\caption{Fibonacci program in the WHILE language.\label{fib}}\end{figure}\begin{figure}[p]\begin{center}\mbox{\lstinputlisting[language=while]{../progs/loops.while}}\end{center}\caption{The three-nested-loops program in the WHILE language. Usually used for timing measurements.\label{loop}}\end{figure}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: