% !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, 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 stream, orlist, of 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 inFigures~\ref{fib}, \ref{loop} and \ref{primes} (if your lexer cannotdeal with comments you can delete them from the prime number program).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 BExpcase class Lop(o: String, b1: BExp, b2: BExp) 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]\lstinputlisting[language=while,xleftmargin=20mm]{../progs/fib.while}\caption{Fibonacci program in the WHILE language.\label{fib}}\end{figure}\begin{figure}[p]\lstinputlisting[language=while,xleftmargin=20mm]{../progs/loops.while}\caption{The three-nested-loops program in the WHILE language. Usually used for timing measurements.\label{loop}}\end{figure}\begin{figure}[p]\lstinputlisting[language=while,xleftmargin=0mm]{../progs/primes.while}\caption{Prime number program.\label{primes}}\end{figure}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: