
diff -r 21f0f24424ab -r 618c7640cf66 coursework/cw02.tex
--- a/coursework/cw02.tex	Sun Oct 12 22:36:18 2014 +0100
+++ b/coursework/cw02.tex	Mon Oct 13 00:09:28 2014 +0100
@@ -1,127 +1,142 @@
 \documentclass{article}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
 \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
+\section*{Coursework 2 (Strand 1)}
 
 \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}
+This coursework is worth 5\% and is due on 3 November at 16:00. You
+are asked to implement the Sulzmann tokeniser for the WHILE language.
+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.
 
-\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*{Disclaimer}
 
+It should be understood that the work you submit represents your own
+effort.  You have not copied from anyone else. An exception is the
+Scala code I showed during the lectures, which you can use.
+You can also use your own code from the CW~1.
 
 \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:
+To implement a tokeniser for the WHILE language, you first need to design 
+the appropriate regular expressions for the following eight 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}
+\texttt{while}, 
+\texttt{if}, 
+\texttt{then}, 
+\texttt{else}, 
+\texttt{do}, 
+\texttt{for}, 
+\texttt{to}, 
+\texttt{true}, 
+\texttt{false}, 
+\texttt{read}, 
+\texttt{write},
+\texttt{skip}
 \end{quote} 
 
 \item operators are
 
 \begin{quote}
-\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}
+\texttt{+}, 
+\texttt{-}, 
+\texttt{*}, 
+\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 whitespaces are either \texttt{" "} (one or more) or \texttt{$\backslash$n}
 \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\%)}
+You can use the basic regular expressions 
 
-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
+\[
+\varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*
+\]
 
-\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. 
+\noindent
+but also the following extended regular expressions
 
 \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\\
+\begin{tabular}{ll}
+$[c_1 c_2 \ldots c_n]$ & a range of characters\\
+$r^+$ & one or more times $r$\\
+$r^?$ & optional $r$\\
+$r^{\{n\}}$ & n-times $r$\\
 \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}. 
+Once you have designed all regular expressions for 1 - 8, then
+give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.
+
+\subsection*{Question 2 (marked with 3\%)}
+
+Implement the Sulzmann tokeniser from the lectures. For this you need
+to implement the functions $nullable$ and $der$ (you can use your code
+from CW 1), as well as $mkeps$ and $inj$. These functions need to be
+appropriately extended for the extended regular expressions from
+Q1. Also add the record regular expression from the lectures and
+implement a function, say \pcode{env}, that returns all assignments
+from a value (such that you can extract easily the tokens from a
+value). 
+
+The functions $mkeps$ and $inj$ return values. Calculate
+the value for your regular expressions from Q1 and the string
+
+\begin{center}
+\code{"read n;"}
+\end{center} 
+
+\noindent
+and use your \pcode{env} function to give the token sequence.
+
+\subsection*{Question 3 (marked with 1\%)}
+
+Extend your tokenizer from Q2 to also simplify regular expressions
+after each derivation step and rectify the computed values after each
+injection. Use this tokenizer to tokenize the programs in
+Figure~\ref{fib} and \ref{loop}.
 
 
-\begin{figure}[h]
+\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}[h]
+\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}}
+\caption{The three-nested-loops program in the WHILE language. 
+Usually used for timing measurements.\label{loop}}
 \end{figure}
 
 \end{document}




