3 ms·
Tree-sitter is unfathomable to me. This is the grammar for Ruby: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/grammar.js https://github.com/tree
by chrisseaton 6y ago
Tree-sitter is unfathomable to me. This is the grammar for Ruby:
https://github.com/tree-sitter/tree-sitter-ruby/blob/master/grammar.js 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?
- anaerobicover 6y agoNo, 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/src/scanner.cc https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... Precisely because the language is complicated and less amenable to LR parsing.
- ComputerGuru 6y agoNot 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)?
- codesnik 6y agoIt'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.
- revscat 6y agoFlexibility. “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.
- anaerobicover 6y agoI 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.
- tp3 6y agoSo, a syntactic tree is a list of elements, grouped by their ordering, which are to be parsed from their arguments, as they appeared in the input. Or a grammar tree, which is a set of elements. There's many things we can do to make Tree-sitter simpler to read and write. Perhaps, like in Perl, there are syntactic categories of types that make it much easier to find things like nodes in a tree, since they're the ones that come in the input. Or I'd be willing to say that maybe, like in Haskell, certain aspects of the language, are syntactic categories, like the parser. So some things that might not be obvious in code, like what the syntax for a class of names is, might be obvious in theory, too. Or, at least they might be obvious in a particular way. Or some aspects of the compiler are really special, and we can infer those in terms of what the compiler does. Or, of course, we can do all these other things, too. We can rewrite the parser, or the compiler, to try to do more or less anything that the parser does. Or maybe we can make Tree-sitter a lot simpler in general. Which I think is probably what you've been thinking about.
- RangerScience 6y agoMy 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.
- e12e 6y ago> Not a ruby developer here: that sounds terrifying! Does it make it harder to have a proper mental model of the language It is a little terrifying in the sense that I'd not want to write language level tools (eg: syntax highlighter). But if you have scheme on one end and natural language on the other, ruby leans à bit towards natural language - but in a good way. In some ways ruby isn't that different from Smalltalk - but it has a lot (sometimes I think too many, sometimes not) conveniences. Parantheses and brackets are largely optional "where it makes sense". Conditionals support postfix, eg these are equivalent: if should_send?() send_mail({to: 'u@x.com'}) end send_mail to: 'u@x.com' if should_send?
- codesnik 6y agobison should be compared to https://github.com/tree-sitter/tree-sitter-ruby/blob/master/src/grammar.json https://github.com/tree-sitter/tree-sitter-ruby/blob/master/... probably?
- chrisseaton 6y agoNo 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.
- tclem 6y ago@chrisseaton you are correct, the JSON file is generated. The handwritten parts are: - https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a04adb4accb0c121f037ab59df3c3488228/grammar.js https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a0... - https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a04adb4accb0c121f037ab59df3c3488228/src/scanner.cc https://github.com/tree-sitter/tree-sitter-ruby/blob/32cd5a0... So about 2k loc. The trickiest (and most verbose) parts of the external scanner have to do with heredocs and the various ways to declare literals (strings, symbols, regexes, etc).
- dcreager 6y agoThis 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 https://github.com/whitequark/parser
- chrisseaton 6y agoI didn't mean the tree-sitter grammar was not understandable - it's very understandable - I just can't work out how to managed to find such a concise way to express grammars. Even compared to Whitequark it's 1/3 the size. What's the unique thing you do that makes it so concise? It also seems somehow to be completely declarative? How have you managed to transform Ruby parsing to be context-free? For example where's the set of what's currently a local variable so you can distinguish from method calls?
- dcreager 6y agoAhh my mistake! :-) To be fair, we're cheating a little bit because the Ruby grammar relies so heavily on an external scannar, which is just under 1,000 lines of C++: https://github.com/tree-sitter/tree-sitter-ruby/blob/master/src/scanner.cc https://github.com/tree-sitter/tree-sitter-ruby/blob/master/...
- chrisseaton 6y agoBut for example how do you parse the difference between `x = 14; x` and `y = 14; x`? In the latter case `x` is a method call, and in the former it's a local variable read. I can't see where the parser maintains a set of local variables and where it queries this set. Is it somehow done declaratively? If so that's a huge achievement I don't think that's really been done before in a parser generator. I really want to try tree-sitter for using in an actual Ruby implementation because it's so beautiful!
- dcreager 6y ago
- tclem 6y agoHey thanks! I'm one of the primary developers of this grammar along with @maxbrunsfeld. It was the driving force for supporting an external scanner and while there are still some Ruby edges cases, I'm pretty happy with how it came out. I will say we spent a lot of time on this and I read both the bison Ruby grammar and whitequark's ruby parser (which is excellent) in great detail to understand how to deal with certain parts of the language. One thing I love about tree-sitter is how both the grammar and the resulting ASTs are so readable. I can come back to this project after months of not contributing and pick up right where I left off.