W3C home > Mailing lists > Public > w3c-sgml-wg@w3.org > December 1996

Re: clink/ilink direction (Was: anchor awareness)

From: David G. Durand <dgd@cs.bu.edu>
Date: Mon, 30 Dec 1996 12:19:41 -0500
Message-Id: <v02130508aeeda5d2d72f@[165.90.139.120]>
To: w3c-sgml-wg@www10.w3.org
At 7:13 PM 12/29/96, Joe English wrote:
>Groves are like trees in that every node with the exception
>of a unique root node has a single parent.  However, nodes
>in a grove also have a collection of named properties,
>whose values can be either "plain data" or a list of
>references to other nodes.  Nodal properties (those whose
>value is a list of nodes) are classified as either "subnode
>properties" or "reference node properties"; every node
>except for the root is a member of a subnode property of
>exactly one other node in the grove (i.e., its parent), but
>there are no restrictions on reference node properties.  If
>you consider only the subnode properties, you have a tree;
>if you consider the reference node properties as well, you
>have a directed (possibly cyclic) graph.
>
>Further, non-leaf nodes have a single distinguished subnode
>property designated as the "content property"; if you
>consider only the content properties you get the
>"principal tree" of the grove.  For example in the
>SGML grove plan, attribute nodes are subnodes of element
>nodes, but they are not part of the principal tree.

Thanks for the first clear explanation I have seen.
>David Durand wrote:
>> Ah, kind of like a parse tree. In fact, exactly like.
>
>A grove is nothing like a parse tree in the sense
>of the term with which I am familiar (a representation
>of a derivation of a string of terminals with respect to
>a grammar); they're more like an abstract syntax tree
>(i.e., a representation of the information derived from
>the parse tree) augmented with cross-references between nodes.

You are correct. I used the terminology sloppily, while wearing my
implementor hat: I think of the tree that my Yacc grammars build as a parse
tree, but it is actually an abstract syntax tree (with annotations). So a
grove is what everyone else calls an abstract syntax tree. The point about
new terminology for old concepts still holds, I think. Many ASTs in
implementations (as opposed to textbooks) are so annotated (with
cross-references).

>> My inclination agaist groves stems from:
>>    1. The complexity of groves (reflecting the complexity of full SGML parsin
>> g).
>
>The grove data structure taken by itself is really quite
>simple and elegant.  The SGML property set is horrendously
>complex, but if you only consider the "important" parts
>(e.g., ESIS plus a few extra properties that got left out)
>groves are very useful.  (Cost 2 uses a grove-like data
>structure for its internal representation, so I can attest
>to their utility.)

   But this really supports my point. I have taken most of the "use groves"
stuff to refer to the property set. Since we are defining an abstract
syntax representation, we need not constrin application data structures at
all, just what objects and relationships are available. I would advise
using standard terminology instead of new terminology so that people will
understand things. If that ends up being logically equivalent to some grove
plan, fine, but I'm not clear that groves per se offer much to the
non-HyTime/DSSSL expert, but a lot of new terminology.

   So I agree with your points, but I still don't find them convincing. All
we need is ASTs where internal nodes have labelled slots to get all the
data content of a grove. And Len and Gavin are right, that using OO
terminology is likely to make this clearer to programmers than using grove
terminology (as long as we keep the operational aspects separate).

  -- David

I am not a number. I am an undefined character.
_________________________________________
David Durand              dgd@cs.bu.edu  \  david@dynamicDiagrams.com
Boston University Computer Science        \  Sr. Analyst
http://www.cs.bu.edu/students/grads/dgd/   \  Dynamic Diagrams
--------------------------------------------\  http://dynamicDiagrams.com/
MAPA: mapping for the WWW                    \__________________________
Received on Monday, 30 December 1996 12:13:09 EST

This archive was generated by hypermail pre-2.1.9 : Wednesday, 24 September 2003 10:03:50 EDT