diff -r c7009356ddd8 -r c0600f8b6427 handouts/ho02.tex --- a/handouts/ho02.tex Wed May 29 13:25:30 2024 +0100 +++ b/handouts/ho02.tex Thu Sep 19 15:47:33 2024 +0100 @@ -8,7 +8,7 @@ \begin{document} \fnote{\copyright{} Christian Urban, King's College London, - 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023} + 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024} \section*{Handout 2 (Regular Expression Matching)} @@ -389,10 +389,10 @@ construct the regular expression for $s$ by calling $\textit{der}$ with $r_1$ and ``appending'' $r_2$. There is however one exception to this simple rule: if $r_1$ can match the empty string, then -all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is +all of $c\!::\!s$ is matched by $r_2$. Therefore in case $r_1$ is nullable (that is can match the empty string) we have to allow the choice $\textit{der}\,c\,r_2$ for calculating the regular -expression that can match $s$. Therefore we have to add the +expression that can match $s$. This means we have to add the regular expression $\textit{der}\,c\,r_2$ in the result. The $*$-case is again simple: if $r^*$ matches a string of the form $c\!::\!s$, then the first part must be ``matched'' by a @@ -788,7 +788,7 @@ (23/Aug/2016) I found another place where this algorithm can be sped up (this idea is not integrated with what is coming next, but I present it nonetheless). The idea is to not define \texttt{ders} -that it iterates the derivative character-by-character, but in bigger +so that it iterates the derivative character-by-character, but in bigger chunks. The resulting code for \texttt{ders2} looks as follows: \lstinputlisting[numbers=none]{../progs/app52.scala}