File ChangingTree.html    Author McKeeman    Copyright © 2007    index

Preliminaries

In MATLAB, in the xcom directory, type (or cut and paste from here to the MATALAB command line).

>> help Tree.m
>> xcom -treeTrace -treeDump x:=1
>> addpath tests trials
>> testTree
>> tryTree

>> load cfg cfg               % prepare to run Parser standalone
>> EOL = 10;                  % ASCII newline
>> lx = Lexer(cfg, ['x:=1;' EOL 'y:=x']);
>> pr = Parser(lxtr.dump();
>> tr = Tree(pr)
>> tr.dump()

Read the general description of the Syntax Tree.

But, Why?

The syntax tree building code should never have to be changed so long as using read-only syntax trees is considered sufficient. If, on the other hand, one wants abstract syntax trees, or writable trees, then changes are required.

The Arena Implementation

Nodes point to nodes, thus some kind of pointer mechanism must exist. In the case of xcom, the syntax tree is arena-allocated.

Trees are built strictly depth-first. The nodes can have any width. The descendents of a node are either internal nodes, or leaves. The leaves contain tokens. The tree-walker could consult the CFG to find out which descendents are leaves, and the width of the node, but in xcom the information is contained within the tree node itself. The first entry in the node is the rule name (a small integer). The second entry contains a pattern of 2-bit values. Two of the 4 possibilities are NODE and LEAF. The pattern ends when a two-bit zero (NONE) is encountered in the pattern. The details are documented in the source file Tree.m.