Representing an AST

rob@aimnet.com (Rob Duncan)
14 Jun 1996 15:34:33 -0400

          From comp.compilers

Related articles
Representing an AST rob@aimnet.com (1996-06-14)
Re: Representing an AST ok@cs.rmit.edu.au (1996-06-21)
| List of all articles for this month |

From: rob@aimnet.com (Rob Duncan)
Newsgroups: comp.compilers
Date: 14 Jun 1996 15:34:33 -0400
Organization: Aimnet Information Services
Keywords: analysis, question

(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.
--


Post a followup to this message

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