# HG changeset patch # User Christian Urban # Date 1410579025 -3600 # Node ID 35104ee14f8780f51d49b5c90b852d16784595e5 # Parent 10f02605a46acbaf7b068a22685f561125153eb5 updated diff -r 10f02605a46a -r 35104ee14f87 data.sty --- a/data.sty Sun Sep 07 08:37:44 2014 +0100 +++ b/data.sty Sat Sep 13 04:30:25 2014 +0100 @@ -23,19 +23,19 @@ \begin{filecontents}{re-ruby.data} 1 0.00006 -2 0.00003 -3 0.00001 -4 0.00001 +#2 0.00003 +#3 0.00001 +#4 0.00001 5 0.00001 -6 0.00002 -7 0.00002 -8 0.00004 -9 0.00007 +#6 0.00002 +#7 0.00002 +#8 0.00004 +#9 0.00007 10 0.00013 -11 0.00026 -12 0.00055 -13 0.00106 -14 0.00196 +#11 0.00026 +#12 0.00055 +#13 0.00106 +#14 0.00196 15 0.00378 16 0.00764 17 0.01606 diff -r 10f02605a46a -r 35104ee14f87 graphics.sty --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graphics.sty Sat Sep 13 04:30:25 2014 +0100 @@ -0,0 +1,3 @@ +\usepackage{tikz} +\usepackage{pgf} +\usetikzlibrary{plotmarks} diff -r 10f02605a46a -r 35104ee14f87 handouts/ho01.pdf Binary file handouts/ho01.pdf has changed diff -r 10f02605a46a -r 35104ee14f87 handouts/ho01.tex --- a/handouts/ho01.tex Sun Sep 07 08:37:44 2014 +0100 +++ b/handouts/ho01.tex Sat Sep 13 04:30:25 2014 +0100 @@ -1,18 +1,415 @@ \documentclass{article} \usepackage{../style} \usepackage{../langs} - +\usepackage{../graphics} +\usepackage{../data} +\usepackage{longtable} \begin{document} \section*{Handout 1} -This module is about the processing of strings. Lets start with what we mean by \emph{strings}. Strings -(they are also sometimes referred to as \emph{words}) are lists of characters drawn from an \emph{alphabet}. -If nothing else is specified, we usually assume -the alphabet consists of just the lower-case letters $a$, $b$, \ldots, $z$. Sometimes, however, we explicitly -restrict strings to contain, for example, only the letters $a$ and $b$. In this case we say the alphabet is the set $\{a, b\}$. +This module is about text processing, be it for web-crawlers, +compilers, dictionaries, DNA-data and so on. When looking for +a particular string in a large text we can use the +Knuth-Morris-Pratt algorithm, which is currently the most +efficient general string search algorithm. But often we do +\emph{not} look for just a particular string, but for string +patterns. For example in programming code we need to identify +what are the keywords, what are the identifiers etc. Also +often we face the problem that we are given a string (for +example some user input) and want to know whether it matches a +particular pattern. For example for excluding some user input +that would otherwise have nasty effects on our program +(crashing or going into an infinite loop, if not worse). +\defn{Regular expressions} help with conveniently specifying +such patterns. + + +The idea behind regular expressions is that they are a simple +method for describing languages (or sets of strings)...at +least languages we are interested in in computer science. For +example there is no convenient regular expression for +describing the English language short of enumerating all +English words. But they seem useful for describing for example +email addresses.\footnote{See ``8 Regular Expressions You +Should Know'' \url{http://goo.gl/5LoVX7}} Consider the +following regular expression + +\begin{equation}\label{email} +\texttt{[a-z0-9\_.-]+ @ [a-z0-9.-]+ . [a-z.]\{2,6\}} +\end{equation} + +\noindent where the first part matches one or more lowercase +letters (\pcode{a-z}), digits (\pcode{0-9}), underscores, dots +or hyphens. The \pcode{+} ensures the ``one or more''. Then +comes the \pcode{@}-sign, followed by the domain name which +must be one or more lowercase letters, digits, underscores, +dots or hyphens. Note there cannot be an underscore in the +domain name. Finally there must be a dot followed by the +toplevel domain. This toplevel domain must be 2 to 6 lowercase +letters including the dot. Example strings which follow this +pattern are: + +\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}] +niceandsimple@example.com +very.common@example.org +a.little.lengthy.but.fine@dept.example.co.uk +other.email-with-dash@example.ac.uk +\end{lstlisting} + + +\noindent +But for example the following two do not: + +\begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}] +user@localserver +disposable.style.email.with+symbol@example.com +\end{lstlisting} + +Many programming language offer libraries that can be used to +validate such strings against regular expressions, like the +one for email addresses in \eqref{email}. There are some +common, and I am sure very familiar, ways how to construct +regular expressions. For example in Scala we have + +\begin{center} +\begin{longtable}{lp{9cm}} +\pcode{re*} & matches 0 or more occurrences of preceding +expression\\ +\pcode{re+} & matches 1 or more occurrences of preceding +expression\\ +\pcode{re?} & matches 0 or 1 occurrence of preceding +expression\\ +\pcode{re\{n\}} & matches exactly \pcode{n} number of +occurrences\\ +\pcode{re\{n,m\}} & matches at least \pcode{n} and at most {\tt m} +occurences of the preceding expression\\ +\pcode{[...]} & matches any single character inside the +brackets\\ +\pcode{[^...]} & matches any single character not inside the +brackets\\ +\pcode{..-..} & character ranges\\ +\pcode{\\d} & matches digits; equivalent to \pcode{[0-9]} +\end{longtable} +\end{center} + +\noindent With this you can figure out the purpose of the +regular expressions in the web-crawlers shown Figures +\ref{crawler1}, \ref{crawler2} and \ref{crawler3}. Note the +regular expression for http-addresses in web-pages: + +\[ +\pcode{"https?://[^"]*"} +\] + +\noindent It specifies that web-addresses need to start with a +double quote, then comes \texttt{http} followed by an optional +\texttt{s} and so on. Usually we would have to escape the +double quotes in order to make sure we interpret the double +quote as character, not as double quote for a string. But +Scala's trick with triple quotes allows us to omit this kind +of escaping. As a result we can just write: + +\[ +\pcode{""""https?://[^"]*"""".r} +\] + +\noindent Not also that the convention in Scala is that +\texttt{.r} converts a string into a regular expression. I +leave it to you to ponder whether this regular expression +really captures all possible web-addresses.\bigskip + +Regular expressions were introduced by Kleene in the 1950ies +and they have been object of intense study since then. They +are nowadays pretty much ubiquitous in computer science. I am +sure you have come across them before. Why on earth then is +there any interest in studying them again in depth in this +module? Well, one answer is in the following graph about +regular expression matching in Python and in Ruby. + +\begin{center} +\begin{tikzpicture}[y=.1cm, x=.15cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (30,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0,5,...,30} + \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {number of \texttt{a}s}; + \node[rotate=90,above=0.8cm] at (y axis mid) {time in secs}; + %plots + \draw[color=blue] plot[mark=*] + file {re-python.data}; + \draw[color=brown] plot[mark=triangle*] + file {re-ruby.data}; + %legend + \begin{scope}[shift={(4,20)}] + \draw[color=blue] (0,0) -- + plot[mark=*] (0.25,0) -- (0.5,0) + node[right]{\small Python}; + \draw[yshift=-\baselineskip, color=brown] (0,0) -- + plot[mark=triangle*] (0.25,0) -- (0.5,0) + node[right]{\small Ruby}; + \end{scope} +\end{tikzpicture} +\end{center} + +\noindent This graph shows that Python needs approximately 29 +seconds in order to find out that a string of 28 \texttt{a}s +matches the regular expression \texttt{[a?]\{28\}[a]\{28\}}. +Ruby is even slightly worse.\footnote{In this example Ruby +uses the slightly different regular expression +\texttt{a?a?a?...a?a?aaa...aa}, where the \texttt{a?} and +\texttt{a} each occur $n$ times.} Admittedly, this regular +expression is carefully chosen to exhibit this exponential +behaviour, but similar ones occur more often than one wants in +``real life''. They are sometimes called \emph{evil regular +expressions} because they have the potential to make regular +expression matching engines topple over, like in Python and +Ruby. The problem is that this can have some serious +consequences, for example, if you use them in your +web-application, because hackers can look for these instances +where the matching engine behaves badly and mount a nice +DoS-attack against your application. + +It will be instructive to look behind the ``scenes''to find +out why Python and Ruby (and others) behave so badly when +matching with evil regular expressions. But we will also look +at a relatively simple algorithm that solves this problem much +better than Python and Ruby do\ldots actually it will be two +versions of the algorithm: the first one will be able to +process strings of approximately 1,000 \texttt{a}s in 30 +seconds, while the second version will even be able to +process up to 12,000 in less than 10(!) seconds, see the graph +below: + +\begin{center} +\begin{tikzpicture}[y=.1cm, x=.0006cm] + %axis + \draw (0,0) -- coordinate (x axis mid) (12000,0); + \draw (0,0) -- coordinate (y axis mid) (0,30); + %ticks + \foreach \x in {0,2000,...,12000} + \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\x}; + \foreach \y in {0,5,...,30} + \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\y}; + %labels + \node[below=0.6cm] at (x axis mid) {number of \texttt{a}s}; + \node[rotate=90, above=0.8cm] at (y axis mid) {time in secs}; + + %plots + \draw[color=green] plot[mark=square*, mark options={fill=white} ] + file {re2b.data}; + \draw[color=black] plot[mark=square*, mark options={fill=white} ] + file {re3.data}; +\end{tikzpicture} +\end{center} + +\subsection*{Basic Regular Expressions} + +The regular expressions shown above we will call +\defn{extended regular expressions}. The ones we will mainly +study are \emph{basic regular expressions}, which by +convention we will just call regular expressions, if it is +clear what we mean. The attraction of (basic) regular +expressions is that many features of the extended one are just +syntactic suggar. (Basic) regular expressions are defined by +the following grammar: + +\begin{center} +\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l} + $r$ & $::=$ & $\varnothing$ & null\\ + & $\mid$ & $\epsilon$ & empty string / "" / []\\ + & $\mid$ & $c$ & single character\\ + & $\mid$ & $r_1 \cdot r_2$ & sequence\\ + & $\mid$ & $r_1 + r_2$ & alternative / choice\\ + & $\mid$ & $r^*$ & star (zero or more)\\ + \end{tabular} +\end{center} + +\noindent Because we overload our notation, there are some +subtleties you should be aware of. First, when regular +expressions are referred to then $\varnothing$ does not stand +for the empty set: it is a particular pattern that does not +match any string. Similarly, in the context of regular +expressions, $\epsilon$ does not stand for the empty string +(as in many places in the literature) but for a pattern that +matches the empty string. Second, the letter $c$ stands for +any character from the alphabet at hand. Again in the context +of regular expressions, it is a particular pattern that can +match the specified string. Third, you should also be careful +with the our overloading of the star: assuming you have read +the handout about our basic mathematical notation, you will +see that in the context of languages (sets of strings) the +star stands for an operation on languages. While $r^*$ stands +for a regular expression, the operation on sets is defined as + +\[ +A^* \dn \bigcup_{0\le n} A^n +\] + +We will use parentheses to disambiguate regular expressions. +Parentheses are not really part of a regular expression, and +indeed we do not need them in our code because there the tree +structure is always clear. But for writing them down in a more +mathematical fashion, parentheses will be helpful. For example +we will write $(r_1 + r_2)^*$, which is different from, say +$r_1 + (r_2)^*$. The former means roughly zero or more times +$r_1$ or $r_2$, while the latter means $r_1$ or zero or more +times $r_2$. This will turn out are two different pattern, +which match in general different strings. We should also write +$(r_1 + r_2) + r_3$, which is different from the regular +expression $r_1 + (r_2 + r_3)$, but in case of $+$ and $\cdot$ +we actually do not care about the order and just write $r_1 + +r_2 + r_3$, or $r_1 \cdot r_2 \cdot r_3$, respectively. The +reasons for this will become clear shortly. In the literature +you will often find that the choice $r_1 + r_2$ is written as +$r_1\mid{}r_2$ or $r_1\mid\mid{}r_2$. Also following the +convention in the literature, we will often omit the $\cdot$ +all together. This is to make some concrete regular +expressions more readable. For example the regular expression +for email addresses shown in \eqref{email} would look like + +\[ +\texttt{[...]+} \;\cdot\; \texttt{@} \;\cdot\; +\texttt{[...]+} \;\cdot\; \texttt{.} \;\cdot\; +\texttt{[...]\{2,6\}} +\] + +\noindent +which is much less readable than \eqref{email}. Similarly for +the regular expression that matches the string $hello$ we +should write + +\[ +{\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o} +\] + +\noindent +but often just write {\it hello}. + +If you prefer to think in terms of the implementation +of regular expressions in Scala, the constructors and +classes relate as follows + +\begin{center} +\begin{tabular}{rcl} +$\varnothing$ & $\mapsto$ & \texttt{NULL}\\ +$\epsilon$ & $\mapsto$ & \texttt{EMPTY}\\ +$c$ & $\mapsto$ & \texttt{CHAR(c)}\\ +$r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)}\\ +$r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)}\\ +$r^*$ & $\mapsto$ & \texttt{STAR(r)} +\end{tabular} +\end{center} + +A source of confusion might arise from the fact that we +use the term \emph{basic regular expression} for the regular +expressions used in ``theory'' and defined above, and +\emph{extended regular expression} for the ones used in +``practice'', for example Scala. If runtime is not of an +issue, then the latter can be seen as some syntactic sugar of +the former. Fo example we could replace + +\begin{center} +\begin{tabular}{rcl} +$r^+$ & $\mapsto$ & $r\cdot r^*$\\ +$r?$ & $\mapsto$ & $\epsilon + r$\\ +$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\ +$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\ +\end{tabular} +\end{center} + +\subsection*{The Meaning of Regular Expressions} + + +So far we have only considered informally what the +\emph{meaning} of a regular expression is. This is no good for +specifications of what algorithms are supposed to do or which +problems they are supposed to solve. + +To do so more formally we will associate with every regular +expression a language, or set of strings, that is supposed to +be matched by this regular expression. To understand what is +going on here it is crucial that you have also read the +handout about our basic mathematical notations. + +The meaning of a regular expression can be defined recursively +as follows + +\begin{center} +\begin{tabular}{rcl} +$L(\varnothing)$ & $\dn$ & $\varnothing$\\ +$L(\epsilon)$ & $\dn$ & $\{[]\}$\\ +$L(c)$ & $\dn$ & $\{"c"\}$\\ +$L(r_1+ r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$\\ +$L(r_1 \cdot r_2)$ & $\dn$ & $L(r_1) @ L(r_2)$\\ +$L(r^*)$ & $\dn$ & $(L(r))^*$\\ +\end{tabular} +\end{center} + +\noindent +As a result we can now precisely state what the meaning, for example, of the regular expression +${\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}$ is, namely +$L({\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}) = \{\text{\it"hello"}\}$...as expected. Similarly if we have the +choice-regular-expression $a + b$, its meaning is $L(a + b) = \{\text{\it"a"}, \text{\it"b"}\}$, namely the only two strings which can possibly +be matched by this choice. You can now also see why we do not make a difference +between the different regular expressions $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$....they +are not the same regular expression, but have the same meaning. + +The point of the definition of $L$ is that we can use it to precisely specify when a string $s$ is matched by a +regular expression $r$, namely only when $s \in L(r)$. In fact we will write a program {\it match} that takes any string $s$ and +any regular expression $r$ as argument and returns \emph{yes}, if $s \in L(r)$ and \emph{no}, +if $s \not\in L(r)$. We leave this for the next lecture. + +\begin{figure}[p] +\lstinputlisting{../progs/crawler1.scala} +\caption{The Scala code for a simple web-crawler that checks +for broken links in a web-page. It uses the regular expression +\texttt{http\_pattern} in Line~15 for recognising URL-addresses. +It finds all links using the library function +\texttt{findAllIn} in Line~21.\label{crawler1}} +\end{figure} + + +\begin{figure}[p] +\lstinputlisting{../progs/crawler2.scala} + +\caption{A version of the web-crawler that only follows links +in ``my'' domain---since these are the ones I am interested in +to fix. It uses the regular expression \texttt{my\_urls} in +Line~16 to check for my name in the links. The main change is +in Lines~26--29 where there is a test whether URL is in ``my'' +domain or not.\label{crawler2}} + +\end{figure} + +\begin{figure}[p] +\lstinputlisting{../progs/crawler3.scala} + +\caption{A small email harvester---whenever we download a +web-page, we also check whether it contains any email +addresses. For this we use the regular expression +\texttt{email\_pattern} in Line~16. The main change is in Line +32 where all email addresses that can be found in a page are +printed.\label{crawler3}} +\end{figure} + +\pagebreak +Lets start +with what we mean by \emph{strings}. Strings (they are also +sometimes referred to as \emph{words}) are lists of characters +drawn from an \emph{alphabet}. If nothing else is specified, +we usually assume the alphabet consists of just the lower-case +letters $a$, $b$, \ldots, $z$. Sometimes, however, we +explicitly restrict strings to contain, for example, only the +letters $a$ and $b$. In this case we say the alphabet is the +set $\{a, b\}$. There are many ways how we can write down strings. In programming languages, they are usually written as {\it "hello"} where the double quotes indicate that we dealing with a string. @@ -56,31 +453,7 @@ contains only the empty string $\{\text{""}\}$: the former has no elements, whereas the latter has one element. -As seen, there are languages which contain infinitely many strings, like the set of all strings. -The ``natural'' languages like English, French and so on contain many but only finitely many -strings (namely the ones listed in a good dictionary). It might be therefore be surprising that the -language consisting of all email addresses is infinite provided we assume it is defined by the -regular expression\footnote{See \url{http://goo.gl/5LoVX7}} -\[ -([\text{\it{}a-z0-9\_.-}]^+)@([\text{\it a-z0-9.-}]^+).([\text{\it a-z.}]^{\{2,6\}}) -\] - -\noindent -One reason is that before the $@$-sign there can be any string you want assuming it -is made up from letters, digits, underscores, dots and hyphens---clearly there are infinitely many -of those. Similarly the string after the $@$-sign can be any string. However, this does not mean -that every string is an email address. For example - -\[ -"\text{\it foo}@\text{\it bar}.\text{\it c}" -\] - -\noindent -is not, because the top-level-domains must be of length of at least two. (Note that there is -the convention that uppercase letters are treated in email-addresses as if they were -lower-case.) -\bigskip Before we expand on the topic of regular expressions, let us review some operations on sets. We will use capital letters $A$, $B$, $\ldots$ to stand for sets of strings. @@ -147,127 +520,9 @@ \end{center} \bigskip -\noindent -\emph{Regular expressions} are meant to conveniently describe languages...at least languages -we are interested in in Computer Science. For example there is no convenient regular expression -for describing the English language short of enumerating all English words. -But they seem useful for describing all permitted email addresses, as seen above. - -Regular expressions are given by the following grammar: - -\begin{center} -\begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l} - $r$ & $::=$ & $\varnothing$ & null\\ - & $\mid$ & $\epsilon$ & empty string / "" / []\\ - & $\mid$ & $c$ & single character\\ - & $\mid$ & $r_1 \cdot r_2$ & sequence\\ - & $\mid$ & $r_1 + r_2$ & alternative / choice\\ - & $\mid$ & $r^*$ & star (zero or more)\\ - \end{tabular} -\end{center} - -\noindent -Because we overload our notation, there are some subtleties you should be aware of. First, the letter -$c$ stands for any character from the -alphabet at hand. Second, we will use parentheses to disambiguate -regular expressions. For example we will write $(r_1 + r_2)^*$, which is different from, say $r_1 + (r_2)^*$. -The former means roughly zero or more times $r_1$ or $r_2$, while the latter means $r_1$ or zero or more times -$r_2$. We should also write $(r_1 + r_2) + r_3$, which is different from the regular expression $r_1 + (r_2 + r_3)$, -but in case of $+$ and $\cdot$ we actually do not care about the order and just write $r_1 + r_2 + r_3$, or $r_1 \cdot r_2 \cdot r_3$, -respectively. The reasons for this will become clear shortly. In the literature you will often find that the choice -$r_1 + r_2$ is written as $r_1\mid{}r_2$ or $r_1\mid\mid{}r_2$. Also following the convention in the literature, we will in case of $\cdot$ even -often omit it all together. For example the regular expression for email addresses shown above is meant to be of the form - -\[ -([\ldots])^+ \cdot @ \cdot ([\ldots])^+ \cdot . \cdot \ldots -\] - -\noindent -meaning first comes a name (specified by the regular expression $([\ldots])^+$), then an $@$-sign, then -a domain name (specified by the regular expression $([\ldots])^+$), then a dot and then a top-level domain. Similarly if -we want to specify the regular expression for the string {\it "hello"} we should write - -\[ -{\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o} -\] - -\noindent -but often just write {\it hello}. - -Another source of confusion might arise from the fact that we use the term \emph{regular expression} for the regular expressions used in ``theory'' -and also the ones used in ``practice''. In this course we refer by default to the regular expressions defined by the grammar above. -In ``practice'' we often use $r^+$ to stand for one or more times, $\backslash{}d$ to stand for a digit, $r^?$ to stand for an optional regular -expression, or ranges such as $[\text{\it a - z}]$ to stand for any lower case letter from $a$ to $z$. They are however mere convenience -as they can be seen as shorthand for -\begin{center} -\begin{tabular}{rcl} -$r^+$ & $\mapsto$ & $r\cdot r^*$\\ -$r^?$ & $\mapsto$ & $\epsilon + r$\\ -$\backslash d$ & $\mapsto$ & $0 + 1 + 2 + \ldots + 9$\\ -$[\text{\it a - z}]$ & $\mapsto$ & $a + b + \ldots + z$\\ -\end{tabular} -\end{center} - - -We will see later that the \emph{not}-regular-expression can also be seen as convenience. This regular -expression is supposed to stand for every string \emph{not} matched by a regular expression. We will write -such not-regular-expressions as $\sim{}r$. While being ``convenience'' it is often not so clear what the shorthand for -these kind of not-regular-expressions is. Try to write down the regular expression which can match any -string except the two strings {\it "hello"} and {\it "world"}. It is possible in principle, but often it is easier to just include -$\sim{}r$ in the definition of regular expressions. Whenever we do so, we will state it explicitly. - -So far we have only considered informally what the \emph{meaning} of a regular expression is. -To do so more formally we will associate with every regular expression a set of strings -that is supposed to be matched by this -regular expression. This can be defined recursively as follows - -\begin{center} -\begin{tabular}{rcl} -$L(\varnothing)$ & $\dn$ & $\{\,\}$\\ -$L(\epsilon)$ & $\dn$ & $\{""\}$\\ -$L(c)$ & $\dn$ & $\{"c"\}$\\ -$L(r_1+ r_2)$ & $\dn$ & $L(r_1) \cup L(r_2)$\\ -$L(r_1 \cdot r_2)$ & $\dn$ & $\{s_1@ s_2 | s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$\\ -$L(r^*)$ & $\dn$ & $\bigcup_{n \ge 0} L(r)^n$\\ -\end{tabular} -\end{center} +\subsection*{My Fascination for Regular Expressions} -\noindent -As a result we can now precisely state what the meaning, for example, of the regular expression -${\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}$ is, namely -$L({\it h} \cdot {\it e} \cdot {\it l} \cdot {\it l} \cdot {\it o}) = \{\text{\it"hello"}\}$...as expected. Similarly if we have the -choice-regular-expression $a + b$, its meaning is $L(a + b) = \{\text{\it"a"}, \text{\it"b"}\}$, namely the only two strings which can possibly -be matched by this choice. You can now also see why we do not make a difference -between the different regular expressions $(r_1 + r_2) + r_3$ and $r_1 + (r_2 + r_3)$....they -are not the same regular expression, but have the same meaning. - -The point of the definition of $L$ is that we can use it to precisely specify when a string $s$ is matched by a -regular expression $r$, namely only when $s \in L(r)$. In fact we will write a program {\it match} that takes any string $s$ and -any regular expression $r$ as argument and returns \emph{yes}, if $s \in L(r)$ and \emph{no}, -if $s \not\in L(r)$. We leave this for the next lecture. - -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler1.scala}}} -\caption{Scala code for a web-crawler that can detect broken links in a web-page. It uses -the regular expression {\tt http\_pattern} in Line~15 for recognising URL-addresses. It finds -all links using the library function {\tt findAllIn} in Line~21.} -\end{figure} - -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler2.scala}}} -\caption{A version of the web-crawler which only follows links in ``my'' domain---since these are the -ones I am interested in to fix. It uses the regular expression {\tt my\_urls} in Line~16. -The main change is in Line~26 where there is a test whether URL is in ``my'' domain or not.} - -\end{figure} - -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/crawler3.scala}}} -\caption{A small email harvester---whenever we download a web-page, we also check whether -it contains any email addresses. For this we use the regular expression {\tt email\_pattern} in -Line~17. The main change is in Lines 33 and 34 where all email addresses that can be found in a page are printed.} -\end{figure} \end{document} diff -r 10f02605a46a -r 35104ee14f87 handouts/notation.pdf Binary file handouts/notation.pdf has changed diff -r 10f02605a46a -r 35104ee14f87 handouts/notation.tex --- a/handouts/notation.tex Sun Sep 07 08:37:44 2014 +0100 +++ b/handouts/notation.tex Sat Sep 13 04:30:25 2014 +0100 @@ -232,7 +232,7 @@ \noindent Note the difference in the last two lines: the empty set behaves like $0$ for multiplication and the set $\{[]\}$ -like $1$ for multiplication. +like $1$ for multiplication ($n * 1 = n$ and $n * 0 = 0$). Following the language concatenation, we can define a \defn{language power} operation as follows: @@ -247,9 +247,10 @@ set, but the set containing the empty string. So no matter what the set $A$ is, $A^0$ will always be $\{[]\}$. (There is another hint about a connection between the $@$-operation and -multiplication: How is $x^n$ defined and what is $x^0$?) +multiplication: How is $x^n$ defined recursively and what is +$x^0$?) -Next we can define the \defn{star operation} for languages: +Next we can define the \defn{star operation} for languages: $A^*$ is the union of all powers of $A$, or short \begin{equation}\label{star} diff -r 10f02605a46a -r 35104ee14f87 handouts/scala-ho.pdf Binary file handouts/scala-ho.pdf has changed diff -r 10f02605a46a -r 35104ee14f87 handouts/scala-ho.tex --- a/handouts/scala-ho.tex Sun Sep 07 08:37:44 2014 +0100 +++ b/handouts/scala-ho.tex Sat Sep 13 04:30:25 2014 +0100 @@ -364,7 +364,7 @@ Coming from Java or C, you might be surprised that Scala does not really have loops. It has instead, what is in functional -programming called ,\emph{maps}. To illustrate how they work, +programming called, \emph{maps}. To illustrate how they work, lets assume you have a list of numbers from 1 to 8 and want to build the list of squares. The list of numbers from 1 to 8 can be constructed in Scala as follows: diff -r 10f02605a46a -r 35104ee14f87 langs.sty --- a/langs.sty Sun Sep 07 08:37:44 2014 +0100 +++ b/langs.sty Sat Sep 13 04:30:25 2014 +0100 @@ -61,4 +61,5 @@ \newcommand{\code}[1]{{\lstinline{#1}}} -\newcommand{\pcode}[1]{{\lstset{language={},keywordstyle=\color{black}}\lstinline{#1}}} +\newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}} +\makeatother diff -r 10f02605a46a -r 35104ee14f87 progs/crawler1.scala --- a/progs/crawler1.scala Sun Sep 07 08:37:44 2014 +0100 +++ b/progs/crawler1.scala Sat Sep 13 04:30:25 2014 +0100 @@ -1,5 +1,5 @@ -// A crawler which checks whether there -// are problems with links in web-pages +// A crawler which checks whether there are +// dead links in web-pages import io.Source import scala.util.matching.Regex @@ -12,7 +12,7 @@ } // regex for URLs -val http_pattern = """\"https?://[^\"]*\"""".r +val http_pattern = """"https?://[^"]*"""".r // drops the first and last character from a string def unquote(s: String) = s.drop(1).dropRight(1) @@ -21,7 +21,7 @@ http_pattern.findAllIn(page).map(unquote).toSet } -// naive version - seraches until a given depth +// naive version of crawl - searches until a given depth, // visits pages potentially more than once def crawl(url: String, n: Int) : Unit = { if (n == 0) () @@ -31,9 +31,9 @@ } } -// staring URL for the crawler -val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc/""" -//val startURL = """http://www.inf.kcl.ac.uk/staff/mml/""" +// some starting URLs for the crawler +val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc""" +//val startURL = """http://www.inf.kcl.ac.uk/staff/mcburney""" crawl(startURL, 2) diff -r 10f02605a46a -r 35104ee14f87 progs/crawler2.scala --- a/progs/crawler2.scala Sun Sep 07 08:37:44 2014 +0100 +++ b/progs/crawler2.scala Sat Sep 13 04:30:25 2014 +0100 @@ -12,7 +12,7 @@ } // regexes for URLs and "my" domain -val http_pattern = """\"https?://[^\"]*\"""".r +val http_pattern = """"https?://[^"]*"""".r val my_urls = """urbanc""".r def unquote(s: String) = s.drop(1).dropRight(1) @@ -33,8 +33,8 @@ } } -// staring URL for the crawler -val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc/""" +// starting URL for the crawler +val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc""" // can now deal with depth 3 and beyond crawl(startURL, 3) diff -r 10f02605a46a -r 35104ee14f87 progs/crawler3.scala --- a/progs/crawler3.scala Sun Sep 07 08:37:44 2014 +0100 +++ b/progs/crawler3.scala Sat Sep 13 04:30:25 2014 +0100 @@ -11,31 +11,30 @@ } // regexes for URLs, for "my" domain and for email addresses -val http_pattern = """\"https?://[^\"]*\"""".r +val http_pattern = """"https?://[^"]*"""".r val my_urls = """urbanc""".r val email_pattern = """([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})""".r -// The regular expression for emails comes from: -// http://net.tutsplus.com/tutorials/other/8-regular-expressions-you-should-know/ - def unquote(s: String) = s.drop(1).dropRight(1) def get_all_URLs(page: String) : Set[String] = { http_pattern.findAllIn(page).map(unquote).toSet } +def print_str(s: String) = + if (s == "") () else println(s) + def crawl(url: String, n: Int) : Unit = { if (n == 0) () - //else if (my_urls.findFirstIn(url) == None) () else { println(s"Visiting: $n $url") val page = get_page(url) - println(email_pattern.findAllIn(page).mkString("\n")) - for (u <- get_all_URLs(page)) crawl(u, n - 1) + print_str(email_pattern.findAllIn(page).mkString("\n")) + for (u <- get_all_URLs(page).par) crawl(u, n - 1) } } // staring URL for the crawler -val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc/""" +val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc""" crawl(startURL, 3)