Data structures for syntax trees

Data structures for syntax trees

[Tero Koskinen]

Hi,

I am looking for advice on what kind of data structures to use for
abstract syntax trees. At the moment, I want present JSON language
as a tree: http://www.json.org/

The requirement is that the data structure works with GNAT GPL
and Janus/Ada. So far, the Janus/Ada part has been giving me trouble.
(With GNAT everything works.)

I have tried to avoid access types and create a tree structure
using tagged types. However, Janus/Ada has some bugs with either
with class-wide types or parameterized types containing controlled
types and passing/copying them around causes crashes when the produced
executable is run. RR Software is aware of the issue, but hasn't been
able to give estimate when the issue will be fixed. So, I am looking for
alternatives.

My current (crashing[1]) attempt is available at
 http://bitbucket.org/tkoskine/jdaughter/src/950f001bf2aa/src/json-data.ads
 http://bitbucket.org/tkoskine/jdaughter/src/950f001bf2aa/src/json-parser.adb

(Basically I have bunch of tagged types derived from JSON_Root_Type
and a few container types, which take JSON_Root_Type'Class objects.)

RR Software told me that using access types should work, but I would
avoid that as long as possible.

Is there still some nice way to avoid access types (in the public API
at least) while also not using class-wide or controlled types?

And what kind of data structures others have used to present
syntax trees?

-Tero

[1] crash usually happens in line 134 or 146 of json-data.adb

Re: Data structures for syntax trees

[Dmitry A. Kazakov]

On Mon, 1 Feb 2010 21:34:41 +0200, Tero Koskinen wrote:

> And what kind of data structures others have used to present
> syntax trees?

I am using access types to non-controlled class-wide objects allocated in
an arena pool. A syntax tree is usually removed as a whole.

   Tree_Pool : Stack_Storage.Pool (2048, 128);

   type Node is abstract tagged limited null record;
   function Image (Item : Node) return String is abstract;
   type Node_Ptr is access Node'Class;
   for Node_Ptr'Storage_Pool use Tree_Pool;

   type Term is abstract new Node with record
      Location : Parsers.Multiline_Source.Location;
   end record;

   type Expression (Count : Positive) is new Node with record
      Operation : Operations;
      Location  : Parsers.Multiline_Source.Location;
      Operands  : Argument_List (1..Count);
   end record;

And so on. The example can be found here:

http://www.dmitry-kazakov.de/ada/components.htm#12.9

I cannot tell if that works with Janus, I don't have the compiler.

Alternatively I would use a directed graph. That again would be access
types to the arena pool of the graph nodes, parent-child relations
maintained implicitly by the pool.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de