equal
deleted
inserted
replaced
67 \begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}] |
67 \begin{lstlisting}[language={},numbers=none,keywordstyle=\color{black}] |
68 user@localserver |
68 user@localserver |
69 disposable.style.email.with+symbol@example.com |
69 disposable.style.email.with+symbol@example.com |
70 \end{lstlisting} |
70 \end{lstlisting} |
71 |
71 |
72 Identifiers, or variables, in program text are often required |
72 As mentioned above, identifiers, or variables, in program text are often required |
73 to satisfy the constraints that they start with a letter and |
73 to satisfy the constraints that they start with a letter and |
74 then can be followed by zero or more letters or numbers and |
74 then can be followed by zero or more letters or numbers and |
75 also can include underscores, but not as the first character. |
75 also can include underscores, but not as the first character. |
76 Such identifiers can be recognised with the regular expression |
76 Such identifiers can be recognised with the regular expression |
77 |
77 |
116 the regular expressions in the web-crawlers shown Figures |
116 the regular expressions in the web-crawlers shown Figures |
117 \ref{crawler1}, \ref{crawler2} and |
117 \ref{crawler1}, \ref{crawler2} and |
118 \ref{crawler3}.\footnote{There is an interesting twist in the |
118 \ref{crawler3}.\footnote{There is an interesting twist in the |
119 web-scraper where \pcode{re*?} is used instead of |
119 web-scraper where \pcode{re*?} is used instead of |
120 \pcode{re*}.} Note, however, the regular expression for |
120 \pcode{re*}.} Note, however, the regular expression for |
121 http-addresses in web-pages is meant to be |
121 http-addresses in web-pages in Figure~\ref{crawler1}, Line 15, is |
|
122 intended to be |
122 |
123 |
123 \[ |
124 \[ |
124 \pcode{"https?://[^"]*"} |
125 \pcode{"https?://[^"]*"} |
125 \] |
126 \] |
126 |
127 |
160 ymax=35, |
161 ymax=35, |
161 ytick={0,5,...,30}, |
162 ytick={0,5,...,30}, |
162 scaled ticks=false, |
163 scaled ticks=false, |
163 axis lines=left, |
164 axis lines=left, |
164 width=7cm, |
165 width=7cm, |
165 height=5cm, |
166 height=4.5cm, |
166 legend entries={Python,Ruby}, |
167 legend entries={Python,Ruby}, |
167 legend pos=north west, |
168 legend pos=north west, |
168 legend cell align=left] |
169 legend cell align=left] |
169 \addplot[blue,mark=*, mark options={fill=white}] |
170 \addplot[blue,mark=*, mark options={fill=white}] |
170 table {re-python.data}; |
171 table {re-python.data}; |
215 ymax=35, |
216 ymax=35, |
216 ytick={0,5,...,30}, |
217 ytick={0,5,...,30}, |
217 scaled ticks=false, |
218 scaled ticks=false, |
218 axis lines=left, |
219 axis lines=left, |
219 width=9cm, |
220 width=9cm, |
220 height=5cm] |
221 height=4.5cm] |
221 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
222 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
222 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
223 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
223 \end{axis} |
224 \end{axis} |
224 \end{tikzpicture} |
225 \end{tikzpicture} |
225 \end{center} |
226 \end{center} |
391 |
392 |
392 \noindent You can now also see why we do not make a difference |
393 \noindent You can now also see why we do not make a difference |
393 between the different regular expressions $(r_1 + r_2) + r_3$ |
394 between the different regular expressions $(r_1 + r_2) + r_3$ |
394 and $r_1 + (r_2 + r_3)$\ldots they are not the same regular |
395 and $r_1 + (r_2 + r_3)$\ldots they are not the same regular |
395 expression, but they have the same meaning. For example |
396 expression, but they have the same meaning. For example |
|
397 you can do the following calculation which shows they |
|
398 have the same meaning: |
396 |
399 |
397 \begin{eqnarray*} |
400 \begin{eqnarray*} |
398 L((r_1 + r_2) + r_3) & = & L(r_1 + r_2) \cup L(r_3)\\ |
401 L((r_1 + r_2) + r_3) & = & L(r_1 + r_2) \cup L(r_3)\\ |
399 & = & L(r_1) \cup L(r_2) \cup L(r_3)\\ |
402 & = & L(r_1) \cup L(r_2) \cup L(r_3)\\ |
400 & = & L(r_1) \cup L(r_2 + r_3)\\ |
403 & = & L(r_1) \cup L(r_2 + r_3)\\ |
515 The hope is that we can do better in the future---for example |
518 The hope is that we can do better in the future---for example |
516 by proving that the algorithms actually satisfy their |
519 by proving that the algorithms actually satisfy their |
517 specification and that the corresponding implementations do |
520 specification and that the corresponding implementations do |
518 not contain any bugs. We are close, but not yet quite there. |
521 not contain any bugs. We are close, but not yet quite there. |
519 |
522 |
520 Despite my fascination, I am also happy to admit that regular |
523 My fascination non withstanding, I am also happy to admit that regular |
521 expressions have their shortcomings. There are some well-known |
524 expressions have their shortcomings. There are some well-known |
522 ``theoretical'' shortcomings, for example recognising strings |
525 ``theoretical'' shortcomings, for example recognising strings |
523 of the form $a^{n}b^{n}$. I am not so bothered by them. What I |
526 of the form $a^{n}b^{n}$. I am not so bothered by them. What I |
524 am bothered about is when regular expressions are in the way |
527 am bothered about is when regular expressions are in the way |
525 of practical programming. For example, it turns out that the |
528 of practical programming. For example, it turns out that the |