void traverse(tree,Ntype,act)
ANY firstnode(tree,Ntype,ptr2tranum)
ANY nextnode(tranum)
ANY nthnode(tree,Ntype,nth,ptr2total)
ANY *nodearray(tree,Ntype,ptr2len)
FORALL(var,TYPE,tree,Ntype) LOOP ... ENDLOOP
Note: If the D option (see below) is used, then an extra
depth parameter must be added to the end of the parameter
list of the FORALL macro and all the functions except
nextnode.
Parameter declarations:
These components of the run-time library provide a variety of powerful parse tree traversal mechanisms. The components traverse the portion of the parse tree that is rooted at tree and search for all nodes of type Ntype. Two special values for Ntype may be used: Any, which indicates that all nodes are of interest, and Token, which indicates that all the token (i.e., leaf) nodes are of interest.
traverse is a routine that traverses tree and calls the parameter routine act at every node of type Ntype that is found, passing that node to act as its argument. The act routine must have a single, parse tree node, parameter.
The firstnode and nextnode functions provide more controlled traversals through trees. Instead of calling an action at each node, these routines return the selected nodes one at a
time. firstnode sets up the traversal specified by tree and Ntype and then returns the first node found. firstnode also assigns a unique number to the traversal and sets the ptr2tranum argument to point to this number. Each subsequent call to nextnode that specifies this traversal number will return the next node found in this traverse. With these two routines it is possible to have any number of concurrent traversals. The forall template construct (see FORALL(4) ) and the FORALL macro (see below) are implemented with these two functions.
The nthnode function provides another level of flexibility. nthnode returns the nth-node (specified by parameter nth) from the traversal specified by tree and Ntype. nthnode is more efficient than firstnode and nextnode when a single node must be found. nthnode also sets the integer pointed to by ptr2total to the total number of nodes of type Ntype in the traversal. If there are no such nodes then nthnode returns NULL. If ptr2total is NULL then no assignment to the integer is made.
The function nodearray traverses the tree specificed by tree and stores all nodes of type Ntype into an array of nodes. One extra element is added to the end of the array with the value NULL. nodearray also sets the integer pointed to by ptr2len to the number of nodes in the array. If ptr2len is NULL then no assignment to the integer is made.
The FORALL macro provides a convenient way to construct iteration loops that traverse parse trees. The macro call to FORALL(var,NTYPE,tree,Ntype) LOOP ... ENDLOOP is translated into C code roughly as follows:
{ NTYPE var; /* declare local loop variable */
int _tranum; /* and traversal number */
for (var = (NTYPE)firstnode(tree,Ntype,&_tranum);
var != NULL; var = (NTYPE)nextnode(_tranum))
{ ... }
}
On each iteration of the loop, the local variable var is
assigned to the next node of type Ntype in the traverse.
The name of the FORALL macro and the names of all the functions except nextnode may begin with any combination of the four LDRB traversal option characters. The individual letters specify a change to the default traversal rules. L traverse a list of nodes (rather than only a tree) D traverse only to a certain depth (rather than to the full depth) R traverse from right-to-left (rather than left-to-right) B traverse bottom-up (rather than-top down)
If more than one option character precedes a name, the characters must be in the order of LDRB. Use of the D option character requires an additional depth parameter to the macro or function. The depth parameter specifies the number of levels to traverse; a value of one means only the level of the tree node. A value of two means to traverse the tree node level and the nodes directly below this level, but nothing further.
The L option specifies that the traversal should also include all the nodes (and the nodes below them) that follow tree in a node list. (This is sometimes referred to as a forest traversal.) For example, if x were the first node in a list of EXPR nodes, then Ltraverse(x,Expr,act) would traverse the tree rooted at x and all the trees rooted at the EXPR nodes that follow x in the list.
All traversals assume that the tree is constructed properly, and that it does not contain circular lists or arbitrary graphs. All trees created by parse (see PARSE(5) ) are properly constructed. Problems may occur if changes are made to any of the fields, within parse tree nodes, that refer to other parse tree nodes; these are the fields that are accessed by the selector macros and the next and previous macros (see GRAMMAR(2) and LIST(5) ). Any direct manipulation of the tree by the SDTool must be done carefully!
This example traverses the entire parse tree and calls
routine eval at each node of type Expr, passing the node as
an argument to eval:
traverse(top,Expr,eval);
The following example returns the second node of type Expr
that is found in a depth-limited (to level three), rightto-left
traverse:
node = DRnthnode(top,Expr,2,NULL,3);
This example uses the FORALL macro to perform a list
traversal of all nodes of type Filename; the loop body
executes a test program on the files referred to by the
nodes:
LFORALL(fname,FILENAME,top,Filename) LOOP
printf("Testing file %s.\n",tok(fname));
test(tok(fname));
ENDLOOP
The following example creates an array of all nodes of type
Fname found in a parse tree; the nodes are ordered rightto-left
and bottom-up:
ANY *array = RBnodearray(top,Fname,NULL);
GRAMMAR(2)
FORALL(4)
ENCLOSING(5)
LIST(5)
PARSE(5)
UNIQUENODE(5)