Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tree-sitter: an incremental parsing system for programming tools

github.com

Post reply on HN
Print view View original

11–20 of 138 posts

Re: Tree-sitter: an incremental parsing system for programming tools

#11

Post by srcreigh »

Tree Sitter is amazing. The parsing is fast enough to run on every keystroke. The parse tree is extremely concise and readable. It resembles an AST more than a parse tree (ie no 11 levels of binary op precedence rules in the tree). The parse tree emits specific ERROR nodes, so you can get a semi-functional tree even with broken syntax.

I can't wait for the tools to get built with this. Paredit for TypeScript. Syntax-tree based highlighting (vs regex highlighting). A command to "add an arg to current function" which works across languages. A command to add a CSS class to the nearest JSX node, or to walk up the tree at the className="| ..." position, adding a new className if it doesn't exist.

There's a nicely documented Emacs package for this [1]. The documentation is at [2]. The parse trees work great. There's syntax highlighting support and tree-walking APIs. There's a bit of confusion about TSX vs typescript langs but it's fixable with some config change [3].

[1]: https://github.com/ubolonton/emacs-tree-sitter [2]: https://ubolonton.github.io/emacs-tree-sitter/ [3]: https://github.com/ubolonton/emacs-tree-sitter/issues/66#iss...

Re: Tree-sitter: an incremental parsing system for programming tools

#12

Post by chrisseaton »

Tree-sitter is unfathomable to me. This is the grammar for Ruby:

https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...

I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?

Re: Tree-sitter: an incremental parsing system for programming tools

#13

Post by [deleted] »

ducktective wrote: post #6
pcr910303 wrote: post #5

To me, the most impressive use of tree-sitter was an iOS text editor that uses it to parse huge JSON files / mixed language files and highlight them in a very robust way. [0][1] I’m hoping tree-sitter becomes more common like LSP and Emacs can get exact highlighting and other tools with it… [0]: https://twitter.com/simonbs/status/1352697855845273600 [1]: https://twitter.com/simonbs/status/1362492842141171720?s=21

Yeah but I don't think LSP specs contain syntax-highlighting or semantic highlighting.

[deleted]

Re: Tree-sitter: an incremental parsing system for programming tools

#14

Post by patrec »

guerrilla wrote: post #9

Is the use case for this mainly IDEs or is it intended to replace traditional lexer and parser generators too?

I have used tree-sitter, but only for a very simple use case. The main shortcoming I am aware of are error messages, see here:

https://github.com/tree-sitter/tree-sitter/issues/255

Tree sitter will basically always generate a parse tree, even for malformed input, in which case it will add ERROR nodes for the bits it doesn't like (it will also inform you that there were problems with the parse by setting a boolean attribute). So you have some information you can use to construct a useful error message yourself, but some parser generators will handle this better (although it has to be said that the difficulty of obtaining good error messages from a parser generator are still one of the main the reasons production parsers are mostly written by hand).

Re: Tree-sitter: an incremental parsing system for programming tools

#15

Post by anaerobicover »

chrisseaton wrote: post #12

Tree-sitter is unfathomable to me. This is the grammar for Ruby: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?

No, the Ruby grammar is actually an outlier from what I've seen; it has one of the largest/most complex external scanners: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...

Precisely because the language is complicated and less amenable to LR parsing.

Re: Tree-sitter: an incremental parsing system for programming tools

#16

Post by guerrilla »

patrec wrote: post #14
guerrilla wrote: post #9

Is the use case for this mainly IDEs or is it intended to replace traditional lexer and parser generators too?

I have used tree-sitter, but only for a very simple use case. The main shortcoming I am aware of are error messages, see here: https://github.com/tree-sitter/tree-sitter/issues/255 Tree sitter will basically always generate a parse tree, even for malformed input, in which case it will add ERROR nodes for the bits it doesn't like (it will also inform you that there were problems with the parse by setting a boolean att…

Ah I see, so the reparation isn't avoidable for now? That doesn't seem very appropraite for compilers then.

Re: Tree-sitter: an incremental parsing system for programming tools

#17

Post by ComputerGuru »

anaerobicover wrote: post #15
chrisseaton wrote: post #12

Tree-sitter is unfathomable to me. This is the grammar for Ruby: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?

No, the Ruby grammar is actually an outlier from what I've seen; it has one of the largest/most complex external scanners: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... Precisely because the language is complicated and less amenable to LR parsing.

Not a ruby developer here: that sounds terrifying! Does it make it harder to have a proper mental model of the language (note: not the libraries) or is this mainly because of flexibility (too many ways to skin one cat)?

Re: Tree-sitter: an incremental parsing system for programming tools

#18

Post by Grimm1 »

I recently used this to put together a unified PL classification model. It's nice because any language treesitter grows to support we'll support pretty effortlessly and treesitter captures more than enough nuance per language to derive high quality classifications.

It's fair to say we can classify a snippet of code based on either single or multiple AST paths produced by treesitter. Right now only doing the programming language but extending it to function classification or description etc isn't out of the question we just don't need it right now.

Re: Tree-sitter: an incremental parsing system for programming tools

#19

Post by codesnik »

chrisseaton wrote: post #12

Tree-sitter is unfathomable to me. This is the grammar for Ruby: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?

bison should be compared to https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... probably?

Re: Tree-sitter: an incremental parsing system for programming tools

#20

Post by chrisseaton »

codesnik wrote: post #19
chrisseaton wrote: post #12

Tree-sitter is unfathomable to me. This is the grammar for Ruby: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... I find it absolutely amazing that a grammar for something as complicated as Ruby can be so concise. Less than a thousand lines. The corresponding Bison grammar is 13k lines. And I think the tree-sitter one is scannerless so also includes the lexer?! How do they do it?

bison should be compared to https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... probably?

No the JSON file there is generated (I believe?) from the JavaScript I linked, while the Bison file is hand-written.

With tree-sitter you're hand-writing a 1k file. With Bison you're hand-writing a 13k file.

Post reply on HN