"Tree-sitter - a new parsing system for programming tools" by Max Brunsfeld
Why Hacker News recommends it
HN points to it as the best explanation of tree-sitter's design choices and as an accessible introduction to parser generators.
What it is
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.
Recommended by 4 HN commenters across 4 different months, 2018 to 2024.
What Hacker News said
Strong rec ievans · 2024-03 · on “Difftastic, a structural diff tool that understands syntax”
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 insta
Recommends lemming · 2018-11 · on “Owl: Parser generator for visibly pushdown languages”
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.
Recommends rtsao · 2020-10 · on “Introducing Semgrep and r2c”
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, b
Recommends AlexErrant · 2023-12 · on “Lessons from building GitHub code search [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 leetco
Cites throwaway_pdp09 · 2020-12 · on “Advanced Compilers: Self-Guided Online Course”
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.