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.
Why Hacker News points people here: HN points to it as the best explanation of tree-sitter's design choices and as an accessible introduction to parser generators.
“Highly recommend Max Brunsfield's strange loop talk if you want to learn more about the design choices behind tree-sitter”HN comment, 2024
“Highly recommend Max Brunsfield's strange loop talk if you want to learn more about the design choices behind tree-sitter”
Explains design choices behind tree-sitter
Full comment
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!
RecommendslemmingNov 2018
“For a really nice solution to the error message problem, see this recent strangeloop talk”
Clever GLR-based approach to better parser error messages
Full comment
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.
RecommendsrtsaoOct 2020
“If you haven't seen the Strange Loop conference talk on tree-sitter [2] yet, it's worth a watch.”
Talk on tree-sitter's design and goals
Full comment
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
RecommendsAlexErrantDec 2023
“I also enjoyed the Treesitter talk from 5 years ago by Max Brunsfeld”
Taught commenter about parser generators without CS background
Full comment
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 linklink -(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.
Cites itthrowaway_pdp09Dec 2020
“Tree sitter is based on LR parsing (see 23:30 in above video) extended to GLR parsing (see 38:30).”
Confirms tree-sitter uses LR extended to GLR
Full comment
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.
