Regular Expression
a finite string describing a regular ‹formal language
--- https://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory
--- automata-and-formal-languages-cheatsheet.pdf
resource LTRE, my finite automaton regular expression engine and formal languages playground --- https://github.com/Bricktech2000/LTRE
resource CPS-RE, my tiny backtracking regular expression engine in continuation›-passing style --- https://github.com/Bricktech2000/CPS-RE
resource Regular Expression Matching Can Be Simple And Fast by Russ Cox, an intro to finite automaton regular expression engines and a manifesto on why there are no good excuses to use backtracking engines --- regexp1.html --- https://swtch.com/~rsc/regexp/regexp1.html
resource Regular Expression Matching: the Virtual Machine Approach by Russ Cox, notably the discussions on submatch extraction --- regexp2.html and nfa-posix.y.c and nfa-perl.y.c and regexp-bytecode.c --- https://swtch.com/~rsc/regexp/regexp2.html and https://swtch.com/~rsc/regexp/nfa-posix.y.txt and https://swtch.com/~rsc/regexp/nfa-perl.y.txt and https://swtch.com/~rsc/regexp/regexp-bytecode.c.txt
resource Regular Expression Matching in the Wild by Russ Cox, practical tips on writing regular expression engines --- regexp3.html and dfa0.c and dfa1.c and nfa.c --- https://swtch.com/~rsc/regexp/regexp3.html and https://swtch.com/~rsc/regexp/dfa0.c.txt and https://swtch.com/~rsc/regexp/dfa1.c.txt and https://swtch.com/~rsc/regexp/nfa.c.txt
resource Andrew Gallant's blog posts on
ripgrep, more practical tips on writing regular expression engines --- ripgrep is faster than {grep, ag, git grep, ucg, pt, sift} - Andrew Gallant's Blog.pdf and Regex engine internals as a library - Andrew Gallant's Blog.pdf --- https://blog.burntsushi.net/ripgrep/ and https://blog.burntsushi.net/regex-internals/
in formal language theory, regular expressions support alternation r|s, concatenation rs, Kleene star r* and grouping (r); ? and + are omitted since r? = r|ε and r+ = rr*. additionaly, ∅ denotes the empty ‹set, ε the set containing the empty word, and any other character the set containing the word formed by that character. in truth, grouping (r) is redundant and only needed because of infix notation, and the empty string ε and empty set ∅ are redundant and only needed because the notation can't express the empty concatenation and empty alternation, respectively
regular expressions are not a "notation for describing patterns of text". they are a notation for describing the regular ‹formal languages. so many get it wrong; see, for example, A Regular Expression Matcher. Code by Rob Pike, Exegesis by Brian Kernighan --- beautiful.html --- https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html. as a rule of thumb, if a pragmatic regular expression engine doesn't support alternation or grouping or backtracking, chances are high it's not a regular expression engine. sure, it matches patterns of text, but that's not what it means to be a regular expression engine
there exist several algorithms for the determinization of regular expressions, but they're all kind of the same. Thompson's construction (Regular Expression Search Algorith by Thompson) and Aho's "followpos" algorithm (Principles of Compiler Design by Aho and Ullman) both convert regular expressions to equivalent non-deterministic finite acceptor graph intermediate representations. and the powerset construction, the "lock-step" algorithm and the McNaughton--Yamada algorithm (Regular Expressions and State Graphs for Automata by McNaughton and Yamada) are just different takes on computing brzozowski derivatives (Derivatives of Regular Expressions by Janusz A. Brzozowski) on those non-deterministic intermediate representations. see also https://youtu.be/tAw9-nTCuzI, an overview of this all, by Kay Lack
properties (not canonical)
commutitivity of alternation r|s = s|r
idempotence of alternation r|r = r
associativity of alternation r|s|t = r|(s|t) = (r|s)|t
identity of alternation r|∅ = r
annihilation of alternation r|Σ* = Σ*
associativity of concatenation rst = (rs)t = r(st)
identity of concatenation rε = r
annihilation of concatenation r∅ = ∅
left distributivity r(s|t) = rs|rt
right distributivity (s|t)r = sr|tr
idempotence of Kleene star r* = r**
Kleene star of ∅ and ε ∅* = ε* = ε
Kleene star of ? and + (r|ε)* = (rr*)* = r*
Extended Regular Expression
the regular ‹formal languages are closed under complementation, so it is only natural to extend regular expressions with a complementation operator !r. this is seldom done in practice, however---and that's a shame, because these extended ‹regular expressions are more natural and more concise, as argued in Regular Expressions and State Graphs for Automata by McNaughton and Yamada (subsection A Specification Language for Automata) and in Regular-expression derivatives reexamined by Owens, Reppy and Turon (section 5.1 Extended Regular Expressions) and in RE#: High Performance Derivative-Based Regex Matching by Varatalu, Veanes and Ernits (section 2 Motivating Examples)
the introduction of complementation induces a set of dual operators. the dual of alternation \(R \mid S = w.\ w \in R \lor w \in S\) is intersection \(R \mathbin\& S = \overline{\overline R \mid \overline S} = w.\ w \in R \land w \in S\), the dual of concatenation \(R \cdot S = w.\ \exists rs = w.\ r \in R \land s \in S\) is dual concatenation \(R \odot S = \overline{\overline R \cdot \overline S} = w.\ \forall rs = w.\ r \in R \lor s \in S\), and the dual of the Kleene star \(R^* = w.\ \exists r_0 \dots r_n = w.\ \forall r_\circ \in R\) is the dual Kleene star \(R^\circledast = \overline{\overline R^*} = w.\ \forall r_0 \dots r_n = w.\ \exists r_\circ \in R\) --- The dual of concatenation by Alexander Okhotin --- doi_10.1016_j.tcs.2005.07.019.pdf --- https://www.sciencedirect.com/science/article/pii/S0304397505004056. the suggestive \(R \cdot' S = w.\ \exists rs = w.\ r \in R \lor s \in S\) and its dual \(\overline{\overline R \cdot' \overline S} = R \odot' S = w.\ \forall rs = w.\ r \in R \land s \in S\) turn out to be uninteresting because their quantifiers distribute so they simplify to \(w.\ (\exists rs = w.\ r \in R) \lor (\exists rs = w.\ s \in S) = R \cdot \overline\varnothing \mid \overline\varnothing \cdot S\) and \(w.\ (\forall rs = w.\ r \in R) \land (\forall rs = w.\ s \in S) = R \odot \varnothing \mathbin\& \varnothing \odot S\), respectively. similarly, the suggestive \(R^{*'} = w.\ \exists r_0 \dots r_n = w.\ \exists r_\circ \in R\) and its dual \(\overline{\overline R^{*'}} = R^{\circledast'} = w.\ \forall r_0 \dots r_n = w.\ \forall r_\circ \in R\) simplify to \(w.\ \exists srs' = w.\ r \in R = \overline\varnothing \cdot R \cdot \overline\varnothing\) and \(w.\ \forall srs' = w.\ r \in R = \varnothing \odot R \odot \varnothing\), respectively
note an intuition for the dual operators is that while concatenation and Kleene star encode "existential valitidy" if you look at this word right, all of it will be valid, dual concatenation and dual Kleene star encode "universal invalidity" no matter how you look at this word, some of it will be invalid