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

dgd@cs.bu.edu (David G. Durand) wrote:
> W. Eliot Kimber:
> >David G. Durand:
> >>    A "grove" is just a new name for what everyone else in the world calls
> >>a "parse tree".
> >
> >Not exactly correct: groves are a new name for what everyone else in the
> >world calls a direct graph data structure. [...]
>
> trees are directed graphs. Are you saying that groves can include cyles of
> nodes (ie node that are their own ancestors), or multiple inheritance
> (directed _acyclic graphs_)?

Sort of.

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.

> >3. Provides a standardized abstraction mechanism divorced from the
> >   implementation issues.
> 
> 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.

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


--Joe English

  jenglish@crl.com

Received on Sunday, 29 December 1996 22:13:46 UTC