3 ms·
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'
by 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 agoI 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 agoThank you!