diff -r e9d14d58be3c -r daf561a83ba6 cws/main_cw03.tex --- 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};