Representing an AST (Rob Duncan)
14 Jun 1996 15:34:33 -0400

          From comp.compilers

Related articles
Representing an AST (1996-06-14)
Re: Representing an AST (1996-06-21)
| List of all articles for this month |

From: (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

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

Thanks in advance,


Post a followup to this message

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