Re: How to store an AST

Steve Mading <madings@baladi.nmrfam.wisc.edu> wrote:
> Salvador V. Cavadini <salvador@ucseii.edu.ar> 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...


Bye,
nmh.


--
Nils M Holm <nmh@dialup.nacamar.de> [Please use Reply-To:]
http://www.homepages.de/home/nmh/ -- The home of the T3X compiler

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