8 \begin{document} |
8 \begin{document} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2019} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2019} |
10 |
10 |
11 \section*{Handout 4 (Sulzmann \& Lu Algorithm)} |
11 \section*{Handout 4 (Sulzmann \& Lu Algorithm)} |
12 |
12 |
13 So far our algorithm based on derivatives was only able to say |
13 So far our algorithm based on derivatives is only able to say |
14 yes or no depending on whether a string was matched by a regular |
14 yes or no depending on whether a string is matched by a regular |
15 expression or not. Often a more interesting question is to |
15 expression or not. Often a more interesting question is to |
16 find out \emph{how} a regular expression matched a string? |
16 find out \emph{how} a regular expression matched a string? |
17 Answering this question will also help us with the problem we |
17 Answering this question will also help us with the problem we |
18 are after, namely tokenising an input string. |
18 are after, namely tokenising an input string. |
19 |
19 |
84 return the empty list $Stars\,[]$, if no copy was needed |
84 return the empty list $Stars\,[]$, if no copy was needed |
85 for $r^*$. For sequence, there is exactly one value, composed |
85 for $r^*$. For sequence, there is exactly one value, composed |
86 of two component values ($v_1$ and $v_2$). |
86 of two component values ($v_1$ and $v_2$). |
87 |
87 |
88 My implementation of regular expressions and values in Scala is |
88 My implementation of regular expressions and values in Scala is |
89 shown below. I have in my implementation the convention that |
89 shown below. I use the convention that |
90 regular expressions are written entirely with upper-case |
90 regular expressions are written entirely with upper-case |
91 letters, while values just start with a single upper-case |
91 letters, whereas values start with a single upper-case |
92 character and the rest are lower-case letters. |
92 character and the rest are lower-case letters. |
93 |
93 |
94 {\small\lstinputlisting[language=Scala,numbers=none,linebackgroundcolor= |
94 {\small\lstinputlisting[language=Scala,numbers=none,linebackgroundcolor= |
95 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
95 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
96 {../progs/app01.scala}} |
96 {../progs/app01.scala}} |