The Format description

**Figure 2:** A binary linked tree structure.
$\includegraphics[scale=0.7]{tree.eps}$

In this approach, we describe the directions as operations on paths expressed using a parameterised format. We want to be able to combine these operations to produce expressions for strings of directions.

To illustrate the descriptions we use the example of a binary tree, see Fig. 2. In this tree is binary, each node has a left and right subtree and the nodes in each level are joined by a doubly linked list.

The format description is a way of describing a set of paths that an operation can be applied to. It can be thought of as a somewhat simpler version of a regular expression.

Take as an example matching the format x.r.l^p with an arbitrary path name. Pulling the expression apart, the x will match any sequence of directions. The r term must match against one rdirection. The l^p term will match any sequence of l directions for values of p greater or equal to zero. We call p a parameter of the format. More generally, each format is a list of terms, a term being a fixed direction d or a variable number of directions d^v_i where v_i is a parameter.

A rule is a pair of formats that can be applied to a path name to produce a new path name. For example the rule $x.r.l^{p} \rightarrow x.l.r^{p}$ can be applied to the path l.r.l.r.l.l to produce l.r.l.l.r.r. The rule simply describes the operation of locating the last r in the path and flipping it to a l and all the following l to r. It corresponds to the previous direction p in our binary tree.

An operation is a set of rules that relate to moving in a particular direction from a node in the structure. In our example binary tree the directions are the left and right from the original tree, plus additional next and previous directions. We can abbreviate these directions as L,R,N,P, and describe the rules using the following syntax.

**Figure 3:** Format description of binary tree
$\begin{figure}\begin{center} \hrule \medskip\begin{center} \parbox{8cm}{ \parbox... ...\end{eqnarray*}} } \newline \end{center}\end{center}\medskip \hrule \end{figure}$

The analyser can produce dataflow/dependency information for simple programs described in Sec. 7. The Automatic Group approach is more general and has replaced the Format method. However, the Format system is a more intuitive method for describing structures, so it would be worthwhile to be able to convert automatically from this description to an underlying AG description for analysis.