miniblog.

← Back to all posts
May 4, 2023 at 06:52
On storing ASTs in flat arrays for performance, and the relationship with bytecode interpreters:
Flattening ASTs (and Other Compiler Data Structures)
Flattening ASTs (and Other Compiler Data Structures)
This is an introduction to data structure flattening, a special case of arena allocation that is a good fit for programming language implementations. We build a simple interpreter twice, the normal way and the flat way, and show that some fairly mechanical code changes can give you a 2.4× speedup.

Related Posts

Sep 16, 2024 at 15:24
ASTs typically discard comments, and that's usually what you want. The only time (AFAICS) that preserving comments is useful is for writing a code formatter. Could you write a formatter in terms of a list of lexemes? A CST is a non-trivial bit of code for one use case.
Jul 2, 2024 at 15:18
Counter-intuitively, if you're writing a parser for a programming language, you need it to be a total function. As soon as you build IDE tooling, you need ASTs from invalid or incomplete input. The parser should return (Ast, List<Error>) rather than Result<Ast, Error>.
Jul 24, 2022 at 05:45
Difftastic is effectively computing the "tree edit distance" between two ASTs, and there's a bunch of papers on this topic. Literature review is hard though: sometimes a paper takes a while to digest, only to realise that they're solving a slightly different problem.