6 ms·

IMHO the majority of engineers not understanding lexing/parsing beyond generators has held back good engineering of incremental parsers/lexers for a long time.

IMHO the majority of engineers not understanding lexing/parsing beyond generators has held back good engineering of incremental parsers/lexers for a long time. Things like tree-sitter took forever to come along, but the research projects that built the algorithms they rely on are a quarter century old.(https://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5885.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1997/5885.html) Meanwhile, incremental lexing and incremental recursive descent parsing and LL are actually not that hard (incremental LR is trickier). It's just that few people really understand how any of it works to implement it. This is not a "it was not needed" issue. Lexing times of files for syntax highlighting is still "seconds" for larger files, for example. Meanwhile, i can explain near-optimal incremental lexing to someone who knows how lexers work in a few bullet points, and it's trivial to implement: 1. As your lexer looks at characters, keep track of the maximum lookahead and lookbehind used during a lex. 2. When some range of the string to lex is invalidated, adjust the invalidation bounds to include the maximum lookhead/lookbehind as well. 3. Relex the invalidated portion of the string. That's it. For optimality, compute the maximum lookhead/lookbehind on a per-token basis, instead on a per-lex basis (this is trivial if your editor is already storing the tokens under the text somewhere) If you store position info in your tokens, you can easily adjust as well. For incremental recursive descent parsing, it's similar - only rules who ever looked tokens that changed could be affected by them. You can easily keep the interval of tokens that a given rule looked at. (If you want truly optimal, you can store the set of intervals looked at, but this is almost always overkill) If all you ever have is a generator, you will never implement any of the above until your generator does. I have watched tons of projects spend lots of time optimizing grammars, doing weird caching, etc, when a few simple/better algorithms would have saved them from all of it. (which is why in that sense, tree-sitter has been a revolution)

bsder 4y ago
> IMHO the majority of engineers not understanding lexing/parsing beyond generators has held back good engineering of incremental parsers/lexers for a long time. That's a touch unfair. You could easily extend that statement to "The predominant languages of C and C++ have held back good engineering of parsers/lexers." period. This is due to the fact that you effectively have to parse the universe to resolve the symbol table in both languages. In addition, people didn't need incremental parsing until syntax highlighting became widespread via LSPs. Before that, you were always working at the compile level, so why put in all the work for an incremental parser you were never going to make use of? People have recently been designing the languages, themselves to better support parsing/lexing paradigms that can be incremental and restarted. This is why most modern languages have converged to having specific syntax to delineate the difference between variable name and variable type, for example. Rust, for example, has fairly funky things around "unary minus" because of its design for parsing and lexing.
brhsagain 4y ago
This is extremely interesting to me. I looked at the papers tree-sitter referenced but they were all written assuming an LR/generator-based parser and I couldn't figure out how to adapt it to recursive descent. Let's say I've parsed an AST binary_expression lhs: number rhs: binary_expression lhs: number rhs: call_expression func: identifier args: call_argument_list [0]: number [1]: number and I've detected that `rhs` on line 3 has changed. So I go back to the start of the node. What do I do then? How do I know I need to parse an expression there and that it belongs to the rhs of a binary expression? In the literature, this is solved by storing the parse state. How do you do that with recursive descent? Is there something you'd recommend reading to understand how to do incremental parsing for recursive descent specifically?
- DannyBee 4y ago
  I implemented it for ANTLR (which is LL(*), so not fully recursive descent, but top-down) but never got around to shepherding the patches through. https://github.com/dberlin/antlr4ts/blob/incremental/IncrementalParsing.md https://github.com/dberlin/antlr4ts/blob/incremental/Increme... is an intro. The commits on that branch should give you some idea. I have regular non-TS ANTLR4 support somewhere too. I'm happy to chat about it elsewhere as well, drop me a line at my email.
  - brhsagain 4y ago
    Thank you!

bsder 4y ago

> IMHO the majority of engineers not understanding lexing/parsing beyond generators has held back good engineering of incremental parsers/lexers for a long time. That's a touch unfair. You could easily extend that statement to "The predominant languages of C and C++ have held back good engineering of parsers/lexers." period. This is due to the fact that you effectively have to parse the universe to resolve the symbol table in both languages. In addition, people didn't need incremental parsing until syntax highlighting became widespread via LSPs. Before that, you were always working at the compile level, so why put in all the work for an incremental parser you were never going to make use of? People have recently been designing the languages, themselves to better support parsing/lexing paradigms that can be incremental and restarted. This is why most modern languages have converged to having specific syntax to delineate the difference between variable name and variable type, for example. Rust, for example, has fairly funky things around "unary minus" because of its design for parsing and lexing.

brhsagain 4y ago

This is extremely interesting to me. I looked at the papers tree-sitter referenced but they were all written assuming an LR/generator-based parser and I couldn't figure out how to adapt it to recursive descent. Let's say I've parsed an AST binary_expression lhs: number rhs: binary_expression lhs: number rhs: call_expression func: identifier args: call_argument_list [0]: number [1]: number and I've detected that `rhs` on line 3 has changed. So I go back to the start of the node. What do I do then? How do I know I need to parse an expression there and that it belongs to the rhs of a binary expression? In the literature, this is solved by storing the parse state. How do you do that with recursive descent? Is there something you'd recommend reading to understand how to do incremental parsing for recursive descent specifically?

DannyBee 4y ago
I implemented it for ANTLR (which is LL(*), so not fully recursive descent, but top-down) but never got around to shepherding the patches through. https://github.com/dberlin/antlr4ts/blob/incremental/IncrementalParsing.md https://github.com/dberlin/antlr4ts/blob/incremental/Increme... is an intro. The commits on that branch should give you some idea. I have regular non-TS ANTLR4 support somewhere too. I'm happy to chat about it elsewhere as well, drop me a line at my email.
- brhsagain 4y ago
  Thank you!