\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../langs}+ −
+ −
\usepackage{array}+ −
+ −
+ −
\begin{document}+ −
\newcolumntype{C}[1]{>{\centering}m{#1}}+ −
+ −
\section*{Coursework 1 (Strand 1)}+ −
+ −
This coursework is worth 4\% and is due on 19 October at+ −
16: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+ −
which you answered the questions, otherwise a mark of 0\% will+ −
be awarded. You can submit your answers in a txt-file or pdf.+ −
Code send as code.+ −
+ −
+ −
+ −
\subsubsection*{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 or+ −
uploaded to KEATS, which you can freely use.\bigskip+ −
+ −
\noindent+ −
If you have any questions, please send me an email in \textbf{good}+ −
time.\bigskip+ −
+ −
\subsection*{Task}+ −
+ −
The task is to implement a regular expression matcher based on+ −
derivatives of regular expressions. The implementation should+ −
be able to deal with the usual (basic) regular expressions+ −
+ −
\[+ −
\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*+ −
\]+ −
+ −
\noindent+ −
but also with the following extended regular expressions:+ −
+ −
\begin{center}+ −
\begin{tabular}{ll}+ −
$[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\+ −
$r^+$ & one or more times $r$\\+ −
$r^?$ & optional $r$\\+ −
$r^{\{n\}}$ & exactly $n$-times\\+ −
$r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\+ −
$r^{\{n..\}}$ & at least $n$-times $r$\\+ −
$r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\+ −
$\sim{}r$ & not-regular-expression of $r$\\+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent You can assume that $n$ and $m$ are greater or equal than+ −
$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 2, where you are asked to explicitly give the rules for+ −
\textit{nullable} and \textit{der} for the extended regular+ −
expressions.\newpage+ −
+ −
\noindent+ −
The meanings of the extended regular expressions are+ −
+ −
\begin{center}+ −
\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}+ −
$L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ + −
$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\+ −
$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\+ −
$L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\+ −
$L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\+ −
$L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\+ −
$L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\+ −
$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent whereby in the last clause the set $\Sigma^*$ stands+ −
for the set of \emph{all} strings over the alphabet $\Sigma$+ −
(in the implementation the alphabet can be just what is+ −
represented by, say, the type \pcode{Char}). So $\sim{}r$+ −
means in effect ``all the strings that $r$ cannot match''.\medskip + −
+ −
\noindent+ −
Be careful that your implementation of \textit{nullable} and+ −
\textit{der} satisfies for every regular expression $r$ the following+ −
two properties (see also Question 2):+ −
+ −
\begin{itemize}+ −
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$+ −
\item $L(der\,c\,r) = Der\,c\,(L(r))$+ −
\end{itemize}+ −
+ −
+ −
+ −
\subsection*{Question 1 (Unmarked)}+ −
+ −
What is your King's email address (you will need it in+ −
Question 4)?+ −
+ −
\subsection*{Question 2}+ −
+ −
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:+ −
+ −
\begin{center}+ −
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
$\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^+)$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^?)$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^{\{n\}})$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^{\{..m\}})$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^{\{n..\}})$ & $\dn$ & $?$\\+ −
$\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & $?$\\+ −
$\textit{nullable}(\sim{}r)$ & $\dn$ & $?$+ −
\end{tabular}+ −
\end{center}+ −
+ −
\begin{center}+ −
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
$der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\+ −
$der\, c\, (r^+)$ & $\dn$ & $?$\\+ −
$der\, c\, (r^?)$ & $\dn$ & $?$\\+ −
$der\, c\, (r^{\{n\}})$ & $\dn$ & $?$\\+ −
$der\, c\, (r^{\{..m\}})$ & $\dn$ & $?$\\+ −
$der\, c\, (r^{\{n..\}})$ & $\dn$ & $?$\\+ −
$der\, c\, (r^{\{n..m\}})$ & $\dn$ & $?$\\+ −
$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent+ −
Remember your definitions have to satisfy the two properties+ −
+ −
\begin{itemize}+ −
\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$+ −
\item $L(der\,c\,r)) = Der\,c\,(L(r))$+ −
\end{itemize}+ −
+ −
\noindent+ −
Given the definitions of \textit{nullable} and \textit{der}, it is+ −
easy to implement a regular expression matcher. Test your regular+ −
expression matcher with (at least) the examples:+ −
+ −
+ −
\begin{center}+ −
\def\arraystretch{1.2} + −
\begin{tabular}{r|m{12mm}|m{12mm}|m{12mm}|m{12mm}|m{12mm}|m{12mm}}+ −
string & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ &+ −
$(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$\\\hline+ −
$[]$ &&&&&& \\\hline + −
\texttt{a} &&&&&& \\\hline + −
\texttt{aa} &&&&&& \\\hline + −
\texttt{aaa} &&&&&& \\\hline + −
\texttt{aaaaa} &&&&&& \\\hline + −
\texttt{aaaaaa}&&&&&& \\+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent+ −
Does your matcher produce the expected results?+ −
+ −
\subsection*{Question 3}+ −
+ −
As you can see, there are a number of explicit regular expressions+ −
that deal with single or several characters, for example:+ −
+ −
\begin{center}+ −
\begin{tabular}{ll}+ −
$c$ & matches a single character\\ + −
$[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\+ −
$\textit{ALL}$ & matches any character+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent+ −
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)+ −
are matched, namely those where $f$ returns \texttt{true}.+ −
In this question implement \textit{CFUN} and define+ −
+ −
\begin{center}+ −
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
$\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\+ −
$\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$+ −
\end{tabular}+ −
\end{center}+ −
+ −
\noindent in your matcher and then also give definitions for+ −
+ −
\begin{center}+ −
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}+ −
$c$ & $\dn$ & $\textit{CFUN}(?)$\\+ −
$[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\+ −
$\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$+ −
\end{tabular}+ −
\end{center}+ −
+ −
+ −
\subsection*{Question 4}+ −
+ −
Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression+ −
+ −
\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]+ −
+ −
\noindent+ −
Define in your code the following regular expression for email addresses+ −
+ −
\[+ −
([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+ −
address. When calculating the derivative, simplify all regular+ −
expressions as much as possible by applying the+ −
following 7 simplification rules:+ −
+ −
\begin{center}+ −
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}+ −
$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ + −
$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ + −
$r \cdot \ONE$ & $\mapsto$ & $r$\\ + −
$\ONE \cdot r$ & $\mapsto$ & $r$\\ + −
$r + \ZERO$ & $\mapsto$ & $r$\\ + −
$\ZERO + r$ & $\mapsto$ & $r$\\ + −
$r + r$ & $\mapsto$ & $r$\\ + −
\end{tabular}+ −
\end{center}+ −
+ −
\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+ −
Implement the simplification rules in your regular expression matcher.+ −
Consider the regular expression $/ \cdot * \cdot+ −
(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *+ −
\cdot /$ and decide wether the following four strings are matched by+ −
this regular expression. Answer yes or no.+ −
+ −
\begin{enumerate}+ −
\item \texttt{"/**/"}+ −
\item \texttt{"/*foobar*/"}+ −
\item \texttt{"/*test*/test*/"}+ −
\item \texttt{"/*test/*test*/"}+ −
\end{enumerate}+ −
+ −
\subsection*{Question 5}+ −
+ −
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+ −
strings consisting of $a$s only can be matched by $(r_1^+)^+$.+ −
Similarly test them with $(r_2^+)^+$. Again answer in all six cases+ −
with yes or no. \medskip+ −
+ −
\noindent+ −
These are strings are meant to be entirely made up of $a$s. Be careful+ −
when copy-and-pasting the strings so as to not forgetting any $a$ and+ −
to not introducing any other character.+ −
+ −
\begin{enumerate}+ −
\setcounter{enumi}{4}+ −
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\+ −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\+ −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}+ −
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ + −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ + −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}+ −
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ + −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ + −
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}+ −
\end{enumerate}+ −
+ −
+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −