diff -r b153c04834eb -r 4573d36d0b2f coursework/cw01.tex --- a/coursework/cw01.tex Mon Oct 01 01:11:42 2018 +0100 +++ b/coursework/cw01.tex Mon Oct 01 14:04:48 2018 +0100 @@ -11,7 +11,7 @@ \section*{Coursework 1 (Strand 1)} This coursework is worth 4\% and is due on 12 October at -16:00. You are asked to implement a regular expression matcher +18:00. You are asked to implement a regular expression matcher and 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 @@ -62,12 +62,15 @@ $0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip \noindent {\bf Important!} Your implementation should have explicit -cases for the basic regular expressions, but also for explicit cases for -the extended regular expressions. That means do not treat the extended -regular expressions by just translating them into the basic ones. See -also Question 3, where you are asked to explicitly give the rules for -\textit{nullable} and \textit{der} for the extended regular -expressions.\newpage +case classes for the basic regular expressions, but also explicit case +classes for +the extended regular expressions.\footnote{Please call them + \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, + \code{UPTO}, \code{FROM}, \code{BETWEEN}, \code{NOT} or something + like that.} That means do not treat the extended regular expressions +by just translating them into the basic ones. See also Question 3, +where you are asked to explicitly give the rules for \textit{nullable} +and \textit{der} for the extended regular expressions.\medskip \noindent The meanings of the extended regular expressions are @@ -110,16 +113,18 @@ \subsection*{Question 2 (Unmarked)} -In which programming languages have you written a program (like spent -at least a day working on the program)? +Can you please list all programming languages in which you have +already written programs (like spent at least a good working day +working on the program)? This is just for my curiosity to estimate +what your background is. \subsection*{Question 3} From the lectures you have seen the definitions for the functions \textit{nullable} and \textit{der} for the basic regular -expressions. Implement the rules for the extended regular -expressions: +expressions. Implement and write down rules for the extended +regular expressions: \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} @@ -192,11 +197,11 @@ \end{center} \noindent -the latter is useful for matching any string (for example +The latter is useful for matching any string (for example by using $\textit{ALL}^*$). In order to avoid having an explicit constructor for each case, we can generalise all these cases and introduce a single constructor $\textit{CFUN}(f)$ where $f$ is a function from characters -to a boolean. The idea is that the function $f$ determines which character(s) +to booleans. The idea is that the function $f$ determines which character(s) are matched, namely those where $f$ returns \texttt{true}. In this question implement \textit{CFUN} and define @@ -217,6 +222,11 @@ \end{tabular} \end{center} +\noindent +You can either add the constructor $CFUN$ to your implementation in +Question 3, or you can implement this questions first +and then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3. + \subsection*{Question 5} @@ -231,7 +241,7 @@ ([a\mbox{-}z0\mbox{-}9\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}}) \] -\noindent and calculate the derivative according to your email +\noindent and calculate the derivative according to your own email address. When calculating the derivative, simplify all regular expressions as much as possible by applying the following 7 simplification rules: @@ -251,9 +261,11 @@ \noindent Write down your simplified derivative in a readable notation using parentheses where necessary. That means you should use the infix notation $+$, $\cdot$, $^*$ and so on, -instead of code.\bigskip - -\noindent +instead of raw code.\bigskip + + +\subsection*{Question 6} + Implement the simplification rules in your regular expression matcher. Consider the regular expression $/ \cdot * \cdot (\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot * @@ -267,7 +279,7 @@ \item \texttt{"/*test/*test*/"} \end{enumerate} -\subsection*{Question 6} +\subsection*{Question 7} Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be $(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three