|
876
|
1 |
% !TEX program = xelatex
|
|
1039
|
2 |
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
|
|
876
|
3 |
\usepackage{../slides}
|
|
|
4 |
\usepackage{../graphicss}
|
|
|
5 |
\usepackage{../langs}
|
|
|
6 |
\usepackage{../data}
|
|
|
7 |
\usetikzlibrary{cd}
|
|
|
8 |
|
|
|
9 |
|
|
|
10 |
\usepackage{tcolorbox}
|
|
|
11 |
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
|
|
|
12 |
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
|
|
|
13 |
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
|
|
|
14 |
|
|
|
15 |
|
|
1039
|
16 |
|
|
959
|
17 |
\setbeamersize{text margin left=2mm} % <- like this
|
|
|
18 |
\hfuzz=220pt
|
|
876
|
19 |
|
|
|
20 |
\lstset{language=Scala,
|
|
|
21 |
style=mystyle,
|
|
|
22 |
numbersep=0pt,
|
|
|
23 |
numbers=none,
|
|
|
24 |
xleftmargin=0mm}
|
|
|
25 |
|
|
959
|
26 |
\pgfplotsset{compat=1.17}
|
|
913
|
27 |
|
|
959
|
28 |
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
|
|
|
29 |
|
|
|
30 |
% beamer stuff
|
|
1039
|
31 |
\renewcommand{\slidecaption}{Christian Urban, King's College London}
|
|
876
|
32 |
|
|
|
33 |
|
|
|
34 |
|
|
913
|
35 |
\begin{document}
|
|
876
|
36 |
|
|
959
|
37 |
|
|
|
38 |
|
|
876
|
39 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
40 |
\begin{frame}[t]
|
|
959
|
41 |
\frametitle{%
|
|
876
|
42 |
\begin{tabular}{@ {}c@ {}}
|
|
913
|
43 |
\\[8mm]
|
|
1039
|
44 |
\LARGE POSIX Matching\\
|
|
|
45 |
\LARGE using Regular Expressions\\[5mm]
|
|
|
46 |
\normalsize\textcolor{gray}{Meshal Binnasban\;\; Christian Urban}
|
|
876
|
47 |
\end{tabular}}
|
|
|
48 |
|
|
|
49 |
\end{frame}
|
|
|
50 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
51 |
|
|
913
|
52 |
|
|
959
|
53 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
54 |
\begin{frame}[t]
|
|
|
55 |
\frametitle{Quiz 1}
|
|
|
56 |
\begin{bubble}[10cm]\it
|
|
|
57 |
There are many, many regular expression libraries.\bigskip\\
|
|
959
|
58 |
|
|
913
|
59 |
\textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
|
|
|
60 |
difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
|
|
|
61 |
\end{bubble}
|
|
|
62 |
|
|
|
63 |
\begin{textblock}{12}(2,9)
|
|
|
64 |
\begin{tikzpicture}
|
|
|
65 |
\draw(0,0) node[rotate=20]{linear};
|
|
|
66 |
\draw(3,0) node[rotate=-20]{\bl{$O(n \log n)$}};
|
|
|
67 |
\draw(3,-2) node[rotate=10]{quadratic};
|
|
|
68 |
\draw(6,0) node[rotate=20]{P};
|
|
|
69 |
\draw(7,0) node[rotate=-20]{NP};
|
|
|
70 |
\draw(7,-1) node[rotate=0]{\bl{$O(2^n)$}};
|
|
|
71 |
\end{tikzpicture}
|
|
|
72 |
\end{textblock}
|
|
|
73 |
|
|
|
74 |
\end{frame}
|
|
959
|
75 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
76 |
|
|
959
|
77 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
78 |
\begin{frame}[t]
|
|
|
79 |
\frametitle{Quiz 2}
|
|
|
80 |
|
|
|
81 |
\begin{textblock}{12}(2,2.5)
|
|
1039
|
82 |
A typical regular expression for (some) email addresses:
|
|
913
|
83 |
\begin{center}
|
|
|
84 |
($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\_\!\!\_\,.-]^+}}_{\textrm{name}}$)\bl{$\,@\,$}
|
|
|
85 |
($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\,-]^+}}_{\textrm{domain}}$) \bl{$\,.\,$}
|
|
1039
|
86 |
($\underbrace{\bl{[a\mbox{-}z\,.]^{\{2..6\}}}}_{\textrm{top-level domain}}$)
|
|
959
|
87 |
\end{center}
|
|
913
|
88 |
\end{textblock}
|
|
|
89 |
|
|
|
90 |
\only<2>{
|
|
|
91 |
\begin{textblock}{10}(4,8)
|
|
|
92 |
bounded regular expressions:\medskip\\
|
|
959
|
93 |
\begin{tabular}{ll}
|
|
913
|
94 |
\bl{$r^{\{n\}}$} & exactly n-times \bl{$r$}\\
|
|
|
95 |
\bl{$r^{\{n..m\}}$} & between n and m-times\\
|
|
|
96 |
\bl{$r^{\{n..\}}$} & from n-times\\
|
|
|
97 |
\bl{$r^{\{..m\}}$} & upto m-times\\
|
|
|
98 |
\end{tabular}\smallskip\\
|
|
|
99 |
\footnotesize\hfill ${}^*$ in some applications the counters can be in the millions
|
|
|
100 |
\end{textblock}}
|
|
959
|
101 |
|
|
913
|
102 |
\end{frame}
|
|
959
|
103 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
104 |
|
|
|
105 |
|
|
959
|
106 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
107 |
\begin{frame}[t]
|
|
|
108 |
\frametitle{Quiz 2}
|
|
|
109 |
|
|
|
110 |
|
|
|
111 |
\begin{textblock}{12}(2,2.5)
|
|
1039
|
112 |
\onslide<1->{Thompson construction for $r_1 \cdot r_2$: By recursion we are given two NFAs for $r_1$ and $r_2$.\medskip\\
|
|
913
|
113 |
\onslide<2->{For $r_1\cdot r_2$:}\bigskip}
|
|
|
114 |
\end{textblock}
|
|
|
115 |
|
|
|
116 |
\begin{textblock}{12}(2,6)
|
|
|
117 |
\onslide<1>{
|
|
|
118 |
\begin{tikzpicture}[node distance=3mm,
|
|
|
119 |
>=stealth',very thick,
|
|
|
120 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20}]
|
|
|
121 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
|
959
|
122 |
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
|
|
|
123 |
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
|
|
913
|
124 |
\node (R_1) [right=of Q_0] {$\ldots$};
|
|
|
125 |
\node[state, accepting] (T_1) [right=of R_1] {$\mbox{}$};
|
|
|
126 |
\node[state, accepting] (T_2) [above=of T_1] {$\mbox{}$};
|
|
|
127 |
\node[state, accepting] (T_3) [below=of T_1] {$\mbox{}$};
|
|
|
128 |
|
|
|
129 |
\node (A_0) [right=2.5cm of T_1] {$\mbox{}$};
|
|
|
130 |
\node[state, initial] (A_01) [above=1mm of A_0] {$\mbox{}$};
|
|
|
131 |
\node[state, initial] (A_02) [below=1mm of A_0] {$\mbox{}$};
|
|
|
132 |
|
|
|
133 |
\node (b_1) [right=of A_0] {$\ldots$};
|
|
|
134 |
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
|
|
|
135 |
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
|
|
|
136 |
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
|
|
|
137 |
\begin{pgfonlayer}{background}
|
|
|
138 |
\node (1) [rounded corners, inner sep=1mm, thick,
|
|
|
139 |
draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_3)] {};
|
|
|
140 |
\node (2) [rounded corners, inner sep=1mm, thick,
|
|
|
141 |
draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
|
|
|
142 |
\node [yshift=2mm] at (1.north) {$r_1$};
|
|
|
143 |
\node [yshift=2mm] at (2.north) {$r_2$};
|
|
|
144 |
\end{pgfonlayer}
|
|
|
145 |
\end{tikzpicture}}
|
|
|
146 |
\end{textblock}
|
|
|
147 |
|
|
|
148 |
\begin{textblock}{12}(2,6)
|
|
|
149 |
\onslide<2>{
|
|
|
150 |
\begin{tikzpicture}[node distance=3mm,
|
|
|
151 |
>=stealth',very thick,
|
|
|
152 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
|
|
|
153 |
\node[state, initial] (Q_0) {$\mbox{}$};
|
|
959
|
154 |
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
|
|
|
155 |
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
|
|
913
|
156 |
\node (r_1) [right=of Q_0] {$\ldots$};
|
|
|
157 |
\node[state] (t_1) [right=of r_1] {$\mbox{}$};
|
|
|
158 |
\node[state] (t_2) [above=of t_1] {$\mbox{}$};
|
|
|
159 |
\node[state] (t_3) [below=of t_1] {$\mbox{}$};
|
|
|
160 |
|
|
|
161 |
\node (A_0) [right=2.5cm of t_1] {$\mbox{}$};
|
|
|
162 |
\node[state] (A_01) [above=1mm of A_0] {$\mbox{}$};
|
|
|
163 |
\node[state] (A_02) [below=1mm of A_0] {$\mbox{}$};
|
|
|
164 |
|
|
|
165 |
\node (b_1) [right=of A_0] {$\ldots$};
|
|
|
166 |
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
|
|
|
167 |
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
|
|
|
168 |
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
|
|
|
169 |
\path[->] (t_1) edge (A_01);
|
|
|
170 |
\path[->] (t_2) edge node [above] {$\varepsilon$\footnotesize{}s} (A_01);
|
|
|
171 |
\path[->] (t_3) edge (A_01);
|
|
|
172 |
\path[->] (t_1) edge (A_02);
|
|
|
173 |
\path[->] (t_2) edge (A_02);
|
|
|
174 |
\path[->] (t_3) edge node [below] {$\varepsilon$\footnotesize{}s} (A_02);
|
|
959
|
175 |
|
|
913
|
176 |
\begin{pgfonlayer}{background}
|
|
|
177 |
\node (3) [rounded corners, inner sep=1mm, thick,
|
|
|
178 |
draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
|
|
|
179 |
\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
|
|
|
180 |
\end{pgfonlayer}
|
|
|
181 |
\end{tikzpicture}}
|
|
|
182 |
\end{textblock}
|
|
|
183 |
|
|
|
184 |
|
|
|
185 |
\end{frame}
|
|
959
|
186 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
187 |
|
|
959
|
188 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
189 |
\begin{frame}[t]
|
|
|
190 |
\frametitle{Quiz 2}
|
|
|
191 |
|
|
|
192 |
\begin{textblock}{12}(2,2.5)
|
|
1039
|
193 |
\onslide<1->{Thompson construction for $r^*$: By recursion we have a NFA for $r$.\medskip\\
|
|
913
|
194 |
\onslide<2->{For $r^*$:\bigskip}}
|
|
|
195 |
\end{textblock}
|
|
|
196 |
|
|
|
197 |
\begin{textblock}{12}(4,6)
|
|
959
|
198 |
\onslide<1>{
|
|
913
|
199 |
\begin{tikzpicture}[node distance=3mm,
|
|
|
200 |
>=stealth',very thick,
|
|
|
201 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
|
202 |
baseline=(current bounding box.north)]
|
|
|
203 |
\node (2) {$\mbox{}$};
|
|
|
204 |
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
|
|
959
|
205 |
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
|
|
913
|
206 |
\node (a) [right=of 2] {$\ldots$};
|
|
|
207 |
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
|
|
|
208 |
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
|
|
|
209 |
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
|
|
|
210 |
\begin{pgfonlayer}{background}
|
|
|
211 |
\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
|
|
|
212 |
\node [yshift=3mm] at (1.north) {$r$};
|
|
|
213 |
\end{pgfonlayer}
|
|
|
214 |
\end{tikzpicture}}
|
|
|
215 |
\end{textblock}
|
|
876
|
216 |
|
|
913
|
217 |
\begin{textblock}{12}(2,6)
|
|
959
|
218 |
\onslide<2->{
|
|
913
|
219 |
\begin{tikzpicture}[node distance=3mm,
|
|
|
220 |
>=stealth',very thick,
|
|
|
221 |
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
|
|
|
222 |
baseline=(current bounding box.north)]
|
|
|
223 |
\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
|
|
|
224 |
\node (2) [right=16mm of 1] {$\mbox{}$};
|
|
|
225 |
\node[state] (4) [above=1mm of 2] {$\mbox{}$};
|
|
959
|
226 |
\node[state] (5) [below=1mm of 2] {$\mbox{}$};
|
|
913
|
227 |
\node (a) [right=of 2] {$\ldots$};
|
|
|
228 |
\node[state] (a1) [right=of a] {$\mbox{}$};
|
|
|
229 |
\node[state] (a2) [above=of a1] {$\mbox{}$};
|
|
|
230 |
\node[state] (a3) [below=of a1] {$\mbox{}$};
|
|
|
231 |
\path[->] (1) edge node [below] {$\varepsilon$} (4);
|
|
|
232 |
\path[->] (1) edge node [below] {$\varepsilon$} (5);
|
|
|
233 |
\path[->] (a1) edge [bend left=45] node [below] {$\varepsilon$} (1);
|
|
|
234 |
\path[->] (a2) edge [bend right] node [below] {$\varepsilon$} (1);
|
|
|
235 |
\path[->] (a3) edge [bend left=45] node [below] {$\varepsilon$} (1);
|
|
|
236 |
\begin{pgfonlayer}{background}
|
|
|
237 |
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
|
|
|
238 |
\node [yshift=3mm] at (2.north) {$r^*$};
|
|
|
239 |
\end{pgfonlayer}
|
|
|
240 |
\end{tikzpicture}}
|
|
|
241 |
\end{textblock}
|
|
|
242 |
|
|
|
243 |
\begin{textblock}{12}(2,12)
|
|
959
|
244 |
\onslide<3->{
|
|
913
|
245 |
\begin{bubble}[9.5cm]\it
|
|
959
|
246 |
Quiz:\smallskip\\
|
|
1039
|
247 |
\textbf{What is the Thompson construction for \bl{$r^{\{n\}}$} ?}
|
|
913
|
248 |
\end{bubble}}
|
|
|
249 |
\end{textblock}
|
|
|
250 |
|
|
|
251 |
\end{frame}
|
|
|
252 |
|
|
959
|
253 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
254 |
|
|
959
|
255 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
256 |
\begin{frame}[t]
|
|
|
257 |
\frametitle{Quiz 3}
|
|
|
258 |
|
|
959
|
259 |
Hierarchy of Languages:
|
|
913
|
260 |
|
|
|
261 |
\begin{center}
|
|
|
262 |
\begin{tikzpicture}
|
|
959
|
263 |
[rect/.style={draw=black!50,
|
|
913
|
264 |
top color=white,
|
|
959
|
265 |
bottom color=black!20,
|
|
|
266 |
rectangle,
|
|
|
267 |
very thick,
|
|
913
|
268 |
rounded corners}, scale=1.2]
|
|
|
269 |
|
|
|
270 |
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
|
|
|
271 |
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
|
|
|
272 |
\draw (0,-0.85) node [rect, text depth=17mm] {\;\;context sensitive languages\;\;};
|
|
|
273 |
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
|
|
|
274 |
\draw (0,-1.4) node [rect] {regular languages};
|
|
|
275 |
\end{tikzpicture}
|
|
959
|
276 |
\end{center}
|
|
913
|
277 |
|
|
|
278 |
\begin{textblock}{12}(2,11.5)
|
|
959
|
279 |
\onslide<2->{
|
|
913
|
280 |
\begin{bubble}[9.5cm]\it
|
|
|
281 |
Quiz:\smallskip\\
|
|
959
|
282 |
|
|
913
|
283 |
\textbf{Can we use standard parsing algorithms for matching / lexing\,?}
|
|
1039
|
284 |
Say CYK, LL(1), LR(k), PEG, \ldots
|
|
913
|
285 |
\end{bubble}}
|
|
|
286 |
\end{textblock}
|
|
|
287 |
|
|
|
288 |
\end{frame}
|
|
959
|
289 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
290 |
|
|
|
291 |
\defverbatim{\foo}{\footnotesize%
|
|
|
292 |
\begin{verbatim}
|
|
|
293 |
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|
|
|
|
294 |
null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s
|
|
959
|
295 |
| -|~|!|{}|\|\||\+)*.*(?:.*=.*)))
|
|
913
|
296 |
\end{verbatim}
|
|
|
297 |
}
|
|
|
298 |
|
|
959
|
299 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
300 |
\begin{frame}[t,fragile]
|
|
|
301 |
\frametitle{Quiz 4}
|
|
|
302 |
|
|
|
303 |
\begin{textblock}{12}(2,2.5)
|
|
1039
|
304 |
\begin{bubble}[10.5cm]\it
|
|
959
|
305 |
Quiz:\smallskip\\
|
|
1039
|
306 |
\textbf{Do regular expressions have any security relevance\,?}
|
|
913
|
307 |
\end{bubble}
|
|
|
308 |
\end{textblock}
|
|
|
309 |
|
|
|
310 |
\only<2->{
|
|
|
311 |
\begin{textblock}{2}(1,6)
|
|
|
312 |
\includegraphics[scale=0.8]{../pics/zeek.png}
|
|
|
313 |
\includegraphics[scale=0.17]{../pics/snort.png}
|
|
|
314 |
\end{textblock}}
|
|
|
315 |
|
|
|
316 |
\only<3->{
|
|
|
317 |
\begin{textblock}{7}(7,5.6)
|
|
|
318 |
\includegraphics[scale=0.14]{../pics/cloudflare.png}\\
|
|
|
319 |
\footnotesize
|
|
|
320 |
It serves more web traffic than Twitter, Amazon, Apple,
|
|
|
321 |
Instagram, Bing \& Wikipedia combined.\medskip\\
|
|
|
322 |
Web Application Firewall filters out
|
|
|
323 |
SQL injection attacks, XSS attacks etc
|
|
|
324 |
\end{textblock}}
|
|
|
325 |
|
|
|
326 |
\only<3->{
|
|
|
327 |
\begin{textblock}{13}(4,12.3)
|
|
|
328 |
\footnotesize
|
|
|
329 |
\hspace{1.5cm}a global outage on 2 July 2019 (first one for six years)
|
|
|
330 |
\color{blue}\foo\color{black}
|
|
|
331 |
\end{textblock}
|
|
|
332 |
}
|
|
|
333 |
|
|
959
|
334 |
|
|
913
|
335 |
\end{frame}
|
|
|
336 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
337 |
|
|
959
|
338 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
339 |
\begin{frame}[t]
|
|
|
340 |
\frametitle{Quiz 3}
|
|
|
341 |
|
|
959
|
342 |
\begin{textblock}{12}(2,2)
|
|
913
|
343 |
\begin{bubble}[9.5cm]\it
|
|
|
344 |
Quiz:\smallskip\\
|
|
959
|
345 |
|
|
913
|
346 |
\textbf{Can we use standard parsing algorithms for matching / lexing\,?}
|
|
1039
|
347 |
Say CYK, LL(1), LR(k), PEG, \ldots
|
|
913
|
348 |
\end{bubble}
|
|
|
349 |
\end{textblock}
|
|
|
350 |
|
|
|
351 |
|
|
|
352 |
\begin{textblock}{12}(1,7)
|
|
|
353 |
\textbf{POSIX lexing}
|
|
|
354 |
|
|
|
355 |
\begin{tabular}{@ {}ll}
|
|
1039
|
356 |
Assume you have: & \bl{$r_{key} \dn \texttt{if} + \texttt{then} + \texttt{while} + \ldots$}\\
|
|
913
|
357 |
& \bl{$r_{id\;} \,\dn \texttt{[a-z]} \cdot \texttt{[a-z0-9\_]}^*$}\medskip\\
|
|
|
358 |
|
|
1039
|
359 |
Lex a string with & \bl{$(r_{key} + r_{id})^*$}\medskip\\
|
|
913
|
360 |
|
|
|
361 |
What should be & \\
|
|
|
362 |
the result for: & \bl{\texttt{"iffoo"}} \;\;\; \bl{\texttt{"if"}}\\
|
|
959
|
363 |
\end{tabular}
|
|
913
|
364 |
\end{textblock}
|
|
|
365 |
|
|
|
366 |
\only<2->{
|
|
959
|
367 |
\begin{textblock}{13.5}(1.5,4)
|
|
913
|
368 |
\begin{mybox3}{POSIX rules}
|
|
|
369 |
\begin{itemize}
|
|
|
370 |
\item \textbf{The Longest Match Rule:} The longest initial
|
|
|
371 |
substring matched by any regular expression is taken as next token.
|
|
|
372 |
\item \textbf{Priority Rule:} For a particular longest initial
|
|
|
373 |
substring, the first (leftmost) regular expression that can match
|
|
|
374 |
determines the token.
|
|
959
|
375 |
\item \ldots
|
|
913
|
376 |
\end{itemize}
|
|
|
377 |
\begin{center}
|
|
|
378 |
\bl{$(a + ab) \cdot (bc + c)$} \;\;and\;\; \bl{\texttt{"}$abc$\texttt{"}}
|
|
959
|
379 |
\end{center}
|
|
913
|
380 |
\end{mybox3}
|
|
876
|
381 |
\end{textblock}}
|
|
|
382 |
|
|
|
383 |
\end{frame}
|
|
|
384 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
385 |
|
|
959
|
386 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
387 |
\begin{frame}[t]
|
|
|
388 |
\frametitle{Quiz 1}
|
|
|
389 |
\begin{bubble}[10cm]\it
|
|
|
390 |
There are many, many regular expression libraries.\bigskip\\
|
|
959
|
391 |
|
|
913
|
392 |
\textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
|
|
|
393 |
difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
|
|
|
394 |
\end{bubble}
|
|
|
395 |
|
|
|
396 |
\begin{textblock}{12}(1,9)
|
|
1039
|
397 |
\begin{tabular}{p{4cm}|p{4cm}|p{5cm}}
|
|
|
398 |
atrociously slow (s't) & pretty lazy (s't) & \textcolor{gray}{Off the Beaten Track}\medskip\\
|
|
913
|
399 |
Python, Ruby, Swift, Dart, JavaScript & Rust, Go, RE2 & \textcolor{gray}{Snort, .Net7}\\
|
|
|
400 |
\end{tabular}
|
|
|
401 |
\end{textblock}
|
|
|
402 |
|
|
|
403 |
\end{frame}
|
|
959
|
404 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
405 |
|
|
959
|
406 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
407 |
\begin{frame}[t]
|
|
|
408 |
|
|
959
|
409 |
\mbox{}\\[10mm]
|
|
913
|
410 |
|
|
959
|
411 |
\begin{columns}[t,onlytextwidth]
|
|
1039
|
412 |
\begin{column}{.3\textwidth}
|
|
959
|
413 |
\raisebox{-10mm}{
|
|
1039
|
414 |
\hspace{3mm}\begin{tikzpicture}
|
|
913
|
415 |
\begin{axis}[
|
|
|
416 |
xlabel={\bl{$n$} \pcode{a}s},
|
|
|
417 |
%%x label style={at={(1.05,0.0)}},
|
|
|
418 |
ylabel={time in secs},
|
|
|
419 |
enlargelimits=false,
|
|
|
420 |
xtick={0,10,...,30},
|
|
|
421 |
xmax=35,
|
|
|
422 |
ymax=35,
|
|
|
423 |
ytick={0,5,...,30},
|
|
|
424 |
scaled ticks=false,
|
|
|
425 |
axis lines=left,
|
|
|
426 |
width=5cm,
|
|
959
|
427 |
height=5cm,
|
|
913
|
428 |
legend entries={Python,JavaScript,Swift,Dart},
|
|
|
429 |
legend style={font=\small,at={(0.5,-0.39)},anchor=north},
|
|
|
430 |
legend cell align=left]
|
|
|
431 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
|
|
|
432 |
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
|
|
|
433 |
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
|
|
|
434 |
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
|
|
|
435 |
\end{axis}
|
|
|
436 |
\end{tikzpicture}}
|
|
|
437 |
\end{column}
|
|
|
438 |
|
|
|
439 |
\begin{column}{.2\textwidth}
|
|
|
440 |
\begin{tikzpicture}
|
|
|
441 |
\begin{axis}[
|
|
|
442 |
xlabel={\bl{$n$} \pcode{a}s},
|
|
|
443 |
%ylabel={time in secs},
|
|
|
444 |
enlargelimits=false,
|
|
|
445 |
xtick={0,10,...,30},
|
|
|
446 |
xmax=35,
|
|
|
447 |
ymax=35,
|
|
|
448 |
ytick={0,5,...,30},
|
|
|
449 |
scaled ticks=false,
|
|
|
450 |
axis lines=left,
|
|
|
451 |
width=5cm,
|
|
959
|
452 |
height=5cm,
|
|
913
|
453 |
legend entries={Python,Ruby},
|
|
|
454 |
legend style={font=\small,at={(0.5,-0.39)},anchor=north},
|
|
|
455 |
legend cell align=left]
|
|
|
456 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
|
|
959
|
457 |
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
|
|
913
|
458 |
\end{axis}
|
|
959
|
459 |
\end{tikzpicture}
|
|
|
460 |
\end{column}
|
|
913
|
461 |
\end{columns}
|
|
|
462 |
|
|
|
463 |
\begin{textblock}{4}(9,1.7)
|
|
|
464 |
\textbf{\bl{\texttt{(a?)\boldmath$^{\{n\}}\cdot$(a)\boldmath$^{\{n\}}$}}}
|
|
|
465 |
\end{textblock}
|
|
|
466 |
|
|
959
|
467 |
\begin{textblock}{4}(4,1.7)
|
|
913
|
468 |
\textbf{\bl{\texttt{(a*)*$\cdot$b}}}
|
|
|
469 |
\end{textblock}
|
|
|
470 |
|
|
1039
|
471 |
\begin{textblock}{3.4}(6,11)
|
|
913
|
472 |
\small{}\textbf{matching with strings}
|
|
959
|
473 |
\textbf{\bl{$\underbrace{\texttt{a}...\texttt{a}}_n$}}
|
|
913
|
474 |
\end{textblock}
|
|
|
475 |
|
|
|
476 |
\end{frame}
|
|
|
477 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
478 |
|
|
959
|
479 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
480 |
\begin{frame}[t]
|
|
|
481 |
\frametitle{Quiz 1}
|
|
|
482 |
\begin{bubble}[10cm]\it
|
|
|
483 |
\textbf{Given a regular expression \bl{r} and a string \bl{s}, what is the
|
|
|
484 |
difficulty / complexity of the problem deciding whether \bl{r} matches \bl{s}?}
|
|
|
485 |
\end{bubble}
|
|
|
486 |
|
|
1039
|
487 |
\begin{textblock}{12}(1.7,8)
|
|
913
|
488 |
For \textbf{Perl-style} regular expression matchers (say Python, JavaScript, etc), the
|
|
|
489 |
answer is:
|
|
|
490 |
\only<2->{\begin{center}
|
|
|
491 |
\fontspec{Hoefler Text Black}\textcolor{ProcessBlue}{\huge{}NP}
|
|
959
|
492 |
\end{center}}
|
|
913
|
493 |
\end{textblock}
|
|
|
494 |
|
|
1039
|
495 |
\begin{textblock}{12}(1.7,13)
|
|
|
496 |
\only<3->{Groups and Backreferences: \bl{(\ldots)$\,\ldots{}\backslash{}n$}}
|
|
959
|
497 |
\end{textblock}
|
|
913
|
498 |
\end{frame}
|
|
959
|
499 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
500 |
|
|
|
501 |
|
|
|
502 |
|
|
959
|
503 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
504 |
\begin{frame}
|
|
|
505 |
\frametitle{Quiz 2}
|
|
|
506 |
|
|
|
507 |
\begin{textblock}{12}(2,2)
|
|
959
|
508 |
\onslide<1->{
|
|
913
|
509 |
\begin{bubble}[9.5cm]\it
|
|
959
|
510 |
Quiz:\smallskip\\
|
|
1039
|
511 |
\textbf{What is the Thompson construction for \bl{$r^{\{n\}}$} ?}
|
|
913
|
512 |
\end{bubble}}
|
|
|
513 |
\end{textblock}
|
|
|
514 |
|
|
|
515 |
\only<2->{
|
|
|
516 |
\begin{textblock}{12}(1,6)
|
|
|
517 |
\begin{tabular}{ll}
|
|
|
518 |
Google's RE2 lib & $\Rightarrow$ \bl{$a^{\{1001\}}$} is too big\\
|
|
|
519 |
\onslide<3->{Rust Regex lib} & \onslide<5->{$\Rightarrow$ \bl{$a^{\{1000\}\{100\}\{5\}}$} too big}\\
|
|
|
520 |
& \onslide<6->{$\Rightarrow$ \bl{$a^{\{0\}\{4294967295\}}$} ?}
|
|
|
521 |
\end{tabular}
|
|
|
522 |
\end{textblock}}
|
|
|
523 |
|
|
|
524 |
\only<4>{
|
|
959
|
525 |
\begin{textblock}{13.5}(1.5,4)
|
|
|
526 |
\begin{mybox3}{From Rust's Regex Description}\it
|
|
913
|
527 |
``\ldots [the] syntax is similar to Perl-style regular expressions, but lacks a few features like look
|
|
|
528 |
around and backreferences. In exchange, all searches execute in linear time with respect
|
|
|
529 |
to the size of the regular expression and search text. \ldots''
|
|
|
530 |
\end{mybox3}
|
|
|
531 |
\end{textblock}}
|
|
|
532 |
|
|
|
533 |
|
|
959
|
534 |
\end{frame}
|
|
876
|
535 |
|
|
|
536 |
|
|
|
537 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
538 |
\begin{frame}[t]
|
|
1039
|
539 |
\frametitle{\begin{tabular}{l}Regular Expressions \&\\[-2mm]
|
|
|
540 |
Brzozowski Derivatives\end{tabular}}
|
|
876
|
541 |
|
|
913
|
542 |
\begin{textblock}{6}(2,5)
|
|
|
543 |
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
|
|
|
544 |
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
|
|
|
545 |
& \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} \\
|
|
|
546 |
& \bl{$\mid$} & \bl{$c, d, \ldots$} & characters\\
|
|
|
547 |
& \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
|
|
|
548 |
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
|
|
|
549 |
& \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
|
|
|
550 |
\end{tabular}
|
|
|
551 |
\end{textblock}
|
|
959
|
552 |
|
|
876
|
553 |
\end{frame}
|
|
959
|
554 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
555 |
|
|
|
556 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
557 |
\begin{frame}[c]
|
|
913
|
558 |
\frametitle{\begin{tabular}{l}The Derivative of a Rexp\end{tabular}}
|
|
|
559 |
|
|
|
560 |
\large
|
|
959
|
561 |
If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular
|
|
913
|
562 |
expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
|
|
|
563 |
|
|
|
564 |
\small
|
|
|
565 |
\bl{$\der\,c\,r$} gives the answer, Brzozowski 1964\medskip\\
|
|
1039
|
566 |
(``lost in the sands of time'', re-appeared in 2009 in a paper by S.~Owens, J.~Reppy and A.~Turon)
|
|
876
|
567 |
\end{frame}
|
|
|
568 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
569 |
|
|
|
570 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
571 |
\begin{frame}[c]
|
|
913
|
572 |
\frametitle{\begin{tabular}{l}The Derivative of a Rexp\end{tabular}}
|
|
876
|
573 |
|
|
913
|
574 |
\begin{center}
|
|
|
575 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
|
|
|
576 |
\bl{$\der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
|
|
|
577 |
\bl{$\der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
|
|
|
578 |
\bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
|
|
|
579 |
\bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\
|
|
|
580 |
\bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
|
|
959
|
581 |
& & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\
|
|
913
|
582 |
& & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\
|
|
|
583 |
\bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\
|
|
|
584 |
\end{tabular}
|
|
|
585 |
\end{center}
|
|
876
|
586 |
|
|
|
587 |
\end{frame}
|
|
959
|
588 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
589 |
|
|
|
590 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
591 |
\begin{frame}[t]
|
|
|
592 |
\frametitle{\begin{tabular}{l}Brzozowski matcher\end{tabular}}
|
|
876
|
593 |
|
|
913
|
594 |
Does \bl{$r_1$} match \bl{"$abc$"}?
|
|
|
595 |
\begin{center}
|
|
|
596 |
\begin{tabular}{@{}rl@{}l@{}}
|
|
|
597 |
Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\
|
|
|
598 |
Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\
|
|
|
599 |
Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\
|
|
|
600 |
Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\
|
|
|
601 |
& test whether \bl{$r_4$} can recognise\\
|
|
|
602 |
& the empty string\medskip\\
|
|
|
603 |
Output: & result of the test\\
|
|
959
|
604 |
& $\Rightarrow \bl{\textit{true}} \,\text{or}\,
|
|
|
605 |
\bl{\textit{false}}$\\
|
|
913
|
606 |
\end{tabular}
|
|
|
607 |
\end{center}
|
|
876
|
608 |
|
|
913
|
609 |
|
|
|
610 |
\end{frame}
|
|
959
|
611 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
612 |
|
|
|
613 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
614 |
\begin{frame}[c]
|
|
|
615 |
\frametitle{\mbox{Nullable}}
|
|
|
616 |
|
|
876
|
617 |
|
|
913
|
618 |
\ldots{}whether a regular expression can match the empty string:
|
|
|
619 |
\begin{center}
|
|
|
620 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
|
|
621 |
\bl{$nullable(\ZERO)$} & \bl{$\dn$} & \bl{\textit{false}}\\
|
|
|
622 |
\bl{$nullable(\ONE)$} & \bl{$\dn$} & \bl{\textit{true}}\\
|
|
|
623 |
\bl{$nullable (c)$} & \bl{$\dn$} & \bl{\textit{false}}\\
|
|
959
|
624 |
\bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\
|
|
913
|
625 |
\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
|
|
|
626 |
\bl{$nullable (r^*)$} & \bl{$\dn$} & \bl{\textit{true}}\\
|
|
|
627 |
\end{tabular}
|
|
|
628 |
\end{center}
|
|
|
629 |
|
|
|
630 |
\end{frame}
|
|
959
|
631 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
632 |
|
|
1039
|
633 |
|
|
|
634 |
|
|
|
635 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
636 |
\begin{frame}[t]
|
|
|
637 |
\frametitle{\begin{tabular}{l}Correctness of Brozowski Der's\end{tabular}}
|
|
|
638 |
|
|
|
639 |
|
|
|
640 |
\begin{bubble}[7cm]\it
|
|
|
641 |
|
|
|
642 |
\begin{itemize}
|
|
|
643 |
\item \bl{$nullable(r)$} \;iff\; \bl{$[] \in L(r)$}
|
|
|
644 |
\item \bl{$L(\der\;c\;r)$} \;iff\; \bl{$Der\;c\;(L(r))$}
|
|
|
645 |
\end{itemize}
|
|
|
646 |
\end{bubble}
|
|
|
647 |
|
|
|
648 |
\begin{center}
|
|
|
649 |
\bl{$Der\,c\,A \,\dn\, \{s\;|\;c::s \in A\}$}
|
|
|
650 |
\end{center}
|
|
|
651 |
|
|
|
652 |
\begin{textblock}{10}(1,10)
|
|
|
653 |
\begin{itemize}
|
|
|
654 |
\item The beauty is that this only involves functional programs that can be conveniently reasoned about in theorem provers
|
|
|
655 |
\item Very nice first example for teaching theorem provers
|
|
|
656 |
%%\item POSIX lexing can be done via an extension by Sulzmann and Lu
|
|
|
657 |
\end{itemize}
|
|
|
658 |
\end{textblock}
|
|
|
659 |
|
|
|
660 |
\end{frame}
|
|
|
661 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
662 |
|
|
913
|
663 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
664 |
\begin{frame}[t]
|
|
|
665 |
\frametitle{\begin{tabular}{l}Extensions\end{tabular}}
|
|
876
|
666 |
|
|
913
|
667 |
\begin{center}
|
|
|
668 |
\begin{tabular}{@ {\hspace{-4mm}}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
|
|
|
669 |
\bl{$\der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;\ZERO\;else\; (der\,c\,r)\cdot r^{\{n-1\}}$} & \\
|
|
1039
|
670 |
\bl{$\der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;\ZERO\;else\; (der\,c\,r)\cdot r^{\{..n-1\}}$} & \\
|
|
913
|
671 |
\bl{$\der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & \bl{$if\;n=0\;then\;(der\,c\,r)\cdot r^*$} \\
|
|
1039
|
672 |
& & \bl{$else\; (der\,c\,r)\cdot r^{\{n-1..\}}$} & \\
|
|
913
|
673 |
\bl{$\der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & \bl{$if\;n=0 \wedge m=0\;then\;\ZERO\;else$} & \\
|
|
|
674 |
& & \bl{$if \;n=0 \wedge 0<m\; then\;(der\,c\,r)\cdot r^{\{..m-1\}}$} & \\
|
|
|
675 |
& & \bl{$else\; (der\,c\,r)\cdot r^{\{n-1..m-1\}}$} & \\
|
|
|
676 |
\bl{$\der\, c\, (\neg{}r)$} & \bl{$\dn$} & \bl{$\neg(der\,c\,r)$}\\
|
|
1039
|
677 |
\bl{$\der\, c\, (r_1 \,\&\, r_2)$} & \bl{$\dn$} & \bl{$\der\,c\,r_1 \;\&\;\der\;c\;r_2$}\\
|
|
913
|
678 |
\end{tabular}
|
|
|
679 |
\end{center}
|
|
|
680 |
|
|
|
681 |
also works for lookarounds, various anchors, etc, but \textbf{not} for backreferences
|
|
|
682 |
|
|
|
683 |
\begin{textblock}{3}(11,13)
|
|
959
|
684 |
\onslide<2>{
|
|
913
|
685 |
\begin{bubble}[3cm]
|
|
|
686 |
\bl{$a^{\{0\}\{4294967295\}}$}
|
|
|
687 |
\end{bubble}}
|
|
876
|
688 |
\end{textblock}
|
|
|
689 |
|
|
|
690 |
\end{frame}
|
|
959
|
691 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
692 |
|
|
1039
|
693 |
|
|
|
694 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
695 |
|
|
|
696 |
\begin{frame}{\begin{tabular}{l} Sulzmann and Lu's Addition (2014)\end{tabular}}
|
|
|
697 |
|
|
|
698 |
\begin{center}
|
|
|
699 |
($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\_\!\!\_\,.-]^+}}_{\textrm{name}}$)\bl{$\,@\,$}
|
|
|
700 |
($\underbrace{\bl{[a\mbox{-}z0\mbox{-}9\,-]^+}}_{\textrm{domain}}$) \bl{$\,.\,$}
|
|
|
701 |
($\underbrace{\bl{[a\mbox{-}z\,.]^{\{2..5\}}}}_{\textrm{top-level domain}}$)
|
|
|
702 |
\end{center}\bigskip
|
|
|
703 |
|
|
|
704 |
|
|
|
705 |
\begin{center}\small
|
|
|
706 |
\begin{tikzpicture}[node distance=1.1cm,every node/.style={minimum size=7mm}]
|
|
|
707 |
\node (r1) {\bl{$r_1$}};
|
|
|
708 |
\node (r2) [right=of r1] {\bl{$r_2$}};
|
|
|
709 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
|
|
|
710 |
\node (r3) [right=of r2] {\bl{$r_3$}};
|
|
|
711 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
|
|
|
712 |
\node (r4) [right=of r3] {\bl{$r_4$}};
|
|
|
713 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
|
|
|
714 |
\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
|
|
|
715 |
\node (v4) [below=of r4] {\bl{$v_4$}};
|
|
|
716 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (r4) -- (v4);
|
|
|
717 |
\node (v3) [left=of v4] {\bl{$v_3$}};
|
|
|
718 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
|
|
|
719 |
\node (v2) [left=of v3] {\bl{$v_2$}};
|
|
|
720 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]},line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
|
|
|
721 |
\node (v1) [left=of v2] {\bl{$v_1$}};
|
|
|
722 |
\draw[->,-{Computer Modern Rightarrow[length=3mm, width=4mm]}, line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
|
|
|
723 |
%\draw[->,line width=0.5mm] (r3) -- (v3);
|
|
|
724 |
%\draw[->,line width=0.5mm] (r2) -- (v2);
|
|
|
725 |
%\draw[->,line width=0.5mm] (r1) -- (v1);
|
|
|
726 |
\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
|
|
|
727 |
\end{tikzpicture}
|
|
|
728 |
\end{center}
|
|
|
729 |
|
|
|
730 |
\end{frame}
|
|
|
731 |
|
|
|
732 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
733 |
\begin{frame}[c]
|
|
|
734 |
\frametitle{Regexes and Values}
|
|
|
735 |
|
|
|
736 |
\mbox{Regular expressions and their corresponding values (``lexing trees''):}
|
|
|
737 |
|
|
|
738 |
\begin{center}
|
|
|
739 |
\begin{columns}
|
|
|
740 |
\begin{column}{3cm}
|
|
|
741 |
\begin{tabular}{@{}rrl@{}}
|
|
|
742 |
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
|
|
|
743 |
& \bl{$\mid$} & \bl{$\ONE$} \\
|
|
|
744 |
& \bl{$\mid$} & \bl{$c$} \\
|
|
|
745 |
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
|
|
|
746 |
& \bl{$\mid$} & \bl{$r_1 + r_2$} \\
|
|
|
747 |
\\
|
|
|
748 |
& \bl{$\mid$} & \bl{$r^*$} \\
|
|
|
749 |
\\
|
|
|
750 |
\end{tabular}
|
|
|
751 |
\end{column}
|
|
|
752 |
\begin{column}{3cm}
|
|
|
753 |
\begin{tabular}{@{\hspace{-7mm}}rrl@{}}
|
|
|
754 |
\bl{$v$} & \bl{$::=$} & \\
|
|
|
755 |
& & \bl{$Empty$} \\
|
|
|
756 |
& \bl{$\mid$} & \bl{$Char(c)$} \\
|
|
|
757 |
& \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
|
|
|
758 |
& \bl{$\mid$} & \bl{$Left(v)$} \\
|
|
|
759 |
& \bl{$\mid$} & \bl{$Right(v)$} \\
|
|
|
760 |
& \bl{$\mid$} & \bl{$Stars\,[]$} \\
|
|
|
761 |
& \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\
|
|
|
762 |
\end{tabular}
|
|
|
763 |
\end{column}
|
|
|
764 |
\end{columns}
|
|
|
765 |
\end{center}
|
|
|
766 |
|
|
|
767 |
\end{frame}
|
|
|
768 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
769 |
|
|
|
770 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
771 |
\begin{frame}[c]
|
|
|
772 |
\frametitle{POSIX Values / Injection}
|
|
|
773 |
|
|
|
774 |
\begin{textblock}{12}(1,5)
|
|
|
775 |
\begin{itemize}
|
|
|
776 |
\item Sulzmann and Lu's second phase calculates POSIX values:
|
|
|
777 |
|
|
|
778 |
\begin{center}
|
|
|
779 |
\begin{tabular}{l}
|
|
|
780 |
\\
|
|
|
781 |
\bl{$(a + ab) \cdot (bc + c)$} and \bl{$abc$}\\[3mm]
|
|
|
782 |
\bl{$\Rightarrow \;Seq(Right(..ab..), Right(..c..))$}\\
|
|
|
783 |
\mbox{}\\
|
|
|
784 |
\end{tabular}
|
|
|
785 |
\end{center}
|
|
|
786 |
|
|
|
787 |
\item All is still just simple recursive functions and ``algebraic''
|
|
|
788 |
reasoning (easy in theorem provers because people make mistakes)
|
|
|
789 |
\end{itemize}
|
|
|
790 |
\end{textblock}
|
|
|
791 |
|
|
|
792 |
|
|
|
793 |
\end{frame}
|
|
|
794 |
|
|
|
795 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
796 |
|
|
|
797 |
\begin{frame}[c]{\begin{tabular}{c}\mbox{}\\[15mm]\fontsize{96}{104}\textcolor{red}{\selectfont BUT\ldots}\end{tabular}}
|
|
|
798 |
|
|
|
799 |
\end{frame}
|
|
|
800 |
|
|
|
801 |
|
|
876
|
802 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
913
|
803 |
\begin{frame}[t]
|
|
1039
|
804 |
\frametitle{\mbox{Problems with ders}}
|
|
876
|
805 |
|
|
913
|
806 |
\textcolor{blue}{
|
|
876
|
807 |
\small
|
|
913
|
808 |
\def\ll{\stackrel{der\,a}{\longrightarrow}}
|
|
876
|
809 |
\begin{center}
|
|
1039
|
810 |
\begin{tabular}{@{\hspace{0mm}}rll}
|
|
913
|
811 |
$(a + aa)^*$ & $\ll$ & $(\ONE + \ONE{}a) \cdot (a + aa)^*$\\
|
|
|
812 |
& $\ll$ & $(\ZERO + \ZERO{}a + \ONE) \cdot (a + aa)^* \;+\; (\ONE + \ONE{}a) \cdot (a + aa)^*$\\
|
|
|
813 |
& $\ll$ & $(\ZERO + \ZERO{}a + \ZERO) \cdot (a + aa)^* + (\ONE + \ONE{}a) \cdot (a + aa)^* \;+\; $\\
|
|
|
814 |
& & $\qquad(\ZERO + \ZERO{}a + \ONE) \cdot (a + aa)^* + (\ONE + \ONE{}a) \cdot (a + aa)^*$\\
|
|
|
815 |
& $\ll$ & \ldots\\ \hspace{15mm}
|
|
876
|
816 |
\end{tabular}
|
|
913
|
817 |
\end{center}}
|
|
|
818 |
|
|
959
|
819 |
\begin{textblock}{13.5}(1.5,12)
|
|
913
|
820 |
(regular expressions of sizes 98, 169, 283, 468, 767, \ldots)
|
|
|
821 |
\end{textblock}
|
|
876
|
822 |
|
|
|
823 |
\end{frame}
|
|
959
|
824 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
825 |
|
|
|
826 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
827 |
\begin{frame}[c]
|
|
1039
|
828 |
\frametitle{Possible Simplifications}
|
|
|
829 |
|
|
|
830 |
\def\arraystretch{1.05}
|
|
|
831 |
\begin{center}
|
|
|
832 |
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l}
|
|
|
833 |
\bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\
|
|
|
834 |
\bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\
|
|
|
835 |
\bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \\
|
|
|
836 |
\bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \\
|
|
|
837 |
\bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$} & \\
|
|
|
838 |
\bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$} & \\
|
|
|
839 |
\bl{$r + r$} & $\mapsto$ & \bl{$r$} &
|
|
|
840 |
\end{tabular}
|
|
|
841 |
\end{center}\medskip
|
|
|
842 |
|
|
|
843 |
\small
|
|
|
844 |
\hspace{5mm}\mbox{this gets you off the ground, but there are still catastrophic cases}\\
|
|
|
845 |
\end{frame}
|
|
|
846 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
847 |
|
|
|
848 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
849 |
\begin{frame}[t]
|
|
|
850 |
\frametitle{\,Antimirov's Partial Derivatives}
|
|
|
851 |
|
|
|
852 |
\begin{center}
|
|
|
853 |
\bl{$pder\;s\;r \;\dn\; \{\only<1>{r_1, r_2, \ldots, r_n}\only<2->{\underbrace{r_1, r_2, \ldots, r_n}_{}}\}$}
|
|
|
854 |
\end{center}
|
|
|
855 |
|
|
|
856 |
\only<2->{
|
|
|
857 |
\begin{textblock}{6}(5,5)
|
|
|
858 |
\begin{bubble}[7cm]\it
|
|
|
859 |
Antimirov impressively showed that there can only be
|
|
|
860 |
a maximum of \bl{$n$}-terms where \bl{$n$}
|
|
|
861 |
is the number of character occurrences in \bl{$r$}.
|
|
|
862 |
\end{bubble}
|
|
|
863 |
\end{textblock}}
|
|
|
864 |
|
|
|
865 |
\only<3>{
|
|
|
866 |
\begin{textblock}{11}(1,11)
|
|
|
867 |
\begin{itemize}
|
|
|
868 |
\item pie in the sky / un rêve éveillé:\smallskip\\
|
|
|
869 |
\begin{quotation}
|
|
|
870 |
\noindent{}Brzozowski derivatives plus some clever-to-be-worked-out simplification grow regular expressions
|
|
|
871 |
at maximum \underline{cubically}
|
|
|
872 |
\end{quotation}
|
|
|
873 |
\end{itemize}
|
|
|
874 |
\end{textblock}}
|
|
|
875 |
|
|
|
876 |
\end{frame}
|
|
|
877 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
878 |
|
|
|
879 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
880 |
|
|
|
881 |
\begin{frame}{Two White Knights ??}
|
|
|
882 |
|
|
|
883 |
\only<2->{%
|
|
|
884 |
\begin{textblock}{12}(1,3)
|
|
|
885 |
\begin{itemize}
|
|
|
886 |
\item A Play on Regular Expressions (functional pearl at ICFP 2010) by S.~Fischer, F.~Huch and T.~Wilke
|
|
|
887 |
\item Regular Expressions, Au Point (technical report in arXiv 2010) by A.~Asperti, C.~Sacerdoti
|
|
|
888 |
Coen and E.~Tassi
|
|
|
889 |
\end{itemize}
|
|
|
890 |
\end{textblock}}
|
|
|
891 |
|
|
|
892 |
\only<3-6>{%
|
|
|
893 |
\begin{textblock}{12}(1,8)
|
|
|
894 |
\begin{center}
|
|
|
895 |
shift:\;\; \bl{$a\cdot (b\cdot c)$} \;\;and\;\;
|
|
|
896 |
\only<3>{``$\textcolor{gray}{abc}$''}%
|
|
|
897 |
\only<4>{``$\textcolor{red}{a}\textcolor{gray}{bc}$''}%
|
|
|
898 |
\only<5>{``$\textcolor{red}{ab}\textcolor{gray}{c}$''}%
|
|
|
899 |
\only<6>{``$\textcolor{red}{abc}$''}\\[3mm]
|
|
|
900 |
|
|
|
901 |
\begin{tikzpicture}[nodes={circle,draw}, level distance=1cm, ultra thick]
|
|
|
902 |
\node {$\cdot$}
|
|
|
903 |
child { node{\makebox[0.8em]{\bl{$\alt<4>{\textcolor{black}{\bullet}a}{\phantom{\bullet}a}$}}}}
|
|
|
904 |
child { node{$\cdot$}
|
|
|
905 |
child { node{\makebox[0.8em]{\bl{$\alt<5>{\textcolor{black}{\bullet}b}{\phantom{\bullet}b}$}}}}
|
|
|
906 |
child { node{\makebox[0.8em]{\bl{$\alt<6>{\textcolor{black}{\bullet}c}{\phantom{\bullet}c}$}}}}
|
|
|
907 |
};
|
|
|
908 |
\end{tikzpicture}
|
|
|
909 |
\end{center}
|
|
|
910 |
\end{textblock}}
|
|
|
911 |
|
|
|
912 |
\only<7->{%
|
|
|
913 |
\begin{textblock}{12}(1,8)
|
|
|
914 |
\begin{center}
|
|
|
915 |
shift:\;\; \bl{$ac + ab$} \;\;and\;\;
|
|
|
916 |
\only<7>{``$\textcolor{gray}{ab}$''}%
|
|
|
917 |
\only<8>{``$\textcolor{red}{a}\textcolor{gray}{b}$''}%
|
|
|
918 |
\only<9>{``$\textcolor{red}{ab}$''}\\[3mm]
|
|
|
919 |
|
|
|
920 |
\begin{tikzpicture}[nodes={circle,draw}, level distance=1.5cm, ultra thick]
|
|
|
921 |
\node {$+$}
|
|
|
922 |
child { node{\makebox[0.8em]{\bl{$\alt<8>{\textcolor{black}{\bullet}ac}{a\phantom{\bullet}c}$}}}}
|
|
|
923 |
child { node{\only<7>{\makebox[0.8em]{\bl{$\phantom{\bullet}ab$}}}%
|
|
|
924 |
\only<8>{\makebox[0.8em]{\bl{$\textcolor{black}{\bullet}ab$}}}%
|
|
|
925 |
\only<9>{\makebox[0.8em]{\bl{$a\textcolor{black}{\bullet}b$}}}}%
|
|
|
926 |
};
|
|
|
927 |
\end{tikzpicture}
|
|
|
928 |
\end{center}
|
|
|
929 |
\end{textblock}}
|
|
|
930 |
|
|
|
931 |
|
|
|
932 |
\end{frame}
|
|
|
933 |
|
|
|
934 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
935 |
|
|
|
936 |
\begin{frame}{Marked Regular Expressions}
|
|
|
937 |
|
|
|
938 |
\begin{textblock}{12}(1,3)
|
|
|
939 |
\begin{itemize}
|
|
|
940 |
\item \ldots{}work great for the basic regexes
|
|
|
941 |
\item problems already with \bl{$\&$}
|
|
|
942 |
\item no solution yet how to do \bl{$r^{\{n\}}$} efficiently
|
|
|
943 |
\item not to mention generating POSIX values
|
|
|
944 |
\end{itemize}
|
|
|
945 |
\end{textblock}
|
|
|
946 |
|
|
|
947 |
\begin{textblock}{12}(1,8)
|
|
|
948 |
\begin{center}
|
|
|
949 |
|
|
|
950 |
\begin{tikzpicture}[nodes={circle,draw}, level distance=1.2cm, ultra thick]
|
|
|
951 |
\node {$+$}
|
|
|
952 |
child { node{{\makebox[0.8em]{\bl{$\textcolor{black}{\bullet}a$}}}}}
|
|
|
953 |
child { node{$\cdot$}
|
|
|
954 |
child { node{\bl{$\ONE$}}}
|
|
|
955 |
child { node{\makebox[0.8em]{\bl{$\textcolor{black}{\bullet}a$}}}}
|
|
|
956 |
};
|
|
|
957 |
\end{tikzpicture}
|
|
|
958 |
\end{center}
|
|
|
959 |
\end{textblock}
|
|
|
960 |
\end{frame}
|
|
|
961 |
|
|
|
962 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
963 |
|
|
|
964 |
\begin{frame}{More Interesting Marks}
|
|
|
965 |
|
|
|
966 |
\begin{textblock}{12}(1,3)
|
|
|
967 |
\begin{itemize}
|
|
|
968 |
\item Our version of the marked algorithm:
|
|
|
969 |
\item[] Marks are of the form $\bullet_s$ where $s$ is a string
|
|
|
970 |
\end{itemize}\bigskip
|
|
|
971 |
|
|
|
972 |
|
|
|
973 |
\begin{center}
|
|
|
974 |
\begin{tabular}{ll@{\hspace{10mm}}l}
|
|
|
975 |
1) & $\left|_{\{\bullet_{abc}\}} \bl{(a + ab) \cdot (c + bc)}\right.$ & (start)\medskip\\
|
|
|
976 |
2) & $\bl{(a + ab)}\left|_{\{\bullet_{bc}, \bullet_{c}\}} \bl{\;\cdot\; (c + bc)}\right.$ & (after first sequence)\medskip\\
|
|
|
977 |
3) & $\bl{(a + ab) \cdot (c + bc)} \left|_{\{\bullet_{[]}, \bullet_{[]}\}}\right.$ & (end)\\
|
|
|
978 |
\end{tabular}
|
|
|
979 |
\end{center}
|
|
|
980 |
\end{textblock}
|
|
|
981 |
\end{frame}
|
|
|
982 |
|
|
|
983 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
984 |
\newcommand{\shifts}{\textit{shifts}}
|
|
|
985 |
|
|
|
986 |
\begin{frame}{Shifting Sets of Marks}
|
|
|
987 |
|
|
|
988 |
\begin{textblock}{12}(1,1)
|
|
|
989 |
\begin{center}
|
|
|
990 |
\bl{\begin{tabular}{@{}lcl@{}}
|
|
|
991 |
$\shifts\;ms\;\ZERO$ & $\dn$ & $\{\}$\\
|
|
|
992 |
$\shifts\;ms\;\ONE$ & $\dn$ & $\{\}$\\
|
|
|
993 |
$\shifts\;ms\;c$ & $\dn$ & $\{\bullet_s \mid\bullet_{c::s}\in ms\}$\\
|
|
|
994 |
$\shifts\;ms\;(r_1+r_2)$ & $\dn$ & $\shifts\;ms\;r_1 \;\cup\; \shifts\;ms\;r_2$\\
|
|
|
995 |
$\shifts\;ms\;(r_1\cdot r_2)$ & $\dn$ & let $ms' = \shifts\;ms\;r_1$ in\\
|
|
|
996 |
& &
|
|
|
997 |
$\;\;\begin{cases}
|
|
|
998 |
(\shifts\;(ms' \;\cup\; ms)\;r_2) \;\cup\; ms' & \textit{if}\;r_1 \wedge r_2 \;\textit{null}\\
|
|
|
999 |
(\shifts\;(ms' \;\cup\; ms)\;r_2) & \textit{if}\;r_1\;\textit{null}\\
|
|
|
1000 |
(\shifts\;ms'\;r_2) \;\cup\; ms' & \textit{if}\;r_2\;\textit{null}\\
|
|
|
1001 |
(\shifts\;ms'\;r_2) & \textit{o'wise} \\
|
|
|
1002 |
\end{cases}$\\
|
|
|
1003 |
$\shifts\;ms\;(r^*)$ & $\dn$ & let $ms' = \shifts\;ms\;r$ in\\
|
|
|
1004 |
& & $\;\;\text{if}\; ms' = \{\} \;\text{then}\; \{\} \;\text{else}\;\; \shifts\;ms'\;(r^*) \;\cup\;ms'$\\
|
|
|
1005 |
\end{tabular}}
|
|
|
1006 |
\end{center}
|
|
|
1007 |
\end{textblock}
|
|
|
1008 |
|
|
|
1009 |
\end{frame}
|
|
|
1010 |
|
|
|
1011 |
|
|
|
1012 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
1013 |
\begin{frame}{Matcher}
|
|
|
1014 |
|
|
|
1015 |
\[\bl{\begin{array}{lcl}
|
|
|
1016 |
\textit{matcher}\;s\;r & \dn & \textit{if}\;s = []\\
|
|
|
1017 |
& &\textit{then}\;\textit{nullable}(r)\\
|
|
|
1018 |
& &\textit{else}\;\bullet_{[]} \in \shifts\;\{\bullet_s\}\; r
|
|
|
1019 |
\end{array}}
|
|
|
1020 |
\]
|
|
|
1021 |
|
|
|
1022 |
|
|
|
1023 |
\begin{textblock}{12}(1,10)
|
|
|
1024 |
\begin{itemize}
|
|
|
1025 |
\item can be made to work for \bl{$r_1 \,\&\, r_2$} and \bl{$r^{\{n\}}$} etc
|
|
|
1026 |
|
|
|
1027 |
\item no idea if this is already known
|
|
|
1028 |
\item Meshal has now a good idea how to extract POSIX values
|
|
|
1029 |
\end{itemize}
|
|
|
1030 |
\end{textblock}
|
|
|
1031 |
|
|
|
1032 |
\end{frame}
|
|
|
1033 |
|
|
|
1034 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
1035 |
\begin{frame}[c]
|
|
913
|
1036 |
\frametitle{\mbox{Conclusion}}
|
|
876
|
1037 |
|
|
1039
|
1038 |
\begin{textblock}{12}(1,3)
|
|
876
|
1039 |
\begin{itemize}
|
|
1039
|
1040 |
\item The beauty of all this is that this only involves functional
|
|
|
1041 |
programs that can be conveniently reasoned about in theorem provers
|
|
|
1042 |
(opinions differ, but this is \textbf{not} the case with automata)
|
|
|
1043 |
\item POSIX lexing can be done via an extension by Sulzmann and Lu or using our \shifts{}\bigskip
|
|
|
1044 |
\item How surprising that one can still do new work on regular expressions
|
|
959
|
1045 |
\end{itemize}
|
|
1039
|
1046 |
\end{textblock}
|
|
|
1047 |
|
|
876
|
1048 |
|
|
|
1049 |
\end{frame}
|
|
959
|
1050 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
1051 |
|
|
1039
|
1052 |
\begin{frame}[c]{\begin{tabular}{c}\mbox{}\\[15mm]\fontsize{48}{52}\textcolor{red}{\selectfont Questions}\end{tabular}}
|
|
|
1053 |
|
|
|
1054 |
\end{frame}
|
|
|
1055 |
|
|
|
1056 |
|
|
959
|
1057 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
1058 |
|
|
913
|
1059 |
\begin{frame}<1-10>
|
|
959
|
1060 |
\end{frame}
|
|
876
|
1061 |
|
|
|
1062 |
|
|
|
1063 |
|
|
959
|
1064 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
876
|
1065 |
\end{document}
|
|
|
1066 |
|
|
1039
|
1067 |
|
|
|
1068 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
1069 |
\begin{frame}[t]
|
|
|
1070 |
\frametitle{\begin{tabular}{@ {\hspace{8mm}}c@ {}}Fast Regular Expression Matching\end{tabular}}
|
|
|
1071 |
\mbox{}\\[1mm]
|
|
|
1072 |
|
|
|
1073 |
\begin{columns}[t,onlytextwidth]
|
|
|
1074 |
\begin{column}{.2\textwidth}
|
|
|
1075 |
\raisebox{-10mm}{
|
|
|
1076 |
\begin{tikzpicture}
|
|
|
1077 |
\begin{axis}[
|
|
|
1078 |
xlabel={size of strings},
|
|
|
1079 |
x label style={at={(0.45,-0.16)}},
|
|
|
1080 |
ylabel={time in secs},
|
|
|
1081 |
enlargelimits=false,
|
|
|
1082 |
xtick={0,10,...,30},
|
|
|
1083 |
xmax=35,
|
|
|
1084 |
ymax=35,
|
|
|
1085 |
ytick={0,10,...,30},
|
|
|
1086 |
scaled ticks=false,
|
|
|
1087 |
axis lines=left,
|
|
|
1088 |
width=5cm,
|
|
|
1089 |
height=4.5cm,
|
|
|
1090 |
legend entries={Python,JavaScript,Swift,Dart},
|
|
|
1091 |
legend style={font=\footnotesize,at={(0.45,-0.48)},anchor=north},
|
|
|
1092 |
legend cell align=left]
|
|
|
1093 |
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
|
|
|
1094 |
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
|
|
|
1095 |
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
|
|
|
1096 |
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
|
|
|
1097 |
\end{axis}
|
|
|
1098 |
\end{tikzpicture}}
|
|
|
1099 |
\end{column}
|
|
|
1100 |
|
|
|
1101 |
\end{columns}
|
|
|
1102 |
|
|
|
1103 |
\begin{textblock}{4}(3.5,3.2)
|
|
|
1104 |
{\bl{\texttt{(a*)*$\cdot$b}}}
|
|
|
1105 |
\end{textblock}
|
|
|
1106 |
|
|
|
1107 |
\begin{textblock}{7.5}(8,3)
|
|
|
1108 |
\begin{itemize}
|
|
|
1109 |
\item use \textbf{Brzozowski derivatives} for regex matching rather\\ than NFAs/DFAs% and lexing
|
|
|
1110 |
\item based on work by \textbf{Christian Urban} and \textbf{Roy Dyckhoff}\bigskip
|
|
|
1111 |
\item applications in network security (traffic filtering)
|
|
|
1112 |
\item formal verification of correctness and speed (\textbf{Isabelle} theorem prover)
|
|
|
1113 |
\end{itemize}
|
|
|
1114 |
\end{textblock}
|
|
|
1115 |
|
|
|
1116 |
\end{frame}
|
|
|
1117 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
1118 |
|
|
|
1119 |
|
|
|
1120 |
%%\end{document}
|
|
|
1121 |
|
|
|
1122 |
|
|
|
1123 |
|
|
959
|
1124 |
%%% Local Variables:
|
|
876
|
1125 |
%%% mode: latex
|
|
|
1126 |
%%% TeX-master: t
|
|
959
|
1127 |
%%% End:
|