3 ms·

The main reason is that the parsing model is applying a whole bunch of unanchored regexes to the unparsed remainder of the line one after another until one matc

by chubot 6y ago

The main reason is that the parsing model is applying a whole bunch of unanchored regexes to the unparsed remainder of the line one after another until one matches, then starting again for the next token. This means each token parsed can require dozens of regex matches over the same characters. Hm but why can't you just OR them together? That is perfectly fine with a regular language engine. For example, I OR together about 50 different regexes here (including a whole bunch of constant strings) for the ShCommand mode: https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_devbuild/tmp/osh-lex.re2c.h https://www.oilshell.org/release/0.8.pre6/source-code.wwz/_d... Despite this big mess, everything "just works", i.e. the lexer reads every byte of input just once. re2c picks the alternative with longest match, and it picks the first match to break ties. ----- I suspect the reason that you can't do this is (1) Sublime was originally implemented with a Perl-style regex engine and (2) the order of | clauses matters more when using a backtracking engine. It doesn't have the simple rule that an automata-based engine has. My claim is that you avoid performance problems by using a "regular language" engine. So I think what you point out supports this, even it might be a slightly different issue than "more backtracking". I think you are saying that Sublime's parsing model prevents composition by |, which makes lexing slow, because it forces you to read each byte many times. (in addition to the captures issue, let me think about that)

trishume 6y ago
Two reasons: captures, and it needs to know which of the regexes matched. I meant to but forgot to mention in my original comment that the reason Sublime's built-in highlighter is the fastest is they wrote a custom regex engine which basically does the equivalent of or-ing them together but unlike all other regex engines handles captures and information about which one matched properly while doing so. The custom engine doesn't do backtracking and it falls back to Oniguruma for regexes that use fancy features. So yah it's in theory possible you just need to write a custom regex engine to do it.
- fanf2 6y ago
  re2c supports captures and it will tell you which regex matched. http://re2c.org/manual/manual.html#submatch-extraction http://re2c.org/manual/manual.html#submatch-extraction

by chubot 6y ago

trishume 6y ago

Two reasons: captures, and it needs to know which of the regexes matched. I meant to but forgot to mention in my original comment that the reason Sublime's built-in highlighter is the fastest is they wrote a custom regex engine which basically does the equivalent of or-ing them together but unlike all other regex engines handles captures and information about which one matched properly while doing so. The custom engine doesn't do backtracking and it falls back to Oniguruma for regexes that use fancy features. So yah it's in theory possible you just need to write a custom regex engine to do it.

fanf2 6y ago
re2c supports captures and it will tell you which regex matched. http://re2c.org/manual/manual.html#submatch-extraction http://re2c.org/manual/manual.html#submatch-extraction