104 

   104 

   105 \noindent

   105 \noindent

   106 This coursework is about the shunting yard algorithm by Dijkstra and a

   106 This coursework is about the shunting yard algorithm by Dijkstra and a

   107 regular expression matcher by Brzozowski. The preliminary part is due on

   107 regular expression matcher by Brzozowski. The preliminary part is due on

   108 \cwNINE{} at 4pm; the core, more advanced part, is due on \cwNINEa{}

   108 \cwNINE{} at 4pm; the core, more advanced part, is due on \cwNINEa{}

   110 transforms the usual infix notation of arithmetic expressions into the

   110 transforms the usual infix notation of arithmetic expressions into the

   111 postfix notation, which is for example used in compilers. In the core

   111 postfix notation, which is for example used in compilers. In the core

   112 part, you are asked to implement a regular expression matcher based on

   112 part, you are asked to implement a regular expression matcher based on

   113 derivatives of regular expressions. The background is that

   113 derivatives of regular expressions. The background is that

   114 ``out-of-the-box'' regular expression matching in mainstream languages

   114 ``out-of-the-box'' regular expression matching in mainstream languages

   140 

   140 

   141 

   141 

   142 

   142 

   143 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

   143 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]

   144 $ scala -cp re.jar

   144 $ scala -cp re.jar

   146 scala> for (i <- 0 to 5000000 by 500000) {

   146 scala> for (i <- 0 to 5000000 by 500000) {

   147   | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.")

   147   | println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + "secs.")

   148   | }

   148   | }

   149 0 0.00002 secs.

   149 0 0.00002 secs.

   150 500000 0.10608 secs.

   150 500000 0.10608 secs.

   255 \end{itemize}

   255 \end{itemize}

   256 

   256 

   257 \subsubsection*{Task (file postfix2.scala)}

   257 \subsubsection*{Task (file postfix2.scala)}

   258 

   258 

   259 \begin{itemize}

   259 \begin{itemize}

   261   operator.  This requires proper account of associativity of

   261   operator.  This requires proper account of associativity of

   262   the operators. The power operator is right-associative, whereas the

   262   the operators. The power operator is right-associative, whereas the

   263   other operators are left-associative.  Left-associative operators

   263   other operators are left-associative.  Left-associative operators

   264   are popped off if the precedence is bigger or equal, while

   264   are popped off if the precedence is bigger or equal, while

   265   right-associative operators are only popped off if the precedence is

   265   right-associative operators are only popped off if the precedence is

   298 detect security breaches). However, you need to be fast, otherwise you

   298 detect security breaches). However, you need to be fast, otherwise you

   299 will stumble over problems such as recently reported at

   299 will stumble over problems such as recently reported at

   300 

   300 

   301 {\small

   301 {\small

   302 \begin{itemize}

   302 \begin{itemize}

   304 \item[$\bullet$] \url{https://vimeo.com/112065252}

   305 \item[$\bullet$] \url{https://vimeo.com/112065252}

   306 \end{itemize}}

   307 \end{itemize}}

   307 

   308 

   308 % Knowing how to match regular expressions and strings will let you

   309 % Knowing how to match regular expressions and strings will let you

   309 % solve a lot of problems that vex other humans.

   310 % solve a lot of problems that vex other humans.

   310 

   311 

   348 \end{tabular}

   349 \end{tabular}

   349 \end{center}~\hfill[1 Mark]

   350 \end{center}~\hfill[1 Mark]

   350 

   351 

   351 \item[(6)] Implement a function, called \textit{der}, by recursion over

   352 \item[(6)] Implement a function, called \textit{der}, by recursion over

   352   regular expressions. It takes a character and a regular expression

   353   regular expressions. It takes a character and a regular expression

   354   to the rules:

   355   to the rules:

   355 

   356 

   356 \begin{center}

   357 \begin{center}

   357 \begin{tabular}{lcl}

   358 \begin{tabular}{lcl}

   358 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\

   359 $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\

   483 expression $(a^*)^* \cdot b$ grows when taking successive derivatives

   484 expression $(a^*)^* \cdot b$ grows when taking successive derivatives

   484 according the letter $a$ without simplification and then compare it to

   485 according the letter $a$ without simplification and then compare it to

   485 taking the derivative, but simplify the result.  The sizes

   486 taking the derivative, but simplify the result.  The sizes

   486 are given in \texttt{re.scala}. \hfill[1 Mark]

   487 are given in \texttt{re.scala}. \hfill[1 Mark]

   487 

   488 

   489   task.  The purpose here is that you will be marked for some ``power''

   490   task.  The purpose here is that you will be marked for some ``power''

   490   test cases. For example can your matcher decide within 30 seconds

   491   test cases. For example can your matcher decide within 30 seconds

   491   whether the regular expression $(a^*)^*\cdot b$ matches strings of the

   492   whether the regular expression $(a^*)^*\cdot b$ matches strings of the

   492   form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification

   493   form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification

   493   simplify the regular expression

   494   simplify the regular expression