11 \newcommand{\tabhead}[1]{\textbf{#1}} |
11 \newcommand{\tabhead}[1]{\textbf{#1}} |
12 \newcommand{\code}[1]{\texttt{#1}} |
12 \newcommand{\code}[1]{\texttt{#1}} |
13 \newcommand{\file}[1]{\texttt{\bfseries#1}} |
13 \newcommand{\file}[1]{\texttt{\bfseries#1}} |
14 \newcommand{\option}[1]{\texttt{\itshape#1}} |
14 \newcommand{\option}[1]{\texttt{\itshape#1}} |
15 |
15 |
16 |
16 \newcommand{\bderssimp}[2]{{#1} \backslash_{bsimp} {#2}} |
17 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
17 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
18 \newcommand{\ZERO}{\mbox{\bf 0}} |
18 \newcommand{\ZERO}{\mbox{\bf 0}} |
19 \newcommand{\ONE}{\mbox{\bf 1}} |
19 \newcommand{\ONE}{\mbox{\bf 1}} |
20 \def\lexer{\mathit{lexer}} |
20 \def\lexer{\mathit{lexer}} |
21 \def\mkeps{\mathit{mkeps}} |
21 \def\mkeps{\mathit{mkeps}} |
22 |
22 |
|
23 \def\AZERO{\textit{AZERO}} |
|
24 \def\AONE{\textit{AONE}} |
|
25 \def\ACHAR{\textit{ACHAR}} |
|
26 \def\ASEQ{\textit{ASEQ}} |
|
27 \def\AALTS{\textit{AALTS}} |
|
28 \def\ASTAR{\textit{ASTAR}} |
23 \def\DFA{\textit{DFA}} |
29 \def\DFA{\textit{DFA}} |
24 \def\bmkeps{\textit{bmkeps}} |
30 \def\bmkeps{\textit{bmkeps}} |
25 \def\retrieve{\textit{retrieve}} |
31 \def\retrieve{\textit{retrieve}} |
26 \def\blexer{\textit{blexer}} |
32 \def\blexer{\textit{blexer}} |
27 \def\flex{\textit{flex}} |
33 \def\flex{\textit{flex}} |
35 \def\Der{\mathit{Der}} |
41 \def\Der{\mathit{Der}} |
36 \def\nullable{\mathit{nullable}} |
42 \def\nullable{\mathit{nullable}} |
37 \def\Z{\mathit{Z}} |
43 \def\Z{\mathit{Z}} |
38 \def\S{\mathit{S}} |
44 \def\S{\mathit{S}} |
39 \def\rup{r^\uparrow} |
45 \def\rup{r^\uparrow} |
|
46 %\def\bderssimp{\mathit{bders}\_\mathit{simp}} |
|
47 \def\distinctWith{\textit{distinctWith}} |
|
48 |
40 \def\simp{\mathit{simp}} |
49 \def\simp{\mathit{simp}} |
41 \def\simpALTs{\mathit{simp}\_\mathit{ALTs}} |
50 \def\simpALTs{\mathit{simp}\_\mathit{ALTs}} |
42 \def\map{\mathit{map}} |
51 \def\map{\mathit{map}} |
43 \def\distinct{\mathit{distinct}} |
52 \def\distinct{\mathit{distinct}} |
44 \def\blexersimp{\mathit{blexer}\_\mathit{simp}} |
53 \def\blexersimp{\mathit{blexer}\_\mathit{simp}} |
|
54 \def\map{\textit{map}} |
|
55 \def\vsuf{\textit{vsuf}} |
|
56 \def\sflataux{\textit{sflat}\_\textit{aux}} |
|
57 \def\rrexp{\textit{rrexp}} |
|
58 \def\rsize{\textit{rsize}} |
|
59 \def\asize{\textit{asize}} |
|
60 \def\rerase{\textit{rerase}} |
|
61 \def\erase{\textit{erase}} |
|
62 \def\STAR{\textit{STAR}} |
|
63 \def\flts{\textit{flts}} |
|
64 |
45 %---------------------------------------------------------------------------------------- |
65 %---------------------------------------------------------------------------------------- |
46 %This part is about regular expressions, Brzozowski derivatives, |
66 %This part is about regular expressions, Brzozowski derivatives, |
47 %and a bit-coded lexing algorithm with proven correctness and time bounds. |
67 %and a bit-coded lexing algorithm with proven correctness and time bounds. |
48 |
68 |
49 %TODO: look up snort rules to use here--give readers idea of what regexes look like |
69 %TODO: look up snort rules to use here--give readers idea of what regexes look like |
50 |
70 |
51 |
71 |
52 Regular expressions are widely used in computer science: |
72 Regular expressions are widely used in computer science: |
53 be it in IDEs with syntax hightlighting and auto completion, |
73 be it in text-editors\parencite{atomEditor} with syntax hightlighting and auto completion, |
54 command line tools like $\mathit{grep}$ that facilitates easy |
74 command line tools like $\mathit{grep}$ that facilitates easy |
55 text processing , network intrusion |
75 text processing , network intrusion |
56 detection systems that rejects suspicious traffic, or compiler |
76 detection systems that rejects suspicious traffic, or compiler |
57 front ends--there is always an important phase of the |
77 front ends--the majority of the solutions to these tasks |
58 task that involves matching a regular |
78 involve lexing with regular |
59 exression with a string. |
79 expressions. |
|
80 |
60 Given its usefulness and ubiquity, one would imagine that |
81 Given its usefulness and ubiquity, one would imagine that |
61 modern regular expression matching implementations |
82 modern regular expression matching implementations |
62 are mature and fully-studied. |
83 are mature and fully-studied. |
63 |
84 |
64 If you go to a popular programming language's |
85 If you go to a popular programming language's |