Binary Trees

The structure of a simple binary tree can be shown as:

And represented by a visually notated context free grammar as:

And then a spatial parser using the grammar produces this parse tree for a more complex bt:

The first argument to the parser was the visual grammar; the second argument was the region on the screen in which visual atoms from the binary tree diagram language were spatially arranged according to the conventions of that language.

In the grammar,   " "   functions as a visual literal,   " "   matches any piece of text, and spatial searching for the next item in the target region takes place in a location determined by the last found item and the position of items in the right hand side of the rule (ie. rule used as spatial template).

The extra level of structure for leaves could be eliminated at the cost of making the grammar more complex.

And if this grammar is still too textual for you, an even more visual version has been written&drawn.

And, finally, yes, the diagram really was parsed, as can be seen below. Unfortunately, however, the traditional parse tree with labeled nodes violates the spatial integrity of the arrangement of input elements; the more concise spiderwebs will be used for the remaining examples.

Traditional tree produced from the first parse tree by a layout program which uses node labels generated during the parse and cached in property slots.

  Back to first page