equal
deleted
inserted
replaced
12 This lecture is about implementing a more efficient regular |
12 This lecture is about implementing a more efficient regular |
13 expression matcher (the plots on the right)---more efficient |
13 expression matcher (the plots on the right)---more efficient |
14 than the matchers from regular expression libraries in Ruby |
14 than the matchers from regular expression libraries in Ruby |
15 and Python (the plots on the left). These plots show the |
15 and Python (the plots on the left). These plots show the |
16 running time for the evil regular expression |
16 running time for the evil regular expression |
17 $a^?^{\{n\}}\cdot a^{\{n\}}$ and strings composed of $n$ \pcode{a}s. |
17 $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings composed of $n$ \pcode{a}s. |
18 We will use this regular expression and strings as running |
18 We will use this regular expression and strings as running |
19 example. To see the substantial differences in the two plots |
19 example. To see the substantial differences in the two plots |
20 below, note the different scales of the $x$-axes. |
20 below, note the different scales of the $x$-axes. |
21 |
21 |
22 |
22 |
411 matching and recursion allow us to mimic the mathematical |
411 matching and recursion allow us to mimic the mathematical |
412 definitions very closely.\label{scala1}} |
412 definitions very closely.\label{scala1}} |
413 \end{figure} |
413 \end{figure} |
414 |
414 |
415 For running the algorithm with our favourite example, the evil |
415 For running the algorithm with our favourite example, the evil |
416 regular expression $a^?^{\{n\}}a^{\{n\}}$, we need to implement |
416 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement |
417 the optional regular expression and the exactly $n$-times |
417 the optional regular expression and the exactly $n$-times |
418 regular expression. This can be done with the translations |
418 regular expression. This can be done with the translations |
419 |
419 |
420 \lstinputlisting[numbers=none]{../progs/app51.scala} |
420 \lstinputlisting[numbers=none]{../progs/app51.scala} |
421 |
421 |