I'm looking for a C/C++ library for handling Abstract Syntax Trees that can be generated after recognizing a language in Antlr or yacc/bison. Given that in software or query optimization you need to rewrite the tree into something else (expression simplification or expansion: e.g., pushing the filter/selection predicate towards the leaves), I need to greately allocate and deallocate the memory: therefore, given that I need to visit the AST frequently and that I do not want to fragment primary memory too much. Plus, the visit of the AST should be conducted in a pattern matching fashion, as in functional programming languages. If my requirements would have stopped here, I know I could have used Mach7 by Stroustroup but, alas, I need to do something more than that.
I would like that all the nodes of the tree would have been allocated and deallocated in a contiguous set of memory. By doing so, I could also sort the AST in lexicographical order, so to minimize the jump time. In fact, graph libraries do not allow such kind of sorting under their data representation, and so I was forced to try and implement something from scratch.
Thanks for your time.