105
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
237
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
217
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../langs}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../graphics}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
\usepackage{../data}
|
477
|
6 |
\usepackage{lstlinebgrd}
|
|
7 |
\definecolor{capri}{rgb}{0.0, 0.75, 1.0}
|
108
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
|
306
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
%%http://regexcrossword.com/challenges/cities/puzzles/1
|
398
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
%%https://jex.im/regulex/
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
%%https://www.reddit.com/r/ProgrammingLanguages/comments/42dlem/mona_compiler_development_part_2_parsing/
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
%%https://www.reddit.com/r/ProgrammingLanguages/comments/43wlkq/formal_grammar_for_csh_tsch_sh_or_bash/
|
112
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
%% regex displayers
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
%% https://regexper.com/#a%7Ca
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
%% https://www.debuggex.com
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
%% https://jex.im/regulex/#!embed=false&flags=&re=%5E(a%7Cb)*%3F%24
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
%% email validator
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
%% http://www.ex-parrot.com/%7Epdw/Mail-RFC822-Address.html
|
496
|
21 |
% https://jackfoxy.github.io/FsRegEx/emailregex.html
|
|
22 |
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
%% regex testers
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
% https://regex101.com
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
% http://regexr.com
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
%% emacs regexes
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
%% https://www.gnu.org/software/emacs/manual/html_node/elisp/Regular-Expressions.html
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
|
551
|
31 |
%% reasons for a new programming language
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
%% http://beautifulracket.com
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
|
418
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
% compiler explorer
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
% https://gcc.godbolt.org
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
|
503
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
%https://www.youtube.com/watch?v=gmhMQfFQu20
|
105
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
\begin{document}
|
550
|
39 |
\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018}
|
105
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
\section*{Handout 1}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
This module is about text processing, be it for web-crawlers,
|
492
|
44 |
compilers, dictionaries, DNA-data, ad filters and so on. When looking for a
|
471
|
45 |
particular string, like $abc$ in a large text we can use the
|
|
46 |
Knuth-Morris-Pratt algorithm, which is currently the most efficient
|
|
47 |
general string search algorithm. But often we do \emph{not} just look
|
477
|
48 |
for a particular string, but for string patterns. For example, in
|
550
|
49 |
program code we need to identify what are the keywords (\texttt{if}, \texttt{then},
|
|
50 |
\texttt{while}, \texttt{for}, etc), what are the identifiers (variable names). A pattern for
|
471
|
51 |
identifiers could be stated as: they start with a letter, followed by
|
477
|
52 |
zero or more letters, numbers and underscores. Often we also face the
|
471
|
53 |
problem that we are given a string (for example some user input) and
|
|
54 |
want to know whether it matches a particular pattern---be it an email
|
|
55 |
address, for example. In this way we can exclude user input that would
|
|
56 |
otherwise have nasty effects on our program (crashing it or making it
|
477
|
57 |
go into an infinite loop, if not worse). In tools like Snort, scanning
|
|
58 |
for computer viruses or filtering out spam usually involves scanning
|
|
59 |
for some signature (essentially a string pattern). The point is that
|
|
60 |
the fast Knuth-Morris-Pratt algorithm for strings is not good enough
|
|
61 |
for such string \emph{patterns}.\smallskip
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
\defn{Regular expressions} help with conveniently specifying
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
such patterns. The idea behind regular expressions is that
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
they are a simple method for describing languages (or sets of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
strings)\ldots at least languages we are interested in in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
computer science. For example there is no convenient regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
expression for describing the English language short of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
enumerating all English words. But they seem useful for
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
describing for example simple email addresses.\footnote{See
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
``8 Regular Expressions You Should Know''
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\url{http://goo.gl/5LoVX7}} Consider the following regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
expression
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\begin{equation}\label{email}
|
416
|
76 |
\texttt{[a-z0-9\_.-]+} \;\;\texttt{@}\;\; \texttt{[a-z0-9.-]+} \;\;\texttt{.}\;\; \texttt{[a-z.]\{2,6\}}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
\end{equation}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
|
416
|
79 |
\noindent where the first part, the user name, matches one or more lowercase
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
letters (\pcode{a-z}), digits (\pcode{0-9}), underscores, dots
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
and hyphens. The \pcode{+} at the end of the brackets ensures
|
471
|
82 |
the ``one or more''. Then comes the email \pcode{@}-sign, followed
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
by the domain name which must be one or more lowercase
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
letters, digits, underscores, dots or hyphens. Note there
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
cannot be an underscore in the domain name. Finally there must
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
be a dot followed by the toplevel domain. This toplevel domain
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
must be 2 to 6 lowercase letters including the dot. Example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
strings which follow this pattern are:
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}]
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
niceandsimple@example.org
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
very.common@example.co.uk
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
a.little.lengthy.but.fine@dept.example.ac.uk
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
other.email-with-dash@example.edu
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\noindent
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
But for example the following two do not
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
user@localserver
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
disposable.style.email.with+symbol@example.com
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
\end{lstlisting}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
|
471
|
106 |
\noindent according to the regular expression we specified in line
|
|
107 |
\eqref{email} above. Whether this is intended or not is a different
|
|
108 |
question (the second email above is actually an acceptable email
|
550
|
109 |
address according to the RFC 5322 standard for email addresses).
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
|
327
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
As mentioned above, identifiers, or variables, in program code
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
are often required to satisfy the constraints that they start
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
with a letter and then can be followed by zero or more letters
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
or numbers and also can include underscores, but not as the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
first character. Such identifiers can be recognised with the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
regular expression
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
\begin{center}
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
\pcode{[a-zA-Z] [a-zA-Z0-9_]*}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
\noindent Possible identifiers that match this regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
are \pcode{x}, \pcode{foo}, \pcode{foo_bar_1}, \pcode{A_very_42_long_object_name},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
but not \pcode{_i} and also not \pcode{4you}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
Many programming languages offer libraries that can be used to
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
validate such strings against regular expressions. Also there
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
are some common, and I am sure very familiar, ways of how to
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
construct regular expressions. For example in Scala we have
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
a library implementing the following regular expressions:
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
\begin{tabular}{lp{9cm}}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
\pcode{re*} & matches 0 or more occurrences of preceding
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
expression\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
\pcode{re+} & matches 1 or more occurrences of preceding
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
expression\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
\pcode{re?} & matches 0 or 1 occurrence of preceding
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
expression\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
\pcode{re\{n\}} & matches exactly \pcode{n} number of
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
occurrences of preceding expression\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m}
|
550
|
143 |
occurrences of the preceding expression\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
\pcode{[...]} & matches any single character inside the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
brackets\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
\pcode{[^...]} & matches any single character not inside the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
brackets\\
|
250
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
\pcode{...-...} & character ranges\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
\pcode{.} & matches every character except newline\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
\pcode{(re)} & groups regular expressions and remembers
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
matched text
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
\end{tabular}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
\noindent With this table you can figure out the purpose of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
the regular expressions in the web-crawlers shown Figures
|
250
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
\ref{crawler1}, \ref{crawler2} and
|
416
|
159 |
\ref{crawler3}. Note, however, the regular expression for
|
332
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
http-addresses in web-pages in Figure~\ref{crawler1}, Line 15,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
is intended to be
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
\pcode{"https?://[^"]*"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
\noindent It specifies that web-addresses need to start with a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
double quote, then comes \texttt{http} followed by an optional
|
332
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
\texttt{s} and so on until the closing double quote comes.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
Usually we would have to escape the double quotes in order to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
make sure we interpret the double quote as character, not as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
double quote for a string. But Scala's trick with triple
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
quotes allows us to omit this kind of escaping. As a result we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
can just write:
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
\pcode{""""https?://[^"]*"""".r}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
\noindent Note also that the convention in Scala is that
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
\texttt{.r} converts a string into a regular expression. I
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
leave it to you to ponder whether this regular expression
|
553
|
183 |
really captures all possible web-addresses. If you need a quick
|
554
|
184 |
recap about regular expressions and how the match strings,
|
|
185 |
here is a quick video
|
553
|
186 |
\url{https://youtu.be/bgBWp9EIlMM}.
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
\subsection*{Why Study Regular Expressions?}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
|
471
|
190 |
Regular expressions were introduced by Kleene in the 1950ies and they
|
|
191 |
have been object of intense study since then. They are nowadays pretty
|
|
192 |
much ubiquitous in computer science. There are many libraries
|
|
193 |
implementing regular expressions. I am sure you have come across them
|
|
194 |
before (remember the PRA module?). Why on earth then is there any
|
|
195 |
interest in studying them again in depth in this module? Well, one
|
|
196 |
answer is in the following two graphs about regular expression
|
550
|
197 |
matching in Python, Ruby and Java (Version 8).
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
198 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
199 |
\begin{center}
|
477
|
200 |
\begin{tabular}{@{\hspace{-1mm}}c@{\hspace{1mm}}c@{}}
|
|
201 |
\begin{tikzpicture}
|
|
202 |
\begin{axis}[
|
|
203 |
title={Graph: $\texttt{(a*)*\,b}$ and strings
|
|
204 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
|
205 |
xlabel={$n$},
|
|
206 |
x label style={at={(1.05,0.0)}},
|
|
207 |
ylabel={time in secs},
|
|
208 |
enlargelimits=false,
|
|
209 |
xtick={0,5,...,30},
|
|
210 |
xmax=33,
|
|
211 |
ymax=35,
|
|
212 |
ytick={0,5,...,30},
|
|
213 |
scaled ticks=false,
|
|
214 |
axis lines=left,
|
|
215 |
width=5.5cm,
|
|
216 |
height=4.5cm,
|
550
|
217 |
legend entries={Python, Java 8},
|
477
|
218 |
legend pos=north west,
|
|
219 |
legend cell align=left]
|
|
220 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
|
|
221 |
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
|
|
222 |
\end{axis}
|
|
223 |
\end{tikzpicture}
|
|
224 |
&
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
\begin{tikzpicture}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
\begin{axis}[
|
415
|
227 |
title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
|
|
228 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
|
229 |
xlabel={$n$},
|
|
230 |
x label style={at={(1.05,0.0)}},
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
ylabel={time in secs},
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
enlargelimits=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
xtick={0,5,...,30},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
xmax=33,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
ymax=35,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
ytick={0,5,...,30},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
axis lines=left,
|
415
|
239 |
width=5.5cm,
|
318
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
height=4.5cm,
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
legend entries={Python,Ruby},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
242 |
legend pos=north west,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
legend cell align=left]
|
448
|
244 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
|
245 |
\addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data};
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
\end{axis}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
\end{tikzpicture}
|
415
|
248 |
\end{tabular}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
|
563
|
251 |
\noindent This first graph shows that Python and Java 8 need
|
477
|
252 |
approximately 30 seconds to find out that the regular expression
|
|
253 |
$\texttt{(a*)*\,b}$ does not match strings of 28 \texttt{a}s.
|
|
254 |
Similarly, the second shows that Python needs approximately 29 seconds
|
|
255 |
for finding out whether a string of 28 \texttt{a}s matches the regular
|
|
256 |
expression \texttt{a?\{28\}\,a\{28\}}. Ruby is even slightly
|
448
|
257 |
worse.\footnote{In this example Ruby uses the slightly different
|
|
258 |
regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the
|
|
259 |
\texttt{a?} and \texttt{a} each occur $n$ times. More such test
|
562
|
260 |
cases can be found at \url{https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS}.}
|
477
|
261 |
Admittedly, these regular expressions are carefully chosen to exhibit
|
|
262 |
this exponential behaviour, but similar ones occur more often than one
|
|
263 |
wants in ``real life''. For example, on 20 July 2016 a similar regular
|
|
264 |
expression brought the webpage \href{http://stackexchange.com}{Stack
|
|
265 |
Exchange} to its knees:
|
407
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
266 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
267 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
268 |
\url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
269 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
270 |
|
417
|
271 |
\noindent I can also highly recommend a cool webtalk from an engineer
|
|
272 |
from Stack Exchange on the same subject:
|
|
273 |
|
|
274 |
\begin{center}
|
|
275 |
\url{https://vimeo.com/112065252}
|
|
276 |
\end{center}
|
|
277 |
|
407
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
278 |
\noindent
|
550
|
279 |
A similar problem also occurred in the Atom editor:
|
416
|
280 |
|
|
281 |
\begin{center}
|
|
282 |
\url{http://davidvgalbraith.com/how-i-fixed-atom/}
|
|
283 |
\end{center}
|
|
284 |
|
563
|
285 |
\noindent
|
554
|
286 |
and when somebody tried to match web-addresses using regular
|
|
287 |
expressions
|
|
288 |
|
|
289 |
\begin{center}
|
|
290 |
\url{https://www.tutorialdocs.com/article/regex-trap.html}
|
|
291 |
\end{center}
|
|
292 |
|
563
|
293 |
|
415
|
294 |
Such troublesome regular expressions are sometimes called \emph{evil
|
|
295 |
regular expressions} because they have the potential to make regular
|
|
296 |
expression matching engines to topple over, like in Python, Ruby and
|
563
|
297 |
Java 8. This ``toppling over'' is also sometimes called
|
550
|
298 |
\emph{catastrophic backtracking}. I have also seen the term
|
|
299 |
\emph{eternal matching} used for this. The problem with evil regular
|
|
300 |
expressions is that they can have some serious consequences, for
|
|
301 |
example, if you use them in your web-application. The reason is that
|
|
302 |
hackers can look for these instances where the matching engine behaves
|
|
303 |
badly and then mount a nice DoS-attack against your application. These
|
|
304 |
attacks are already have their own name: \emph{Regular Expression
|
|
305 |
Denial of Service Attacks (ReDoS)}.
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
306 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
307 |
It will be instructive to look behind the ``scenes'' to find
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
308 |
out why Python and Ruby (and others) behave so badly when
|
416
|
309 |
matching strings with evil regular expressions. But we will also look
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
310 |
at a relatively simple algorithm that solves this problem much
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
311 |
better than Python and Ruby do\ldots actually it will be two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
312 |
versions of the algorithm: the first one will be able to
|
477
|
313 |
process strings of approximately 1,100 \texttt{a}s in 23
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
314 |
seconds, while the second version will even be able to process
|
477
|
315 |
up to 11,000(!) in 5 seconds, see the graph below:
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
316 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
317 |
\begin{center}
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
318 |
\begin{tikzpicture}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
319 |
\begin{axis}[
|
415
|
320 |
title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
|
|
321 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
|
322 |
xlabel={$n$},
|
|
323 |
x label style={at={(1.05,0.0)}},
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
324 |
ylabel={time in secs},
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
325 |
enlargelimits=false,
|
477
|
326 |
xtick={0,3000,...,12000},
|
|
327 |
xmax=13000,
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
328 |
ymax=32,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
329 |
ytick={0,5,...,30},
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
330 |
scaled ticks=false,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
331 |
axis lines=left,
|
415
|
332 |
width=7cm,
|
|
333 |
height=4.5cm,
|
|
334 |
legend entries={Our Algorithm V1, Our Algorithm V2},
|
|
335 |
legend pos=outer north east]
|
|
336 |
\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
|
291
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
337 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
338 |
\end{axis}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
339 |
\end{tikzpicture}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
340 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
341 |
|
415
|
342 |
\noindent And in the case of the regular expression $\texttt{(a*)*\,b}$
|
563
|
343 |
and strings of \texttt{a}s we will beat Java 8 by factor of
|
415
|
344 |
approximately 1,000,000 (note the scale on the $x$-axis).
|
|
345 |
|
|
346 |
\begin{center}
|
|
347 |
\begin{tikzpicture}
|
|
348 |
\begin{axis}[
|
|
349 |
title={Graph: $\texttt{(a*)*\,b}$ and strings
|
|
350 |
$\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
|
|
351 |
xlabel={$n$},
|
|
352 |
x label style={at={(1.05,0.0)}},
|
|
353 |
ylabel={time in secs},
|
|
354 |
enlargelimits=false,
|
443
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
355 |
ymax=32,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
356 |
ytick={0,5,...,30},
|
415
|
357 |
axis lines=left,
|
|
358 |
width=7cm,
|
|
359 |
height=4.5cm,
|
|
360 |
legend entries={Our Algorithm V2},
|
|
361 |
legend pos=outer north east]
|
|
362 |
\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
|
|
363 |
\end{axis}
|
|
364 |
\end{tikzpicture}
|
|
365 |
\end{center}
|
|
366 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
367 |
\subsection*{Basic Regular Expressions}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
368 |
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
369 |
The regular expressions shown earlier for Scala, we
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
370 |
will call \emph{extended regular expressions}. The ones we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
371 |
will mainly study in this module are \emph{basic regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
372 |
expressions}, which by convention we will just call
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
373 |
\emph{regular expressions}, if it is clear what we mean. The
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
374 |
attraction of (basic) regular expressions is that many
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
375 |
features of the extended ones are just syntactic sugar.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
376 |
(Basic) regular expressions are defined by the following
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
377 |
grammar:
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
378 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
379 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
380 |
\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
381 |
$r$ & $::=$ & $\ZERO$ & null language\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
382 |
& $\mid$ & $\ONE$ & empty string / \texttt{""} / []\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
383 |
& $\mid$ & $c$ & single character\\
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
384 |
& $\mid$ & $r_1 + r_2$ & alternative / choice\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
385 |
& $\mid$ & $r_1 \cdot r_2$ & sequence\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
386 |
& $\mid$ & $r^*$ & star (zero or more)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
387 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
388 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
389 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
390 |
\noindent Because we overload our notation, there are some
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
391 |
subtleties you should be aware of. When regular expressions
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
392 |
are referred to, then $\ZERO$ (in bold font) does not stand for
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
393 |
the number zero: rather it is a particular pattern that does
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
394 |
not match any string. Similarly, in the context of regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
395 |
expressions, $\ONE$ does not stand for the number one but for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
396 |
a regular expression that matches the empty string. The letter
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
397 |
$c$ stands for any character from the alphabet at hand. Again
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
398 |
in the context of regular expressions, it is a particular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
399 |
pattern that can match the specified character. You should
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
400 |
also be careful with our overloading of the star: assuming you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
401 |
have read the handout about our basic mathematical notation,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
402 |
you will see that in the context of languages (sets of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
403 |
strings) the star stands for an operation on languages. Here
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
404 |
$r^*$ stands for a regular expression, which is different from
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
405 |
the operation on sets is defined as
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
406 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
407 |
\[
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
408 |
A\star\dn \bigcup_{0\le n} A^n
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
409 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
410 |
|
334
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
411 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
412 |
We will use parentheses to disambiguate regular expressions.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
413 |
Parentheses are not really part of a regular expression, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
414 |
indeed we do not need them in our code because there the tree
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
415 |
structure of regular expressions is always clear. But for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
416 |
writing them down in a more mathematical fashion, parentheses
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
417 |
will be helpful. For example we will write $(r_1 + r_2)^*$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
418 |
which is different from, say $r_1 + (r_2)^*$. The former means
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
419 |
roughly zero or more times $r_1$ or $r_2$, while the latter
|
550
|
420 |
means $r_1$, or zero or more times $r_2$. This will turn out to
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
421 |
be two different patterns, which match in general different
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
422 |
strings. We should also write $(r_1 + r_2) + r_3$, which is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
423 |
different from the regular expression $r_1 + (r_2 + r_3)$, but
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
424 |
in case of $+$ and $\cdot$ we actually do not care about the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
425 |
order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2
|
550
|
426 |
\cdot r_3$, respectively. The reasons for this carelessness will become
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
427 |
clear shortly.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
428 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
429 |
In the literature you will often find that the choice $r_1 +
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
430 |
r_2$ is written as $r_1\mid{}r_2$ or $r_1\mid\mid{}r_2$. Also,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
431 |
often our $\ZERO$ and $\ONE$ are written $\varnothing$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
432 |
$\epsilon$, respectively. Following the convention in the
|
550
|
433 |
literature, we will often omit the $\cdot$. This
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
434 |
is to make some concrete regular expressions more readable.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
435 |
For example the regular expression for email addresses shown
|
550
|
436 |
in \eqref{email} would fully expanded look like
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
437 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
438 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
439 |
\texttt{[...]+} \;\cdot\; \texttt{@} \;\cdot\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
440 |
\texttt{[...]+} \;\cdot\; \texttt{.} \;\cdot\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
441 |
\texttt{[...]\{2,6\}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
442 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
443 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
444 |
\noindent
|
471
|
445 |
which is much less readable than the regular expression in
|
|
446 |
\eqref{email}. Similarly for the regular expression that matches the
|
|
447 |
string $hello$ we should write
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
448 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
449 |
\[
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
450 |
h \cdot e \cdot l \cdot l \cdot o
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
451 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
452 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
453 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
454 |
but often just write {\it hello}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
455 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
456 |
If you prefer to think in terms of the implementation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
457 |
of regular expressions in Scala, the constructors and
|
245
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
458 |
classes relate as follows\footnote{More about Scala is
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
459 |
in the handout about \emph{A Crash-Course on Scala}.}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
460 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
461 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
462 |
\begin{tabular}{rcl}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
463 |
$\ZERO$ & $\mapsto$ & \texttt{ZERO}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
464 |
$\ONE$ & $\mapsto$ & \texttt{ONE}\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
465 |
$c$ & $\mapsto$ & \texttt{CHAR(c)}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
466 |
$r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
467 |
$r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
468 |
$r^*$ & $\mapsto$ & \texttt{STAR(r)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
469 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
470 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
471 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
472 |
A source of confusion might arise from the fact that we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
473 |
use the term \emph{basic regular expression} for the regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
474 |
expressions used in ``theory'' and defined above, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
475 |
\emph{extended regular expression} for the ones used in
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
476 |
``practice'', for example in Scala. If runtime is not an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
477 |
issue, then the latter can be seen as syntactic sugar of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
478 |
the former. For example we could replace
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
479 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
480 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
481 |
\begin{tabular}{rcl}
|
471
|
482 |
$r^+$ & $\mapsto$ & $r\cdot r^*$\\
|
|
483 |
$r^?$ & $\mapsto$ & $\ONE + r$\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
484 |
$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
485 |
$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
486 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
487 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
488 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
489 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
490 |
\subsection*{The Meaning of Regular Expressions}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
491 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
492 |
So far we have only considered informally what the
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
493 |
\emph{meaning} of a regular expression is. This is not good
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
494 |
enough for specifications of what algorithms are supposed to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
495 |
do or which problems they are supposed to solve.
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
496 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
497 |
To define the meaning of a regular expression we will
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
498 |
associate with every regular expression a language, or set of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
499 |
strings. This language contains all the strings the regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
500 |
expression is supposed to match. To understand what is going
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
501 |
on here it is crucial that you have read the handout
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
502 |
about basic mathematical notations.
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
503 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
504 |
The \defn{meaning of a regular expression} can be defined
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
505 |
by a recursive function called $L$ (for language), which
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
506 |
is defined as follows
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
507 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
508 |
\begin{center}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
509 |
\begin{tabular}{rcll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
510 |
$L(\ZERO)$ & $\dn$ & $\{\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
511 |
$L(\ONE)$ & $\dn$ & $\{[]\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
512 |
$L(c)$ & $\dn$ & $\{"c"\}$ & or equivalently $\dn \{[c]\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
513 |
$L(r_1+ r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$\\
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
514 |
$L(r_1 \cdot r_2)$ & $\dn$ & $L(r_1) \,@\, L(r_2)$\\
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
515 |
$L(r^*)$ & $\dn$ & $(L(r))\star$\\
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
516 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
517 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
518 |
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
519 |
\noindent As a result we can now precisely state what the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
520 |
meaning, for example, of the regular expression $h \cdot
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
521 |
e \cdot l \cdot l \cdot o$ is, namely
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
522 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
523 |
\[
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
524 |
L(h \cdot e \cdot l \cdot l \cdot o) = \{"hello"\}
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
525 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
526 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
527 |
\noindent This is expected because this regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
528 |
is only supposed to match the ``$hello$''-string. Similarly if
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
529 |
we have the choice-regular-expression $a + b$, its meaning is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
530 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
531 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
532 |
L(a + b) = \{"a", "b"\}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
533 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
534 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
535 |
\noindent You can now also see why we do not make a difference
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
536 |
between the different regular expressions $(r_1 + r_2) + r_3$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
537 |
and $r_1 + (r_2 + r_3)$\ldots they are not the same regular
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
538 |
expression, but they have the same meaning. For example
|
318
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
539 |
you can do the following calculation which shows they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
540 |
have the same meaning:
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
541 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
542 |
\begin{eqnarray*}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
543 |
L((r_1 + r_2) + r_3) & = & L(r_1 + r_2) \cup L(r_3)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
544 |
& = & L(r_1) \cup L(r_2) \cup L(r_3)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
545 |
& = & L(r_1) \cup L(r_2 + r_3)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
546 |
& = & L(r_1 + (r_2 + r_3))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
547 |
\end{eqnarray*}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
548 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
549 |
The point of the definition of $L$ is that we can use it to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
550 |
precisely specify when a string $s$ is matched by a regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
551 |
expression $r$, namely if and only if $s \in L(r)$. In fact we
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
552 |
will write a program \pcode{match} that takes any string $s$
|
492
|
553 |
and any regular expression $r$ as arguments and returns
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
554 |
\emph{yes}, if $s \in L(r)$ and \emph{no}, if $s \not\in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
555 |
L(r)$. We leave this for the next lecture.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
556 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
557 |
There is one more feature of regular expressions that is worth
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
558 |
mentioning. Given some strings, there are in general many
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
559 |
different regular expressions that can recognise these
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
560 |
strings. This is obvious with the regular expression $a + b$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
561 |
which can match the strings $a$ and $b$. But also the regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
562 |
expression $b + a$ would match the same strings. However,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
563 |
sometimes it is not so obvious whether two regular expressions
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
564 |
match the same strings: for example do $r^*$ and $\ONE + r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
565 |
\cdot r^*$ match the same strings? What about $\ZERO^*$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
566 |
and $\ONE^*$? This suggests the following relation between
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
567 |
\defn{equivalent regular expressions}:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
568 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
569 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
570 |
r_1 \equiv r_2 \;\dn\; L(r_1) = L(r_2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
571 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
572 |
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
573 |
\noindent That means two regular expressions are said to be
|
550
|
574 |
equivalent if they match the same set of strings. That is
|
563
|
575 |
their meanings is the same. Therefore we
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
576 |
do not really distinguish between the different regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
577 |
expression $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
578 |
because they are equivalent. I leave you to the question
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
579 |
whether
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
580 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
581 |
\[
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
582 |
\ZERO^* \equiv \ONE^*
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
583 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
584 |
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
585 |
\noindent holds or not? Such equivalences will be important
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
586 |
for our matching algorithm, because we can use them to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
587 |
simplify regular expressions, which will mean we can speed
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
588 |
up the calculations.
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
589 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
590 |
\subsection*{My Fascination for Regular Expressions}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
591 |
|
471
|
592 |
Up until a few years ago I was not really interested in regular
|
|
593 |
expressions. They have been studied for the last 60 years (by smarter
|
|
594 |
people than me)---surely nothing new can be found out about them. I
|
|
595 |
even have the vague recollection that I did not quite understand them
|
|
596 |
during my undergraduate study. If I remember correctly,\footnote{That
|
|
597 |
was really a long time ago.} I got utterly confused about $\ONE$
|
|
598 |
(which my lecturer wrote as $\epsilon$) and the empty string (which he
|
|
599 |
also wrote as $\epsilon$).\footnote{Obviously the lecturer must have
|
550
|
600 |
been bad ;o)} Since then, I have used regular expressions for
|
471
|
601 |
implementing lexers and parsers as I have always been interested in
|
|
602 |
all kinds of programming languages and compilers, which invariably
|
|
603 |
need regular expressions in some form or shape.
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
604 |
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
605 |
To understand my fascination \emph{nowadays} with regular
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
606 |
expressions, you need to know that my main scientific interest
|
471
|
607 |
for the last 17 years has been with theorem provers. I am a
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
608 |
core developer of one of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
609 |
them.\footnote{\url{http://isabelle.in.tum.de}} Theorem
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
610 |
provers are systems in which you can formally reason about
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
611 |
mathematical concepts, but also about programs. In this way
|
550
|
612 |
theorem provers can help with the menacing problem of writing bug-free code. Theorem provers have
|
416
|
613 |
proved already their value in a number of cases (even in
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
614 |
terms of hard cash), but they are still clunky and difficult
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
615 |
to use by average programmers.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
616 |
|
471
|
617 |
Anyway, in about 2011 I came across the notion of \defn{derivatives of
|
|
618 |
regular expressions}. This notion allows one to do almost all
|
|
619 |
calculations with regular expressions on the level of regular
|
|
620 |
expressions, not needing any automata (you will see we only touch
|
|
621 |
briefly on automata in lecture 3). Automata are usually the main
|
|
622 |
object of study in formal language courses. The avoidance of automata
|
550
|
623 |
is crucial for me because automata are graphs and it is rather difficult to
|
471
|
624 |
reason about graphs in theorem provers. In contrast, reasoning about
|
|
625 |
regular expressions is easy-peasy in theorem provers. Is this
|
|
626 |
important? I think yes, because according to Kuklewicz nearly all
|
|
627 |
POSIX-based regular expression matchers are
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
628 |
buggy.\footnote{\url{http://www.haskell.org/haskellwiki/Regex_Posix}}
|
471
|
629 |
With my PhD student Fahad Ausaf I proved the correctness for one such
|
|
630 |
matcher that was proposed by Sulzmann and Lu in
|
|
631 |
2014.\footnote{\url{http://goo.gl/bz0eHp}} Hopefully we can prove that
|
|
632 |
the machine code(!) that implements this code efficiently is correct
|
|
633 |
also. Writing programs in this way does not leave any room for
|
|
634 |
potential errors or bugs. How nice!
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
635 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
636 |
What also helped with my fascination with regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
637 |
is that we could indeed find out new things about them that
|
416
|
638 |
have surprised some experts. Together with two colleagues from China, I was
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
639 |
able to prove the Myhill-Nerode theorem by only using regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
640 |
expressions and the notion of derivatives. Earlier versions of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
641 |
this theorem used always automata in the proof. Using this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
642 |
theorem we can show that regular languages are closed under
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
643 |
complementation, something which Gasarch in his
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
644 |
blog\footnote{\url{http://goo.gl/2R11Fw}} assumed can only be
|
550
|
645 |
shown via automata. So even somebody who has written a 700+-page
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
646 |
book\footnote{\url{http://goo.gl/fD0eHx}} on regular
|
550
|
647 |
expressions did not know better. Well, we showed it can also be
|
507
|
648 |
done with regular expressions only.\footnote{\url{http://nms.kcl.ac.uk/christian.urban/Publications/posix.pdf}}
|
471
|
649 |
What a feeling when you are an outsider to the subject!
|
243
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
650 |
|
471
|
651 |
To conclude: Despite my early ignorance about regular expressions, I
|
550
|
652 |
find them now extremely interesting. They have practical importance
|
471
|
653 |
(remember the shocking runtime of the regular expression matchers in
|
|
654 |
Python, Ruby and Java in some instances and the problems in Stack
|
550
|
655 |
Exchange and the Atom editor). They are used in tools like Snort and
|
|
656 |
Bro in order to monitor network traffic. They have a beautiful mathematical
|
|
657 |
theory behind them, which can be sometimes quite deep and which
|
|
658 |
sometimes contains hidden snares. People who are not very familiar
|
|
659 |
with the mathematical background of regular expressions get them
|
492
|
660 |
consistently wrong (this is surprising given they are a supposed to be
|
|
661 |
core skill for computer scientists). The hope is that we can do better
|
|
662 |
in the future---for example by proving that the algorithms actually
|
471
|
663 |
satisfy their specification and that the corresponding implementations
|
|
664 |
do not contain any bugs. We are close, but not yet quite there.
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
665 |
|
332
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
666 |
Notwithstanding my fascination, I am also happy to admit that regular
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
667 |
expressions have their shortcomings. There are some well-known
|
471
|
668 |
``theoretical'' shortcomings, for example recognising strings of the
|
|
669 |
form $a^{n}b^{n}$ is not possible with regular expressions. This means
|
550
|
670 |
for example if we try to recognise whether parentheses are well-nested
|
492
|
671 |
in an expression is impossible with (basic) regular expressions. I am
|
|
672 |
not so bothered by these shortcomings. What I am bothered about is
|
|
673 |
when regular expressions are in the way of practical programming. For
|
|
674 |
example, it turns out that the regular expression for email addresses
|
|
675 |
shown in \eqref{email} is hopelessly inadequate for recognising all of
|
|
676 |
them (despite being touted as something every computer scientist
|
|
677 |
should know about). The W3 Consortium (which standardises the Web)
|
|
678 |
proposes to use the following, already more complicated regular
|
|
679 |
expressions for email addresses:
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
680 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
681 |
{\small\begin{lstlisting}[language={},keywordstyle=\color{black},numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
682 |
[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9-]+(?:\.[a-zA-Z0-9-]+)*
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
683 |
\end{lstlisting}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
684 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
685 |
\noindent But they admit that by using this regular expression
|
471
|
686 |
they wilfully violate the RFC 5322 standard, which specifies
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
687 |
the syntax of email addresses. With their proposed regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
688 |
expression they are too strict in some cases and too lax in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
689 |
others. Not a good situation to be in. A regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
690 |
that is claimed to be closer to the standard is shown in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
691 |
Figure~\ref{monster}. Whether this claim is true or not, I
|
416
|
692 |
would not know---the only thing I can say about this regular
|
248
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
693 |
expression is it is a monstrosity. However, this might
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
694 |
actually be an argument against the RFC standard, rather than
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
695 |
against regular expressions. A similar argument is made in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
696 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
697 |
\begin{center}
|
570
|
698 |
\url{http://elliot.land/post/its-impossible-to-validate-an-email-address}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
699 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
700 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
701 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
702 |
\noindent which explains some of the crazier parts of email
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
703 |
addresses. Still it is good to know that some tasks in text
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
704 |
processing just cannot be achieved by using regular
|
471
|
705 |
expressions. But for what we want to use them (lexing) they are
|
473
|
706 |
pretty good.\medskip
|
|
707 |
|
|
708 |
\noindent
|
|
709 |
Finally there is a joke about regular expressions:
|
|
710 |
|
|
711 |
\begin{quote}\it
|
|
712 |
``Sometimes you have a programming problem and it seems like the
|
|
713 |
best solution is to use regular expressions; now you have two
|
|
714 |
problems.''
|
|
715 |
\end{quote}
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
716 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
717 |
|
477
|
718 |
\begin{figure}[p]\small
|
550
|
719 |
\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
|
477
|
720 |
{../progs/crawler1.scala}
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
721 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
722 |
\caption{The Scala code for a simple web-crawler that checks
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
723 |
for broken links in a web-page. It uses the regular expression
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
724 |
\texttt{http\_pattern} in Line~\ref{httpline} for recognising
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
725 |
URL-addresses. It finds all links using the library function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
726 |
\texttt{findAllIn} in Line~\ref{findallline}.\label{crawler1}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
727 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
728 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
729 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
730 |
|
477
|
731 |
|
|
732 |
\begin{figure}[p]\small
|
550
|
733 |
\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
|
477
|
734 |
{../progs/crawler2.scala}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
735 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
736 |
\caption{A version of the web-crawler that only follows links
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
737 |
in ``my'' domain---since these are the ones I am interested in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
738 |
to fix. It uses the regular expression \texttt{my\_urls} in
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
739 |
Line~\ref{myurlline} to check for my name in the links. The
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
740 |
main change is in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
741 |
Lines~\ref{changestartline}--\ref{changeendline} where there
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
742 |
is a test whether URL is in ``my'' domain or
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
743 |
not.\label{crawler2}}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
744 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
745 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
746 |
|
477
|
747 |
\begin{figure}[p]\small
|
550
|
748 |
\lstinputlisting[numbers=left,linebackgroundcolor={\ifodd\value{lstnumber}\color{capri!3}\fi}]
|
477
|
749 |
{../progs/crawler3.scala}
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
750 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
751 |
\caption{A small email harvester---whenever we download a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
752 |
web-page, we also check whether it contains any email
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
753 |
addresses. For this we use the regular expression
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
754 |
\texttt{email\_pattern} in Line~\ref{emailline}. The main
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
755 |
change is in Line~\ref{mainline} where all email addresses
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
756 |
that can be found in a page are printed.\label{crawler3}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
757 |
|
242
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
758 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
759 |
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
760 |
\begin{figure}[p]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
761 |
\tiny
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
762 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
763 |
\begin{minipage}{0.8\textwidth}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
764 |
\lstinputlisting[language={},keywordstyle=\color{black},numbers=none]{../progs/email-rexp}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
765 |
\end{minipage}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
766 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
767 |
|
404
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
768 |
\caption{Nothing that can be said about this regular
|
416
|
769 |
expression\ldots{}except it is a monstrosity.\label{monster}}
|
244
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
770 |
\end{figure}
|
108
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
771 |
|
112
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
772 |
|
105
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
773 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
774 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
775 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
776 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
777 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
778 |
%%% End:
|