142 |
142 |
143 \subsection*{Reference Implementation} |
143 \subsection*{Reference Implementation} |
144 |
144 |
145 This Scala assignment comes with a reference implementation in form of |
145 This Scala assignment comes with a reference implementation in form of |
146 a \texttt{jar}-file. This allows you to run any test cases on your own |
146 a \texttt{jar}-file. This allows you to run any test cases on your own |
147 computer. For example you can call Scala on the command line with the |
147 computer. For example you can call \texttt{scala-cli} on the command |
148 option \texttt{-cp re.jar} and then query any function from the |
148 line with the option \texttt{--extra-jars re.jar} and then query any function |
149 \texttt{re.scala} template file. As usual you have to prefix the calls |
149 from the \texttt{re.scala} template file. As usual you have to prefix |
150 with \texttt{M3} or import this object. Since some tasks |
150 the calls with \texttt{M3} or import this object. Since some tasks |
151 are time sensitive, you can check the reference implementation as |
151 are time sensitive, you can check the reference implementation as |
152 follows: if you want to know, for example, how long it takes to match |
152 follows: if you want to know, for example, how long it takes to match |
153 strings of $a$'s using the regular expression $(a^*)^*\cdot b$ you can |
153 strings of $a$'s using the regular expression $(a^*)^*\cdot b$ you can |
154 query as follows: |
154 query as follows: |
155 |
155 |
156 |
156 |
157 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
157 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
158 $ scala -cp re.jar |
158 $ scala-cli --extra-jars re.jar |
159 scala> import M3._ |
159 scala> import M3._ |
160 scala> for (i <- 0 to 5000000 by 500000) { |
160 scala> for (i <- 0 to 5000000 by 500000) { |
161 | println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.") |
161 | println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.") |
162 | } |
162 | } |
163 0: 0.00002 secs. |
163 0: 0.00002 secs. |
341 |
341 |
342 In the first case we just return whatever has accumulated in |
342 In the first case we just return whatever has accumulated in |
343 $acc$. In the fourth case we spill out the $rs$ by appending the |
343 $acc$. In the fourth case we spill out the $rs$ by appending the |
344 $rs$ to the end of the accumulator. Similarly in the last case we |
344 $rs$ to the end of the accumulator. Similarly in the last case we |
345 append the single regular expression $r$ to the end of the |
345 append the single regular expression $r$ to the end of the |
346 accumulator. I let you think why the ``end'' is needed. \mbox{}\hfill\mbox{[1 Mark]} |
346 accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]} |
347 |
347 |
348 \item[(5)] Before we can simplify regular expressions, we need what is often called |
348 \item[(5)] Before we can simplify regular expressions, we need what is often called |
349 \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors |
349 \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors |
350 \texttt{ALTs} and \texttt{SEQs} give us alternatives and sequences, respectively, \emph{smart} |
350 \texttt{ALTs} and \texttt{SEQs} give us alternatives and sequences, respectively, \emph{smart} |
351 constructors might return something different depending on what list of regular expressions |
351 constructors might return something different depending on what list of regular expressions |
514 \texttt{catastrophic9.java}, \texttt{catastrophic.js}, |
514 \texttt{catastrophic9.java}, \texttt{catastrophic.js}, |
515 \texttt{catastrophic.py} etc on KEATS). Compare this with the matcher |
515 \texttt{catastrophic.py} etc on KEATS). Compare this with the matcher |
516 you have implemented. How long can a string of $a$'s be in your |
516 you have implemented. How long can a string of $a$'s be in your |
517 matcher and still stay within the 30 seconds time limit? It should be |
517 matcher and still stay within the 30 seconds time limit? It should be |
518 mu(uu)$^*$ch better than your off-the-shelf matcher in your |
518 mu(uu)$^*$ch better than your off-the-shelf matcher in your |
519 bog-standard language. |
519 bog-standard programming language. |
520 |
520 |
521 \begin{center} |
521 \begin{center} |
522 \begin{tabular}{@{}cc@{}} |
522 \begin{tabular}{@{}cc@{}} |
523 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings |
523 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings |
524 $\underbrace{a\ldots a}_{n}$}\medskip\\ |
524 $\underbrace{a\ldots a}_{n}$}\medskip\\ |