equal
deleted
inserted
replaced
9 % \usepackage{hyperref} |
9 % \usepackage{hyperref} |
10 % \usepackage[margin=0.5in]{geometry} |
10 % \usepackage[margin=0.5in]{geometry} |
11 %\usepackage{pmboxdraw} |
11 %\usepackage{pmboxdraw} |
12 |
12 |
13 \title{POSIX Regular Expression Matching and Lexing} |
13 \title{POSIX Regular Expression Matching and Lexing} |
14 \author[1]{Chengsong Tan} |
14 \author{Chengsong Tan} |
15 \affil[1]{\\ Department of Informatics, King's College London\\ |
15 \affil{King's College London\\ |
16 London, UK\\ |
16 London, UK\\ |
17 \texttt{chengsong.tan@kcl.ac.uk}} |
17 \texttt{chengsong.tan@kcl.ac.uk}} |
18 \authorrunning{Chengsong Tan} |
18 \authorrunning{Chengsong Tan} |
19 \Copyright{Chengsong Tan} |
19 \Copyright{Chengsong Tan} |
20 |
20 |
164 report that they have found thousands of such evil regular expressions |
164 report that they have found thousands of such evil regular expressions |
165 in the JavaScript and Python ecosystems \cite{Davis18}. |
165 in the JavaScript and Python ecosystems \cite{Davis18}. |
166 |
166 |
167 This exponential blowup sometimes causes real pain in real life: |
167 This exponential blowup sometimes causes real pain in real life: |
168 for example on 20 July 2016 one evil regular expression brought the |
168 for example on 20 July 2016 one evil regular expression brought the |
169 webpage \href{http://stackexchange.com}{Stack Exchange} to its knees\cite{SE16}. |
169 webpage \href{http://stackexchange.com}{Stack Exchange} to its knees \cite{SE16}. |
170 In this instance, a regular expression intended to just trim white |
170 In this instance, a regular expression intended to just trim white |
171 spaces from the beginning and the end of a line actually consumed |
171 spaces from the beginning and the end of a line actually consumed |
172 massive amounts of CPU-resources and because of this the web servers |
172 massive amounts of CPU-resources and because of this the web servers |
173 ground to a halt. This happened when a post with 20,000 white spaces |
173 ground to a halt. This happened when a post with 20,000 white spaces |
174 was submitted, but importantly the white spaces were neither at the |
174 was submitted, but importantly the white spaces were neither at the |