14 ms·
Tree-sitter: an incremental parsing system for programming tools
- ducktective 6y agoIs this the same thing neovim uses for syntax highlighting? Is there a chance for it getting integrated to vim? Last I checked vim used a regex method which was slow and faulty.
- pcr910303 6y agoTo 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 https://twitter.com/simonbs/status/1352697855845273600 [1]: https://twitter.com/simonbs/status/1362492842141171720?s=21 https://twitter.com/simonbs/status/1362492842141171720?s=21
- ducktective 6y agoYeah but I don't think LSP specs contain syntax-highlighting or semantic highlighting.
- deleted 6y ago[deleted]
- orra 6y agoLSP supports semantic highlighting: https://microsoft.github.io/language-server-protocol/specification#textDocument_semanticTokens https://microsoft.github.io/language-server-protocol/specifi... Though AIUI the basic syntax highlighting is done by the editor (e.g. VSCode uses Textmate grammar support).
- picardythird 6y agoFYI there is tree-sitter.el for Emacs.
- ACosmicDust 6y agoEmacs does have a package to use tree-sitter [0]. I think emacs-lsp is aware of this highlighting backend and performs pretty well. (semantic highlighting is pretty slow for C++ with font-lock, with tree-sitter it's a breeze :)) [0]: https://github.com/ubolonton/emacs-tree-sitter https://github.com/ubolonton/emacs-tree-sitter
- pdimitar 6y agoWait what? You mean to tell me that Emacs LSP already uses tree-sitter?
- guerrilla 6y agoIs the use case for this mainly IDEs or is it intended to replace traditional lexer and parser generators too?
- patrec 6y agoI 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 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).
- guerrilla 6y agoAh I see, so the reparation isn't avoidable for now? That doesn't seem very appropraite for compilers then.
- patrec 6y agoWhy would it not be appropriate? The only annoyance I see is that currently you will have to generate a good error message from it yourself, but a first pass at the problem shouldn't be too onerous.
- guerrilla 6y agoOk, I misunderstood. I thought it repaired without error sometimes but I see that you were clear that that isn't the case.
- dcreager 6y agoWe are also using this to power a lot of the program analysis features on github.com. We use it to generate the symbol list for Code Navigation, as an example, and are starting to look at extracting more semantic information about some languages using tree-sitter parse trees as intermediaries.
- srcreigh 6y agoTree 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 https://github.com/ubolonton/emacs-tree-sitter [2]: https://ubolonton.github.io/emacs-tree-sitter/ https://ubolonton.github.io/emacs-tree-sitter/ [3]: https://github.com/ubolonton/emacs-tree-sitter/issues/66#issuecomment-778692779 https://github.com/ubolonton/emacs-tree-sitter/issues/66#iss...
- lalaithion 6y agoMaybe I can finally have this syntax highlighting style: https://youtu.be/b0EF0VTs9Dc?t=900 https://youtu.be/b0EF0VTs9Dc?t=900
- srcreigh 6y agoThere is an emacs package for this (maybe beta). I can't remember the name of it and Google is failing me. EDIT: finally found it https://github.com/alphapapa/prism.el https://github.com/alphapapa/prism.el
- jackcviers3 6y agoRainbow delimiters mode kind of does this, but doesn't maintain the scope color of referenced variables.
- brundolf 6y ago
- chrisseaton 6y agoTree-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.
- 6y ago
- Grimm1 6y agoI 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.
- brundolf 6y agoHere's what it looks like to call it from Rust: https://github.com/tree-sitter/tree-sitter/tree/master/lib/binding_rust https://github.com/tree-sitter/tree-sitter/tree/master/lib/b... Seems like this would make it much easier to bootstrap a performant language-server. Very cool; maybe that will be my next project.
- dcreager 6y agoWe also have several of the language grammars published as crates: https://crates.io/search?q=tree-sitter https://crates.io/search?q=tree-sitter (And doing the same for other grammars is a fairly painless process.) So if you're writing a tool for a single language (like a language server), it should be as easy as adding tree-sitter and tree-sitter-blah to your cargo manifest.
- brundolf 6y agoAwesome! Though my thinking was that it would have an especially large impact for languages that aren't popular enough to have their own LSP yet; you no longer have to be an expert in writing interactive compilers to set up a respectable LSP for a niche language, or even a home-grown one
- dcreager 6y agoYes! This is a great point. It's similar to what I mentioned over on this thread [1] about how we're working on a more precise version of Code Navigation based on tree-sitter. The tl;dr is that you'd write something like tree-sitter queries [2], just like you do for the current fuzzy Code Nav, but the query DSL would be a bit more sophisticated, allowing you to specify the actual name resolution rules of your language. One of the things we're using to test this is an LSP shim that lets us test our rules in VS Code (or any other LSP-compliant editor). [1] https://news.ycombinator.com/item?id=26227476 https://news.ycombinator.com/item?id=26227476 [2] https://tree-sitter.github.io/tree-sitter/using-parsers#pattern-matching-with-queries https://tree-sitter.github.io/tree-sitter/using-parsers#patt...
- ahelwer 6y agoI 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.
- maxbrunsfeld 6y agoHey, Tree-sitter author here. Thanks for posting! Let me know if you have questions about the project.
- yig 6y agoAre there any plans to support modifying the grammar on the fly or without recompiling?
- maxbrunsfeld 6y agoOne day, I would love to generalize the web-based playground so that you could edit the grammars. But it's complicated, because we use C as our output language, so you would always need to recompile the C after changing the grammar. So, I would say that it's not on our near-term roadmap.
- dcreager 6y agoI don't think you can do this without recompiling, since the grammars get translated into C code before use. But the built-in command line tools (‘tree-sitter parse’, etc) all support a mode where they will detect local changes to a checked-out grammar definition, and recompile on the fly if needed. (This happens each time the CLI program is started up; it doesn't happen during a long-running process.)
- sitkack 6y agoThe obvious answer is to embed TCC or another C compiler and either generate a dynamic library or generate wasm and load it directly into the process. exec_wasm(generate_wasm(generate_c(grammar))) Now if you can make that whole fn chain incremental, then a delta_grammar -> delta_c -> delta_wasm -> delta_recomputed_wasm_call stack, this will propagate deltas down to exec_wasm and you could dynamically execute the generated code as the grammar changes.
- anaerobicover 6y agoI've done two grammars for my own use in the last few months (well, one isn't quite complete yet) and it's been quite an enjoyable (learning) experience. Thanks for sharing this tool!
- amelius 6y agoNext steps: incrementally resolve symbols and type-check?
- dcreager 6y agoWe're currently working on a more precise version of the Code Nav that's shipped on github.com, which is very similar in spirit to this!
- The_rationalist 6y agoHi, can you consider adding Kotlin to the list of supported languages? Since the feature launched there is now a Kotlin tree sitter implementation https://github.com/fwcd/tree-sitter-kotlin https://github.com/fwcd/tree-sitter-kotlin (but maybe that it needs some improvments)
- dcreager 6y agoThat’s great, thanks for the link to the grammar repo! I can’t commit to a specific timeline but I’ll definitely put this on the list.
- The_rationalist 6y agoThanks, that would be really great :)
- himujjal 6y agoWrote tree-sitter-svelte. Was a good experience. I am also writing a programming language of my own similar to TypeScript and I am using tree-sitter for the same. Its a delight to work with it. Removes a lot of the worries.
- alissasobo 6y agoYou can watch a good Strangeloop presentation on Tree Sitter. https://www.youtube.com/watch?v=Jes3bD6P0To https://www.youtube.com/watch?v=Jes3bD6P0To
- wiradikusuma 6y agoWhile we're in this discussion: Say I want to implement "SQL" for my app (if you've used Jira, I want to make my own JQL). Is this the tool for that? I'm looking for something much simpler than ANTLR.
- nojvek 6y agoShould be able to create your own grammar.js, it’s actually much simpler than ANTLR.
- ritter2a 6y agoI tried to use this to ease the front end work load of students in a compiler project (building a C compiler) for a University course, so that the project could be focused on the more interesting middle and back end parts of the compiler. However, reported bugs in the C grammar that saw no activity at all [1] made this impossible. From this small sample of experiences, I was left with the impression that Tree Sitter is great for things like syntax highlighting, where wrong results are annoying but not dramatic, but not so suitable for tools that need a really correct syntax tree. --- [1] https://github.com/tree-sitter/tree-sitter-c/issues/51 https://github.com/tree-sitter/tree-sitter-c/issues/51
- dcreager 6y agoHi there! You're right that the C grammar in particular is one that could use some love. C is not one of the languages that we're syntax highlighting with tree-sitter yet, nor is it one of the languages that we support Code Navigation for. That means that my team has had to prioritize their work in other places, and no community members have stepped up to take over or help out with maintenance of the C grammar. Not a satisfying answer, I realize, but an honest one.
- drewdennison 6y agoWe've been using tree-sitter for Semgrep and it's nothing short of incredible. Amazing work by Max and team.
- dcreager 6y agoWe really appreciate the contributions you all have sent back to tree-sitter and the various language grammars, too!
- Annili 6y agoI'm curious to see if Tree-sitter can be used to provide fast and rich code navigation. I was able to implement simple goto definition/references [1], not sure if it can be used for more advanced navigation features in a language-agnostic way. If you're interested, GitHub is already using it [2] for that purpose and Sourcegraph is experimenting it [3] [1] https://github.com/alidn/lsif-os https://github.com/alidn/lsif-os [2] https://github.com/github/semantic https://github.com/github/semantic [3] https://github.com/sourcegraph/sourcegraph/issues/17378 https://github.com/sourcegraph/sourcegraph/issues/17378
- maxbrunsfeld 6y agoAt GitHub, we're in the process of building a more precise code navigation system on top of Tree-sitter, that models language-specific name-resolution rules in detail. Our currently-available code navigation system also uses Tree-sitter, but it is pretty simple; it just matches up references and definitions by their name.
- dang 6y agoIf curious, past threads: Tree-sitter: new incremental parsing system for programming tools (2018) [video] - https://news.ycombinator.com/item?id=21675113 https://news.ycombinator.com/item?id=21675113 - Dec 2019 (28 comments) Tree-sitter – a new parsing system for programming tools [video] - https://news.ycombinator.com/item?id=18213022 https://news.ycombinator.com/item?id=18213022 - Oct 2018 (25 comments) Others?
- maxbrunsfeld 6y agoOne more that I know of: Atom understands your code better than ever before - https://news.ycombinator.com/item?id=18349013 https://news.ycombinator.com/item?id=18349013 - Oct 2018
- efritz 6y agoI'm an engineer on the code intelligence team at Sourcegraph. We've been busy building out true precise code intelligence/navigation support, but we also have a mode for zero-configuration code navigation based on text search, universal-ctags, and hand-rolled regular expressions (which works surprisingly well!). Tree-sitter would definitely give better results than our current ctags-based approach. It's been catching our attention more and more lately, and we have plans to use it to upgrade our out-of-the-box, instant code navigation experience. It's not the exact right fit for our primary goals though, since it's designed around being extremely fast while editing and robust against errors. Sourcegraph is only used for navigating committed code, so we're leveraging formats like LSIF to generate complete semantic graphs of codebases and their entire dependency tree. That'll enable a lot of features that are out of reach for tree-sitter, but is a lot harder to get working out of the box and it's a much bigger technical investment. It's very interesting to see the topological space that houses these solutions fill out. Every tool has its own set of unique trade-offs and fall somewhere on these spectrums: - fast vs slow - precise vs imprecise - zero-configuration vs configuration required We've visited a few islands in this space but still very curious to see what other islands can be discovered. We're especially excited about tools and formats like tree-sitter and LSIF around which a large and supportive community can grow so that all the products we love and rely on as developers can all make forward progress.
- gugagore 6y agoCould you compare Sourcegraph to something like Moose, FAMIX, GToolkit? https://github.com/moosetechnology/Moose https://github.com/moosetechnology/Moose
- muglug 6y agoI wish there was a more universal format for parsers, but I just don't think there enough people who know their stuff. Take PHP, a language that a lot of people use: the tree-sitter-php extension doesn't support features added in 2019, let alone features added towards the end of 2020. If you want an up-to-date PHP parser, there's really only one open-source parser[0] that's accurate enough to be used on PHP codebases old and new, and it's written in PHP. Then if you want to parse in a robust fashion you have to adopt a number of hacks to get everything working. I hadn't encountered LSIF before – can GitHub be configured to use those maps? [0] https://github.com/nikic/PHP-Parser https://github.com/nikic/PHP-Parser
- The_rationalist 6y agoAre there any benchmarck available versus TextMate regexes?
- The_rationalist 6y agoHere is the "tracking issue" for JetBrains IDEs https://youtrack.jetbrains.com/issue/KT-45087 https://youtrack.jetbrains.com/issue/KT-45087 Upvote the issue if you wanna bump the priority
- xvilka 6y agoSo far it's the amazing tool and we are happy to use it in our projects. The only two complaints I have is the dependency on JavaScript[1] and missing Rust runtime option[2]. [1] https://github.com/tree-sitter/tree-sitter/issues/465 https://github.com/tree-sitter/tree-sitter/issues/465 [2] https://github.com/tree-sitter/tree-sitter/issues/465 https://github.com/tree-sitter/tree-sitter/issues/465
- stelf 6y agoWhere is the SQL parser? Any specific reason why is it missing (not even started)?
- dcreager 6y agoMy team is only writing tree-sitter parsers as part of working on GitHub developer productivity features like Code Navigation. So the short version is that we (i.e., my team at GitHub) haven't written a tree-sitter parser for SQL because we haven't targeted SQL for Code Nav support yet. That said, this is exactly why we've released tree-sitter as an open-source project. That way there's no need for anyone to be blocked on my team finding the time to work on an SQL parser. Most extant tree-sitter parsers [1] have been developed by external language communities, and not by the core tree-sitter maintainers. (Also note that SQL is a particularly wrinkly language, since there are so many different dialects. Are you looking for an ANSI SQL parser? A MySQL SQL parser? One that covers all of them to some degree?) [1] https://tree-sitter.github.io/tree-sitter/#available-parsers https://tree-sitter.github.io/tree-sitter/#available-parsers
- sidntrivedi 6y agoDoes GitHub currently use tree-sitter for syntax highlighting? If yes, are the libraries open-source? Thanks :)
- dcreager 6y ago> Does GitHub currently use tree-sitter for syntax highlighting? For some languages, yes. https://news.ycombinator.com/item?id=26227214 https://news.ycombinator.com/item?id=26227214 > If yes, are the libraries open-source? They are! tree-sitter itself is open-source [1], as are all of the language parsers we've listed on the homepage [2]. The syntax highlighting support is documented here [3]. [1] https://github.com/tree-sitter/tree-sitter https://github.com/tree-sitter/tree-sitter [2] https://tree-sitter.github.io/tree-sitter/#available-parsers https://tree-sitter.github.io/tree-sitter/#available-parsers [3] https://tree-sitter.github.io/tree-sitter/syntax-highlighting https://tree-sitter.github.io/tree-sitter/syntax-highlightin...
- nojvek 6y agoThis is really cool, I 100% agree that as programmers we’re editing and thinking in terms of ASTs. It just happens that text is a high density way to represent those ASTs. I’m going to play with this and see if I can make a generic language server for vscode that works across languages. Unless someone has already done that. What would be really cool is that tree-sitter (or a sister package) that provides incremental formatting primitives across languages. The closest language agnostic formatter that comes to mind is prettier.js with its extensions. incremental parser —> language server -> formatter across languages would be super rad.
- erezsh 6y agoI tried looking through the docs, and couldn't find any mention of which algorithm you are using. It seems like some LR, grammar, but which kind? LALR? GLR? It seems like a very important bit of information, that's suspiciously missing.
- asqueella 6y agohttps://tree-sitter.github.io/tree-sitter/creating-parsers#writing-the-grammar https://tree-sitter.github.io/tree-sitter/creating-parsers#w... mentions it’s based on GLR.
- maxbrunsfeld 6y agoIt generates LR(1) parsers, and can use GLR on an opt-in basis, for handling specific conflicts.