4 ms·

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. Ma

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.

froh 6y ago
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.
- chubot 6y ago
  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/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.5/source-code.wwz/_devb... http://www.oilshell.org/blog/2020/01/parser-benchmarks.html 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 http://www.oilshell.org/release/latest/doc/eggex.html
  - froh 6y ago
    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!
    - chubot 6y ago
      I call the technique "lexer modes" but it's trivial: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html 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 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! more posts: http://www.oilshell.org/blog/tags.html?tag=eggex#eggex http://www.oilshell.org/blog/tags.html?tag=eggex#eggex http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...
nitely 6y ago
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.

froh 6y ago

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.

chubot 6y ago
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/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.5/source-code.wwz/_devb... http://www.oilshell.org/blog/2020/01/parser-benchmarks.html 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 http://www.oilshell.org/release/latest/doc/eggex.html
- froh 6y ago
  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!
  - chubot 6y ago
    I call the technique "lexer modes" but it's trivial: When Are Lexer Modes Useful? http://www.oilshell.org/blog/2017/12/17.html 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 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! more posts: http://www.oilshell.org/blog/tags.html?tag=eggex#eggex http://www.oilshell.org/blog/tags.html?tag=eggex#eggex http://www.oilshell.org/blog/tags.html?tag=parsing-shell#parsing-shell http://www.oilshell.org/blog/tags.html?tag=parsing-shell#par...

nitely 6y ago

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.