2 ms·

Nice! I had a similar idea to use MCTS to explore various AST generations through an incremental AST parser[0], so I could generate runnable code via LLM at a h

Nice! I had a similar idea to use MCTS to explore various AST generations through an incremental AST parser[0], so I could generate runnable code via LLM at a higher success rate than what we were seeing initially with them. I never got around to it, but this makes me curious to circle back around. [0] There are few parsers that consider "failed, but could run if the next symbol is valid" and "failed and no way to continue" as separate statuses so you can make progress by enumerating (hopefully intelligently so) the space of valid states. Surprisingly TreeSitter wasn't one of them though, for that it's just "fail".

namin 3y ago
Interesting! Is the end goal similar to the outlines library: https://github.com/outlines-dev/outlines https://github.com/outlines-dev/outlines ?
- ianbutler 3y ago
  Yes basically to create some level control for guided program generation.
morgante 3y ago
> [0] There are few parsers that consider "failed, but could run if the next symbol is valid" and "failed and no way to continue" as separate statuses so you can make progress by enumerating (hopefully intelligently so) the space of valid states. Surprisingly TreeSitter wasn't one of them though, for that it's just "fail". I'm not quite sure I follow how this differs from Tree Sitter's error recovery. Do you have an example of a parser that implements this?
- ianbutler 3y ago
  https://pypi.org/project/parso/ https://pypi.org/project/parso/ is what I settled on when digging into this. It's been something like 8 months, but iirc tree-sitter would not emit anything I was able to discern as recoverable. I recognize they do implement a pretty robust error recovery, but the returned error wasn't clearly differentiable from a strict failure in a way I could program against where as for the same partially incomplete code parso would return something different than if it was unrecoverable. I can't remember much more than that and it's entirely possible I was missing some type of configuration to make tree-sitter do the same. Unfortunately it looks like I never pushed my playground code for this idea off of my server which is currently packed up as part of a cross country move I'm on the tail end of otherwise I'd get you the code verbatim.

namin 3y ago

Interesting! Is the end goal similar to the outlines library: https://github.com/outlines-dev/outlines https://github.com/outlines-dev/outlines ?

ianbutler 3y ago
Yes basically to create some level control for guided program generation.

morgante 3y ago

> [0] There are few parsers that consider "failed, but could run if the next symbol is valid" and "failed and no way to continue" as separate statuses so you can make progress by enumerating (hopefully intelligently so) the space of valid states. Surprisingly TreeSitter wasn't one of them though, for that it's just "fail". I'm not quite sure I follow how this differs from Tree Sitter's error recovery. Do you have an example of a parser that implements this?

ianbutler 3y ago
https://pypi.org/project/parso/ https://pypi.org/project/parso/ is what I settled on when digging into this. It's been something like 8 months, but iirc tree-sitter would not emit anything I was able to discern as recoverable. I recognize they do implement a pretty robust error recovery, but the returned error wasn't clearly differentiable from a strict failure in a way I could program against where as for the same partially incomplete code parso would return something different than if it was unrecoverable. I can't remember much more than that and it's entirely possible I was missing some type of configuration to make tree-sitter do the same. Unfortunately it looks like I never pushed my playground code for this idea off of my server which is currently packed up as part of a cross country move I'm on the tail end of otherwise I'd get you the code verbatim.