Re: Parse tree creation question

> I am creating my abstract syntax tree with bison. I have some rules like
> this:
>
> a: b c { $$ = gProgram = new a( $1, $2 ); } ;
> b: d { $$ = new b( $1 ); } ;
> c: e { $$ = new c( $1 ); } ;
>
> Now, if the parsing phase doesn't fail, when a gets reduced, gProgram
> is a pointer to the entire parse tree, so I can't deallocate it when I
> am done working with it. But, if the parsing phase fails for any
> reason, I can't deallocate the nodes constructed up to the momento of
> failure, since I have no pointer to them.


Basically, the answer comes down to garbage collection. To solve the
problem, you need some kind of garbage collector as you can't predict
easily when you need to deallocate objects.


So, you have two choices
a) use an existing garbage collector, either built into your
      language/compiler, or a bolt-on such as the Boehm-Weiser
      conservative collector (works well with C/C++ and yacc in
      my experience)
b) roll your own garbage collector. There are lots of ways of
      doing this. In C++ you can use `smart-pointers' to implement
      a reference counting scheme. Alternately, you can use a `pool'
      scheme where you keep track of all the objects allocated and
      periodically sweep the pool, freeing unneeded objects (mark-sweep
      collection) or copy the relevant objects to a new pool and free
      the entire old pool (copy collection).


(a) is certainly the easier choice, but (b) does have some advantages.
You can tune the garbage collector to the application (in this case,
a compiler), and trigger garbage collection at opportune points when
the total live data is small, which can significantly reduce the overhead.
Depending on your compiler, however, this overhead may be a tiny
proportion of the overall time.


Chris Dodd
chrisd@reservoir.com

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