Re: How to store an AST

Nils M Holm <>
16 May 1999 15:23:59 -0400

          From comp.compilers

Related articles
How to store an AST (Salvador V. Cavadini) (1999-04-30)
Re: How to store an AST (Steve Mading) (1999-05-07)
Re: How to store an AST (Dave Hanson) (1999-05-07)
Re: How to store an AST (Mike Harrison) (1999-05-09)
Re: How to store an AST (Nils M Holm) (1999-05-16)
Re: How to store an AST (Willy Jacobs) (1999-05-16)
| List of all articles for this month |

From: Nils M Holm <>
Newsgroups: comp.compilers
Date: 16 May 1999 15:23:59 -0400
Organization: Compilers Central
Keywords: design

Steve Mading <> wrote:
> Salvador V. Cavadini <> wrote:
> : Hi,
> : I'm programming a front-end for a tool and I need to store in disk the
> : AST produced by the parser. The rest of the tool will randomly access
> : the AST's nodes. I would be greatful if someone can recommend an
> : efficient way for store the AST.
> For the most part, you can just dump out the structures as-is with
> binary read/write but you need to be careful of pointers. Any time
> you have some data that is pointed at by a pointer somewhere, you
> should assume that the data will be in a different memory location
> when you reload it later. This invalidates the pointers that pointed
> at it.

Maybe, this solution is too simple, but why not put all the nodes of the
AST in a big flat array and use offsets into the array instead of pointers.
This way, the entire AST can be read and written using simple block
read/write operations.

I see no major disadvantages compared to 'real' pointers. When building an
AST, nodes in the array can be allocated linearly since usually no nodes
will be deleted during the construction phase.
When performing other operations on trees/graphs, like optimization tasks,
a simple garbage collector or a malloc()-style package which operates on
arrays (instead of the system 'heap') may be helpful.

This method works fine in many of my programs, but admittedly, I am
rather a minimalist...


Nils M Holm <> [Please use Reply-To:] -- The home of the T3X compiler

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.