On Jul 21, 2021, at 9:16 PM, Daniel Colascione <dancol@dancol.org> wrote:


On 7/21/21 12:15 PM, Perry E. Metzger wrote:
On 7/21/21 12:21, Daniel Colascione wrote:
On 7/21/21 7:43 AM, Perry E. Metzger wrote:
Thought I would note that there's a substantial literature now on incremental parsing, especially the sort that is needed for editor tools. One doesn't need to reinvent the algorithms, they're out there waiting to be used. The Tree Sitter project is based on previous published work.

There is indeed a big literature! I wish there were a bigger literature on *composable* incremental parsers though. IMHO, what we need is an incremental GLR system (yes, GLR is bad worst-case, but it's not a practical concern) that spits out a parse *forest* which we then pare down to a parse tree with ad-hoc syntactic consistency rules. Something like this naturally supports multi-language modes and incorporation of out-of-band semantic information.

Tree sitter handles GLR.


Cool. How does it prune the parse forest?

I’m not an expert, but the author talked about using grammar definition to reject branches in his talk.

Yuan