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]{Annonymous} |
14 \author[1]{Chengsong Tan \\ King's College London\\chengsong.tan@kcl.ac.uk} |
15 |
15 |
16 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
16 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
17 \newcommand{\ZERO}{\mbox{\bf 0}} |
17 \newcommand{\ZERO}{\mbox{\bf 0}} |
18 \newcommand{\ONE}{\mbox{\bf 1}} |
18 \newcommand{\ONE}{\mbox{\bf 1}} |
19 \def\lexer{\mathit{lexer}} |
19 \def\lexer{\mathit{lexer}} |
158 report that they have found thousands of such evil regular expressions |
158 report that they have found thousands of such evil regular expressions |
159 in the JavaScript and Python ecosystems \cite{Davis18}. |
159 in the JavaScript and Python ecosystems \cite{Davis18}. |
160 |
160 |
161 This exponential blowup sometimes causes real pain in ``real life'': |
161 This exponential blowup sometimes causes real pain in ``real life'': |
162 for example one evil regular expression brought on 20 July 2016 the |
162 for example one evil regular expression brought on 20 July 2016 the |
163 webpage \href{http://stackexchange.com}{Stack Exchange} to its knees. |
163 webpage \href{http://stackexchange.com}{Stack Exchange} to its knees\cite{SE16}. |
164 In this instance, a regular expression intended to just trim white |
164 In this instance, a regular expression intended to just trim white |
165 spaces from the beginning and the end of a line actually consumed |
165 spaces from the beginning and the end of a line actually consumed |
166 massive amounts of CPU-resources and because of this the web servers |
166 massive amounts of CPU-resources and because of this the web servers |
167 ground to a halt. This happened when a post with 20,000 white spaces |
167 ground to a halt. This happened when a post with 20,000 white spaces |
168 was submitted, but importantly the white spaces were neither at the |
168 was submitted, but importantly the white spaces were neither at the |