2
$\begingroup$

Given a tree, with some nodes annotated, such that the annotations form another tree, I'm thinking "sparse subtree" is an appropriate term for describing the latter tree as it relates to the original tree. But I'd like to check with y'all because I plan to use the term in writing for an audience that will include CS savvy folk.

If not, I think "tree formed by the annotated subset of the nodes of the tree" will work but am hoping one of y'all will suggest something snappier than that.

$\endgroup$
  • $\begingroup$ I'm not sure there is a standard term. Feel free to make up your own. $\endgroup$ – Yuval Filmus Jul 29 '18 at 16:48
  • 1
    $\begingroup$ Just relax and choose whatever name you want. $\endgroup$ – Yuval Filmus Jul 29 '18 at 17:20
  • $\begingroup$ Just be sure to explain at least once in some detail what the term means. $\endgroup$ – Sagnik Jul 30 '18 at 5:53
1
$\begingroup$

AST

This self answer defines the terms and acronyms I've made up to refer to what I asked about.1

The terms I've made up are general definitions of two kinds of tree data structure. I define them more precisely in later sections but in summary they are:

  • A Sparse Tree aka AST. A sparse subset of a tree.

  • Annotated Subset Tree aka AST. A sparse tree formed via "annotation".

Why define terms to distinguish the concepts when their acronyms eliminate the distinction? Because eliminating the distinction is the most important thing, even though defining the distinction is also important enough to warrant my question and this answer.

AST typically refers to Abstract Syntax Tree

One existing typical meaning of AST in the CS world is the specific context I had in mind when I posed my question.2

So now we have not two but three ASTs. In the section Why three ASTs?!? below I'll return to why I'm defining three distinct tree concepts that all share the same acronym.

A Sparse Tree

By A Sparse Tree3 I mean a node of a tree data structure that serves as a root, plus any "well formed"4 potentially sparse subset tree formed of branch and leaf nodes relative to that root.

My example will be A Sparse Tree formed from a parse tree.5

If source code is like this:

foo = bar # Assign bar to identifier foo

And the parse tree is like this:

TOP
  statement                   foo = bar # Assign bar to identifier foo
    assignment                foo = bar
      identifier              foo
      assignment operator     =
      identifier              bar
    end-of-line-comment       # Assign bar to identifier foo

then the following represents two of many possible sparse trees based on that single parse tree:

# A Sparse Tree:
    assignment                foo = bar
      identifier              foo
      identifier              bar

# Another Sparse Tree:
    end-of-line-comment       # Assign bar to identifier foo

Annotated Subset Tree

By Annotated Subset Tree6 I mean A Sparse Tree represented/stored by annotating a subset of the nodes of a tree.

By "annotating" I mean adding additional data to selected nodes.

Why three ASTs?!?

One abstract use case for sparse trees is forming an Abstract Syntax Tree that consists of annotations of the Parse Tree generated by a top down parser.

When the distinction between A Sparse Tree, an Annotated Subset Tree, and an Abstract Syntax Tree is moot -- which is most of the time -- just use the acronym AST without worrying about the ambiguity, because, by my definitions, it doesn't matter.7

That's why the terms I've coined share the same acronym: AST -- so they can be understood as theoretically distinct things but, for some parser implementations, the same thing in practice.

Footnotes

1 My question was originally an attempt to find out if there was already an accepted term for what I described, generically in regard to trees, without regard for Abstract Syntax Trees. Then it became documentation of that attempt and the CS exchange community's response:

I'm not sure there is a standard term. Feel free to make up your own.

Just be sure to explain at least once in some detail what the term means.

2 I deliberately didn't state this context for my question because my original goal was to find out if there was a generic CS term about such trees.

3 A google for "sparse tree" suggests a few things, most notably a new christmas tree aesthetic and an aspect of a software feature (Emacs Org mode), as well as some genuinely CSish notions, but I didn't find any matching what I've described in this answer.

4 By "well formed" I mean that each node in the sparse/subset tree contains content from, and/or pointers to, the content of other nodes, always in the direction of the tree's leaves.

5 The word "sparse" is onomatopoeically reminiscent of "parse". A "happy mnemonic accident" given that that the context for me naming these things is a sparse tree formed from a parse tree. It also reminds me of "A partridge in a pear tree" and I fantasise I will one day come up with and publish a worthy pun along those lines. :)

6 A google for "annotated subset tree" suggests a variety of CSish notions, but I didn't find any matching what I've described in this answer.

7 Of course, the usual use of the term "AST" in a CS context is an Abstract Syntax Tree. The whole point of this SO was to pick abstract terms describing a concrete approach that may be taken by parsers storing an AST. That the terms all initialise to AST, with Abstract Syntax Tree being the dominant meaning of that acronym, is, of course, deliberate, and, imo, delightful.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.