Representing an AST

(I had posted this to comp.lang.prolog, but someone suggested that I
should post it here too.)


I'd be very grateful if someone could give me some advice on
representing an abstract syntax tree for a fairly typical block
structured programming language using Prolog terms.


Is it better to represent each node of the AST with a separate fact,
with arguments referring to labelled children? Or is it better to
construct a single large fact for the whole tree, with the arguments
directly referring to the children?


I.e., what are the consequences of using different representations such
as:


1. node(Label, Type, OtherInfoForThisNode, ListOfChildrenLabels).
2. node_foo(Label, OtherInfoForThisNode, Child1Label, Child2Label).
3. node_foo(LabelForThisFoo, InfoForThisFooNode,
node_baz(LabelForThisBaz, InfoForThisBazNode,
node_iki(LabelForThisIki, ...
...
node_grum(LabelForThisGrum, ...
      ).


There will be thousands of nodes in the parse tree sometimes, and there
are tens of different types of nodes. Performance is an issue. I want
to represent the tree in a way that makes discovering information about
it straightforward and efficient. I'm sure there are standard
techniques for doing this. Where can I look for references and
examples?


Thanks in advance,


Rob.
--

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