--- a/cws/main_cw03.tex Thu Jan 13 12:55:03 2022 +0000
+++ b/cws/main_cw03.tex Mon Apr 11 23:55:27 2022 +0100
@@ -176,6 +176,7 @@
5000000: 1.29659 secs.
\end{lstlisting}%$
+
\subsection*{Preliminaries}
The task is to implement a regular expression matcher that is based on
@@ -241,8 +242,10 @@
The alternative regular expressions comes in two versions: one is
binary (+ / \texttt{ALT}) and the other is n-ary ($\sum$ /
\texttt{ALTs}). The latter takes a list of regular expressions as
-arguments. In what follows we shall use $rs$ to stand for lists of
-regular expressions. The binary alternative can be seen as an abbreviation,
+argument. In what follows we shall use $rs$ to stand for lists of
+regular expressions. When the list is empty, we shall write $\sum\,[]$;
+if it is non-empty, we sometimes write $\sum\,[r_1,..., r_n]$.
+The binary alternative can be seen as an abbreviation,
that is $r_1 + r_2 \dn \sum\,[r_1, r_2]$. As a result we can ignore the
binary version and only implement the n-ary alternative.
@@ -267,7 +270,7 @@
\item[(2)] Implement a function, called \textit{der}, by recursion over
regular expressions. It takes a character and a regular expression
- as arguments and calculates the derivative of a regular expression according
+ as arguments and calculates the \emph{derivative} of a regular expression according
to the rules:
\begin{center}
@@ -337,8 +340,8 @@
\end{tabular}
\end{center}
- The first clause just states that empty lists cannot be further
- flattened. The second removes all $\ZERO$s from the list.
+ The first clause states that empty lists cannot be further
+ flattened. The second removes the first $\ZERO$ from the list and recurses.
The third is when the first regular expression is an \texttt{ALTs}, then
the content of this alternative should be spilled out and appended
with the flattened rest of the list. The last case is for all other
@@ -366,16 +369,16 @@
expressions $r_1,.. ,r_n$; then flatten the resulting list using
\texttt{flts}; finally remove all duplicates in this list (this can be
done in Scala using the function
-\texttt{\_.distinct}). \textcolor{red}{When you perform these
+\texttt{\_.distinct}). When you perform these
operations, you end up with three cases, namely where the list is
empty, contains a single element and ``otherwise''. These cases
- should be processed as follows}
+ should be processed as follows
\begin{center}
-\textcolor{red}{\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
$\sum\;[]$ & $\mapsto$ & $\ZERO$\\
$\sum\;[r]$ & $\mapsto$ & $r$\\
$\sum\;rs$ & $\mapsto$ & $\sum\;rs$ & ``otherwise''\\
-\end{tabular}}
+\end{tabular}
\end{center}
@@ -515,7 +518,7 @@
\begin{center}
\begin{tabular}{@{}cc@{}}
\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings
- $\underbrace{a\ldots a}_{n}$}\bigskip\\
+ $\underbrace{a\ldots a}_{n}$}\medskip\\
\begin{tikzpicture}
\begin{axis}[
@@ -531,7 +534,7 @@
scaled ticks=false,
axis lines=left,
width=6cm,
- height=5.0cm,
+ height=5.5cm,
legend entries={Python, Java 8, JavaScript, Swift, Dart},
legend pos=north west,
legend cell align=left]
@@ -557,7 +560,7 @@
scaled ticks=false,
axis lines=left,
width=6cm,
- height=5.0cm,
+ height=5.5cm,
legend entries={Java 9},
legend pos=north west]
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};