next up previous
Next: 4.7 Debugging with KHEPERA Up: 4 Example Previous: 4.5 Pretty-printing

4.6 The KHEPERA Transformation Language

  KHEPERA transformations are specified in a special ``little language'' that is compiled into C code for tree-pattern matching and replacement. A simple transformation rule conditionally matches a tree, builds a new tree, and performs a replacement. The rule that implements the first sequence comprehension elimination transformation (Rule 1 from Section 4.3) is shown in Figure 8.


  
Figure 8: Simple Transformation Rule
\begin{figure}
 \begin{center}
\begin{verbatim}
rule eliminate_iterator1
{
 matc...
 ...t differently in the PostScript version of
 the paper]
 \end{center}\end{figure}

In Figure 8, a tree pattern follows the match keyword. Tree patterns are written as S-expressions for convenience. The tree pattern in this example is compiled to the pattern matching code shown in the first part of Figure 9 (code for sections of the rule follow the comment containing that section).


  
Figure 9: Generated Tree-Pattern Matching Code
\begin{figure}
 \begin{center}
\begin{verbatim}
int rule_eliminate_iterator1( in...
 ...de, new );
 }
 }
 }
 }
 }
 }
 return 0;
}\end{verbatim} \end{center}\end{figure}

The when expression, which contains arbitrary C code, guards the match, preventing the rest of the rule from being executed unless the expression evaluates to true. The build statement creates a new subtree, taking care to copy subtrees from the matched tree, since those subtrees are likely to be deleted by a replace command.

The tracking necessary for debugging and transformation replay is performed at a low-level in the KHEPERA library. However, the KHEPERA language translator automatically adds functions (with names starting with trk_) to the generated rules. These functions add high-level descriptive information which allows fine-grain navigation during transformation reply, but which is not necessary for answering debugger queries.

A more complicated KHEPERA rule is shown in Figure 10. This rule implements the third sequence comprehension elimination transformation (Rule 3 from Section 4.3).


  
Figure 10: Iterator Distributing Transformation Rule
\begin{figure}
 \begin{center}
\begin{verbatim}
rule dp_func_call
{
 match (this...
 ...t differently in the PostScript version of
 the paper]
 \end{center}\end{figure}

The example in Figure 10 uses the children statement to iterate over the children of the N_ExpressionList node, and uses the do statement as a general-purpose escape to C. This escape mechanism is used to build up a new list with the tre_append function, and to modify an implementor-defined attribute (prime).

KHEPERA language features not discussed here include the use of a conditional if-then-else statement in place of a when statement, the ability to break out of a children loop, and the ability to perform tree traversals of matched subtree sections (this is useful when an expression must be examined to determine if it is independent of some variable under consideration).


next up previous
Next: 4.7 Debugging with KHEPERA Up: 4 Example Previous: 4.5 Pretty-printing
Rickard Faith
8/31/1997