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

21–30 of 138 posts

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

#21

Post by codesnik »

ComputerGuru wrote: post #17
anaerobicover wrote: post #15

Earlier quoted context omitted.

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

It's mostly to work less surprising to the programmer, AFAIR. Probably the most complexity is from having to differentiate local variables and methods depending if the symbol had an assignment before in the scope.

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

#22

Post by revscat »

ComputerGuru wrote: post #17
anaerobicover wrote: post #15

Earlier quoted context omitted.

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

Flexibility. “Too many” is debatable: most organizations wind up settling on a subset of the idioms that Ruby provides, and some of the more esoteric constructs see infrequent use anywhere.

There has been, however, discussion about the need to clean up some of the lesser-used language feature, but obviously doing so carries risks.

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

#24

Post by anaerobicover »

ComputerGuru wrote: post #17
anaerobicover wrote: post #15

Earlier quoted context omitted.

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

I don't write Ruby regularly either, but I wouldn't say that syntactic complexity, is necessarily equivalent to semantic complexity. And the syntax is the only part that's relevant to Tree-sitter: it's not an interpreter/compiler.

Note also that (as I alluded to above) the parsing technique that Tree-sitter uses, "LR parsing", makes some things more difficult to parse than they'd be with another kind of parser. This is a deliberate trade-off, because LR parsing makes certain features of Tree-sitter, like fast re-parsing in response to input changes, much much easier.

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

#25

Post by ahelwer »

I half-wrote a tree-sitter grammar for a niche DSL (the PRISM probabilistic model checking language). It was a very nice experience. It's part of another half-written side project to create a language server for PRISM; I still haven't gotten around to making the whole end-to-end pipeline work.

With its syntax tree query frontend I wonder whether tree-sitter would make a good interpreter frontend for some niche languages, or you need something more powerful.

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

#26

Post by RangerScience »

ComputerGuru wrote: post #17
anaerobicover wrote: post #15

Earlier quoted context omitted.

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

My mental model of Ruby is one the simplest of any of the languages I've worked with, but it's also the hardest to put into any words. JS actually does beat it out, and then Scala and Python come after.

Everything is kind-of-but-not-really an object, a reference, and a function, all at the same time - which sounds complicated but in my head... turns out to be pretty simple. Everything's just kind of different flavors of the same thing. `attr_accessor` is a good place to see this in action.

The flexibility comes more from the variety of available core language options (procs, blocks, and lambdas) and core libraries (map/each/collect, for example), not from a variety of underlying concepts.

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

#27

Post by lalaithion »

srcreigh wrote: post #11

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

Maybe I can finally have this syntax highlighting style: https://youtu.be/b0EF0VTs9Dc?t=900

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

#29

Post by dcreager »

srcreigh wrote: post #11

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

Worth calling out that the syntax highlighting support is used to highlight several languages in github.com. (Linguist is still used for the long tail of languages, but we plan to migrate more and more over to tree-sitter-based highlighting over time.)

The query language is also what's used to drive the fuzzy/ctags-like Code Navigation feature. Both of those are powered by tree-sitter query files defined in each language's repo, like these for Go: https://github.com/tree-sitter/tree-sitter-go/tree/master/qu...

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

#30

Post by dcreager »

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?

This is more a function of Ruby than of tree-sitter. The tree-sitter grammars for other languages are hopefully less inscrutable. For Ruby, we basically just ported whitequark's parser [1] over to tree-sitter's grammar DSL and scanner API.

[1] https://github.com/whitequark/parser

Post reply on HN