Flattening ASTs (and Other Compiler Data Structures)

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

Our great sponsors
  • InfluxDB - Power Real-Time Data Analytics at Scale
  • LearnThisRepo.com - Learn 300+ open source libraries for free using AI.
  • WorkOS - The modern API for authentication & user identity.
  • c4

    C in four functions

    I was surprised to see nodes still have two pointers ("references") given that you now know that that the first pointer will always point exactly to the next node. I've see https://github.com/rswier/c4 use that. Granted it doesn't make for the most readable code, but it's even smaller and faster.

  • V7

    Embedded JavaScript engine for C/C++

    I used such a succinct AST structure to implement a JavaScript parser and interpreter for a severely memory constrained environment (embedded): V7 (https://github.com/cesanta/v7)

    We later switched to a ast->bytecode compilation step but for a while the implicit AST was directly traversed during interpretation.

  • InfluxDB

    Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  • Nim

    Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula. Its design focuses on efficiency, expressiveness, and elegance (in that order of priority).

    Same ideas are used in Nim's incremental compilation (wip) https://github.com/nim-lang/Nim/tree/devel/compiler/ic

  • packedjson

    packedjson is an alternative Nim implementation for JSON. The JSON is essentially kept as a single string in order to save memory over a more traditional tree representation.

    Also there are two JSON implementations with a flat architecture https://github.com/Araq/packedjson and https://github.com/planetis-m/packedjson2 (this one I wrote) But I agree it's a pain to write it like that.

  • packedjson2

    Efficient JSON implementation. The tree is essentially a seq of nodes. Based on planetis-m/jsonecs#8

    Also there are two JSON implementations with a flat architecture https://github.com/Araq/packedjson and https://github.com/planetis-m/packedjson2 (this one I wrote) But I agree it's a pain to write it like that.

  • lyte

    A programming language for Audulus nodes

    I'm using this technique in a compiler [1]. One thing I really like about it is that, unlike pointers, I can reuse the integer indices (`ExprRef` in the article) between arrays. So, for example, I have separate arrays for the AST and computed types, which allows the AST to be immutable. (perhaps the article already mentions this advantage, but I didn't see it in the list of advantages)

    [1] https://github.com/audulus/lyte

  • JSMN

    Jsmn is a world fastest JSON parser/tokenizer. This is the official repo replacing the old one at Bitbucket

    One more JSON implementation using this approach is https://github.com/zserge/jsmn.

  • LearnThisRepo.com

    Learn 300+ open source libraries for free using AI. LearnThisRepo lets you learn 300+ open source repos including Postgres, Langchain, VS Code, and more by chatting with them using AI!

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts