\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+ −
+ −
\noindent+ −
This 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}+ −
+ −
\noindent+ −
You 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 answers+ −
in 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 appropriate+ −
regular 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{\_\!\_}, letters+ −
or digits+ −
\item numbers are \texttt{0}, \text{1}, \ldots+ −
\end{enumerate}+ −
+ −
\noindent+ −
Once you have implemented all regular expressions for 1 - 9, then+ −
give 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 boolean+ −
expressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and + −
\texttt{\%} (quotient). Boolean+ −
operations 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 between+ −
0 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}+ −
+ −
\noindent+ −
As another guidance for your program have a look at the Fibonacci program+ −
and ``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: + −