9 \begin{document} |
9 \begin{document} |
10 \newcolumntype{C}[1]{>{\centering}m{#1}} |
10 \newcolumntype{C}[1]{>{\centering}m{#1}} |
11 |
11 |
12 \section*{Coursework 1 (Strand 1)} |
12 \section*{Coursework 1 (Strand 1)} |
13 |
13 |
14 This coursework is worth 4\% and is due on 12 October at |
14 This coursework is worth 4\% and is due on 11 October at |
15 18:00. You are asked to implement a regular expression matcher |
15 18:00. You are asked to implement a regular expression matcher |
16 and submit a document containing the answers for the questions |
16 and submit a document containing the answers for the questions |
17 below. You can do the implementation in any programming |
17 below. You can do the implementation in any programming |
18 language you like, but you need to submit the source code with |
18 language you like, but you need to submit the source code with |
19 which you answered the questions, otherwise a mark of 0\% will |
19 which you answered the questions, otherwise a mark of 0\% will |
65 \noindent {\bf Important!} Your implementation should have explicit |
65 \noindent {\bf Important!} Your implementation should have explicit |
66 case classes for the basic regular expressions, but also explicit case |
66 case classes for the basic regular expressions, but also explicit case |
67 classes for |
67 classes for |
68 the extended regular expressions.\footnote{Please call them |
68 the extended regular expressions.\footnote{Please call them |
69 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, |
69 \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES}, |
70 \code{UPTO}, \code{FROM}, \code{BETWEEN}, \code{NOT} or something |
70 \code{UPTO}, \code{FROM} and \code{BETWEEN}.} |
71 like that.} That means do not treat the extended regular expressions |
71 That means do not treat the extended regular expressions |
72 by just translating them into the basic ones. See also Question 3, |
72 by just translating them into the basic ones. See also Question 3, |
73 where you are asked to explicitly give the rules for \textit{nullable} |
73 where you are asked to explicitly give the rules for \textit{nullable} |
74 and \textit{der} for the extended regular expressions. So something like |
74 and \textit{der} for the extended regular expressions. So something like |
75 $der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)$ is \emph{not} allowed.\medskip |
75 $der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)$ is \emph{not} allowed.\medskip |
76 |
76 |
278 \subsection*{Question 6} |
278 \subsection*{Question 6} |
279 |
279 |
280 Implement the simplification rules in your regular expression matcher. |
280 Implement the simplification rules in your regular expression matcher. |
281 Consider the regular expression $/ \cdot * \cdot |
281 Consider the regular expression $/ \cdot * \cdot |
282 (\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot * |
282 (\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot * |
283 \cdot /$ and decide wether the following four strings are matched by |
283 \cdot /$ and decide whether the following four strings are matched by |
284 this regular expression. Answer yes or no. |
284 this regular expression. Answer yes or no. |
285 |
285 |
286 \begin{enumerate} |
286 \begin{enumerate} |
287 \item \texttt{"/**/"} |
287 \item \texttt{"/**/"} |
288 \item \texttt{"/*foobar*/"} |
288 \item \texttt{"/*foobar*/"} |