Flattening ASTs (and Other Compiler Data Structures)

• c4

  11 9,212 0.0 C

  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

  3 1,401 1.8 C

  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.

• WorkOS

  workos.com sponsored

  The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  

• Nim

  347 16,060 9.9 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

  1 66 10.0 Nim

  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.

• jsonpak

  2 19 8.4 Nim

  Packed ASTs for compact and efficient JSON representation, with JSON Pointer, JSON Patch support.

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

  1 31 8.5 Rust

  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

  14 3,553 0.0 C

  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.

• InfluxDB

  www.influxdata.com sponsored

  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.

  

Suggest a related project