\documentclass{article}\usepackage{hyperref}\usepackage{amssymb}\usepackage{amsmath}\usepackage{../langs}\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%\begin{document}\section*{Coursework 2}{\bf UPDATE:} There was a typo in Q1 about the regular expressions for comments:they should, of course, start with $\slash\slash$, as in C for example, not with $\backslash\backslash$. (Thanks to Bryan who pointed out this error.)\bigskip\bigskip\noindentThis coursework is worth 3\% and is due on 29 November at 16:00. You are asked to \begin{enumerate}\item implement a tokeniser for the WHILE language,\item implement a parser and an evaluator for boolean and arithmetic expressions, and\item write a WHILE program for printing out prime numbers.\end{enumerate}\noindentYou need to submit a document containing the answers for the questions below. 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. However, the coursework will \emph{only} be judged according to the answers. You can submit your answersin a txt-file or as pdf.\bigskip\subsection*{Question 1 (marked with 1\%)}Implement a tokeniser for the WHILE language. You first need to design the appropriateregular expressions for the following nine syntactic entities:\begin{enumerate}\item keywords are\begin{quote}\texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}\texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}\end{quote} \item operators are\begin{quote}\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}\end{quote} \item strings are enclosed by \texttt{"\ldots"} \item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}\item there are semicolons \texttt{;}\item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}\item comments either start with $\slash\,\slash$ and run to the end of the corresponding line (indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by$\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker\item identifiers are letters followed by underscores \texttt{\_\!\_}, lettersor digits\item numbers are \texttt{0}, \text{1}, \ldots\end{enumerate}\noindentOnce you have implemented all regular expressions for 1 - 9, thengive the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.\subsection*{Question 2 (marked with 1\%)}Implement parser combinators and an evaluation function for arithmetic and booleanexpressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and \texttt{\%} (quotient). Booleanoperations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and \texttt{>}.Using the parser and evaluation function, calculate the values for\begin{itemize}\item \texttt{17 < 3 * 3 * 3}\item \texttt{(29 - 20) * 3}\item \texttt{79 - 20 * 3}\item \texttt{2 * 2 != 12 \% 3}\end{itemize} \subsection*{Question 3 (marked with 1\%)}Write a program in the WHILE programming language that prints out all prime numbers between0 and a fixed number (say 100). A partial grammar of the WHILE language is given below. \begin{center}\begin{tabular}{@{}lcl@{}}\textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\ & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\ & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\ & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\ & $|$ & \texttt{read}\;\textit{Id}\\ & $|$ & \texttt{write}\;\textit{Id}\\ & $|$ & \texttt{write}\;\textit{String}\medskip\\\textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\ & $|$ & \textit{Stmt}\medskip\\\textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\ & $|$ & \textit{Stmt}\medskip\\\textit{AExp} & $\rightarrow$ & \ldots\\\textit{BExp} & $\rightarrow$ & \ldots\\\end{tabular}\end{center}\noindentAs another guidance for your program have a look at the Fibonacci programand ``three-nested-loops'' program shown below in Figures \ref{fib} and \ref{loop}. \begin{figure}[h]\begin{center}\mbox{\lstinputlisting[language=while]{../progs/fib.while}}\end{center}\caption{Fibonacci program in the WHILE language.\label{fib}}\end{figure}\begin{figure}[h]\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: