Strange Loop Conference
4 HN recommenders · recommended in 5 months, 2018–2024
38:38 · 63K views · Oct 14, 2018
Max Brunsfeld introduces Tree-sitter, a parsing system for developer tools that offers incremental parsing and robust error recovery through a uniform C API. The talk explains the design, based on LR extended to GLR parsing.
HN points to it as the best explanation of tree-sitter's design choices and as an accessible introduction to parser generators.
5 comments from Hacker News
Absolutely agreed, and copying from a comment I wrote last year: I think the fact that tree-sitter is dependency-free is worth highlighting. For context, some of my teammates maintain the OCaml tree-sitter bindings and often contribute to grammars as part of our work on Semgrep (Semgrep uses tree-sitter for searching code and parsing queries that are code snippets themselves into AST matchers). Often when writing a linter, you need to bring along the runtime of the language you're targeting. E.g., in python if you're writing a parser using the builtin `ast` module, you need to match the language version & features. So you can't parse Python 3 code with Pylint running on Python 2.7, for instance. This ends up being more obnoxious than you'd think at first, especially if you're targeting multiple languages. Before tree-sitter, using a language's built-in AST tooling was often the best approach because it is guaranteed to keep up with the latest syntax. IMO the genius of tree-sitter is that it's made it way easier than with traditional grammars to keep the language parsers updated. Highly recommend Max Brunsfield's strange loop talk if you want to learn more about the design choices behind tree-sitter: this video And this has resulted in a bunch of new tools built off on tree-sitter, off the top of my head in addition to difftastic: neovim, Zed, Semgrep, and Github code search!
It's great to see more tools adopting tree-sitter [1]. Having a (fast) single tool that can accurately parse most commonly used programming languages is incredibly useful, but it requires the maintenance of dozens of grammars, which is difficult without a large community effort. Hopefully increased adoption means more accurate parsers and support for even more languages. Tree-sitter powers syntax highlighting on GitHub.com and (soon) neovim and OniVim 2. Hopefully regex-based syntax highlighting is a thing of the past soon. If you haven't seen the Strange Loop conference talk on tree-sitter [2] yet, it's worth a watch. I think a Prettier-like code formatter using tree-sitter would be cool, both in terms of potentially broader language support and native performance. [1]: [LINK] [2]: this video
I also enjoyed the Treesitter talk from 5 years ago by Max Brunsfeld this video I'm currently building a query language whose grammar is very much inspired by Github's search syntax. I'm using Lezer, which is a GLR like Treesitter, so this talk learned me some parser generators (I've no formal CS education). Here's my grammar, a playground, and an example search query if anyone wants to play with it [LINK] [LINK] -(a) spider-man -a b -c -"(quote\"d) str" OR "l o l" OR a b c ((a "c") b) tag:what -deck:"x y" I just converted the syntax tree to an abstract syntax tree so I can do De Morgan's law transformations. Literally the only time in my professional life where I feel like I'm solving a leetcode-style problem.
For a really nice solution to the error message problem, see this recent strangeloop talk: this video Basically it uses the parse tree disambiguation from the GLR parser to look for the most likely mistake the user made - it's very clever.
Parsing (use of rather than theory) matters as it affects my work. So I followed up. See this video Tree sitter is based on LR parsing (see 23:30 in above video) extended to GLR parsing (see 38:30). I've had enough of fools on HN posting unverified crap to make themselves feel cool and knowledgeable (and don't kid yourself that you helped me find the right answer by posting the wrong one). Time I withdrew. Goodbye HN.