1
$\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
  • $\begingroup$ I can now just quote or point to this SO question via your comment as the detailed explanation. Job done. Thank you @sagnik and Yuval. :) $\endgroup$ – raiph Jul 30 '18 at 10:23
0
$\begingroup$

This answer documents the term (actually two) I've made up to refer to what I asked about.1

The application context is transformation of a tree data structure called a parse tree (aka "concrete syntax tree") as part of creating an interpreter, compiler, or transpiler.2

Definition of "sparse tree"

A "sparse tree" refers to the root or top node of a tree data structure plus any subset of the rest of its nodes.3

The name "sparse tree" is deliberately close in English to "parse tree" and this will be the only example I illustrate below.

If source code is like this:

foo = bar # assign bar to foo

And the parse tree is like this:

TOP
  statement
    assignment
      identifier
      assignment operator
      identifier
    end-of-line-comment

then the following could both represent sparse trees based on that parse tree:

TOP
    assignment
      identifier
      identifier

TOP
    end-of-line-comment

Definition of "annotated subset tree"

An "annotated subset tree" is a sparse tree formed by annotating a subset of the nodes of a parse tree such that each annotation contains content and/or pointers to the annotations of other nodes in the direction of the tree's leaves.4

One of the primary uses for forming an annotation-based sparse tree is to store the abstract syntax tree corresponding to the parse tree (aka "concrete syntax tree"). That's why I've coined a term that shares the same acronym AST.

When the distinction between sparse tree, annotation subset tree, and abstract syntax tree is moot, which is most of the time, just use the acronym AST.

Footnotes

1 My question was originally an attempt to find out if there was already an accepted term for what I described. 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 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.

$\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.