I remember a neat feature of re2 was you could give it a bunch of regex, and get it to check for all of them at the same time. Made all the difference in an early spam filter I built.
With 1960s computer science - regular languages, their equivalent nondeterministic finite state machines or nondeterministic finite automata NFA and the transformation thereof into deterministic ones DFA. In theoretical worst case the size of the DFA is exponential in size to the NFA, in practice, re2, these algorithms are frickin' awesome.
In theoretical worst case the size of the DFA is exponential in size to the NFA
That's true, but mostly irrelevant in practice as you say. Because the NFA is linear in proportion to PATTERN size, not input size, and even an exponential blowup from there isn't a problem. (and many patterns may not blow up)
For example I wrote a very large set of regular languages to describe shell syntax. Compiling it all to a full DFA and then assembly via re2c creates something like 30 KiB of machine code. And it runs fast.
Ho ly cow I just skimmed the oil source tree, trying to see how you generate the regex based lexers and how you combine them with a parser generator, or a hand crafted stack machine? which depending on its current state would presumably switch between the different regex DFAs?
The eggex approach looks very interesting, stand alone, independent from oil. I appreciate they are separate!
The lexer takes the mode parameter and has extra logic for disambiguation. There are multiple parsers for multiple dialects, and they're both hand-written and generated.
Feel free to follow up if this catches your interest. I'm looking for feedback on both Eggex and Oil!
Yeah, nim-regex is based on NFA. I'm not aware of a pure DFA that is correct and also supports those. I built an hybrid a while ago[0], but it's slower than nim-regex when it needs to capture/assert, I should profile it and find out why some day.
re2 implements captures as "tagged DFAs" (Laurikari algorithm) while zero-width assertions are implemented as running the algorithm "one byte ahead". Neither of these techniques is very well known.
AFAIK, RE2 does not implement a tagged DFA. It implements a DFA that runs when captures are not required and/or to find a match within the text and then it runs the NFA to record the captures.
I'm aware of Laurikari's algorithm, I'm not aware of it being correct[0]. Also, their algorithm has POSIX semantics, RE2 (and most PLs regex engines) has PCRE semantics.
As an aside, it's possible to modify Laurikari's algorithm slightly and obtain PCRE semantics w.r.t. capturing groups, and those correctly. (POSIX capturing semantics are designed for standards specs. I've never met an actual practicing programmer who wanted those semantics instead of the PCRE ones)
That's good to know. Is there an implementation of it? I know of TRE, regex-tdfa, ocaml-regex-tfa, and re2c, they all implement Laurikari's algorithm (or a variation of it), but have POSIX semantics.
12 comments
[ 67.9 ms ] story [ 390 ms ] threadI remember a neat feature of re2 was you could give it a bunch of regex, and get it to check for all of them at the same time. Made all the difference in an early spam filter I built.
That's true, but mostly irrelevant in practice as you say. Because the NFA is linear in proportion to PATTERN size, not input size, and even an exponential blowup from there isn't a problem. (and many patterns may not blow up)
For example I wrote a very large set of regular languages to describe shell syntax. Compiling it all to a full DFA and then assembly via re2c creates something like 30 KiB of machine code. And it runs fast.
https://www.oilshell.org/release/0.8.5/source-code.wwz/_devb...
http://www.oilshell.org/blog/2020/01/parser-benchmarks.html
So as you say, you get the best of both worlds: a concise language, and speed. The only problem is the syntax, which I'm fixing:
http://www.oilshell.org/release/latest/doc/eggex.html
The eggex approach looks very interesting, stand alone, independent from oil. I appreciate they are separate!
When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html
Overview of the parser:
How to Parse Shell Like a Programming Language http://www.oilshell.org/blog/2019/02/07.html
You could look at the architecture like this:
The lexer takes the mode parameter and has extra logic for disambiguation. There are multiple parsers for multiple dialects, and they're both hand-written and generated.Feel free to follow up if this catches your interest. I'm looking for feedback on both Eggex and Oil!
more posts:
http://www.oilshell.org/blog/tags.html?tag=eggex#eggex
http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...
[0] https://github.com/nitely/nregex
I'm aware of Laurikari's algorithm, I'm not aware of it being correct[0]. Also, their algorithm has POSIX semantics, RE2 (and most PLs regex engines) has PCRE semantics.
[0] http://lambda-the-ultimate.org/node/2064#comment-25469