Regex literals optimization (or how to cheat on benchmarks) | Hacker News Reader

Regex literals optimization (or how to cheat on benchmarks)

nitely.github.io

42 pointsnitely12 comments

How does it eg googles re2?

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.

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

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!

I call the technique "lexer modes" but it's trivial:

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:

    reader -> matcher (generated regular languages) -> lexer -> multiple parsers

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!

http://www.oilshell.org/blog/tags.html?tag=eggex#eggex

http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...

It doesn't. RE2 searches for a prefix of literals. If the regex doesn't start with one or more literals, then the full regex engine is ran.

How does nim-regex implement capture groups and zero-width assertions (like \b)? Both of those are tricky with DFAs.

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.

[0] https://github.com/nitely/nregex

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.

[0] http://lambda-the-ultimate.org/node/2064#comment-25469

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.

Reply on news.ycombinator.com