Re: [SPAM UNSURE] Re: Tree Sitter (was Re: cc-mode fontification feels random)

[Stephen Leake]

Daniel Colascione <dancol@dancol.org> writes:

> 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?

wisi also uses GLR. It prunes trees during parse when the parse stacks
contained in the trees are identical; it uses error recover cost and
length to decide which tree to delete, or picks one at random. It's an
error if more than one tree is alive at the end of parse. That's because
programming languages must be unambiguous. It would be possible to adapt
the wisi parser to use some other pruning strategy. 

-- 
-- Stephe