Tree Rewriting

Tree rewriting is a synonym for term rewriting, i.e., the process of transforming trees (tree structured data^?) into other trees by applying rewriting rules.

Bottomup tree rewriting^? is a special case of tree rewriting that is used in code generation to select instructions for subtrees of an expression tree. The paper Rewriting Strategies for Instruction Selection explains the formalization of instruction selection by means of rewrite rules and different strategies that might be employed to apply these rules.

In graph rewriting^? possibly cyclic graphs are transformed. However, tree rewriting systems^? are often implemented using a mild form of graphs, i.e, directed acyclic graphs^? (or DAG^?s) in which it is possible for subtrees to be shared by several supertrees. This is necessary for implementations to be efficient; pure tree rewriting requires making a complete copy of a tree whenever it is bound to a variable which is used more than once in a right-hand side of rewrite rule.

Tree rewrite rules can be implemented in any language that supports hierarchical data structures.

Google on tree rewriting

-- EelcoVisser - 08 Jun 2002

---

Tree rewriting is TermRewriting extended to allow rewriting of arbitrary syntactic forms, typically specified using a context-free grammar.

The pattern and replacement of a rewriting rule are expressed as sentential forms of a given nonterminal of the grammar, with pattern variables bound to deeper nonterminals in a by-example style.

An example ( TXL ) tree rewriting rule over the Java grammar appears below. In this notation nonterminal types of the grammar (in this case the Java grammar) appear in square brackets []. Words beginning with a capital letter are pattern variable names. A pattern variable name followed by a nonterminal type denotes a binding occurrence of the variable; a pattern variable name appearing without a type denotes the variable's previously bound value.

    rule nestedIfToElseIf
        replace [statement]

                if ( E1 [expression] ) 
                    S1 [statement]
                else {
                    if ( E2 [expression] )
                        S2 [statement]
                    Else2 [opt else_clause]
                }

        by
                if ( E1 ) 
                    S1 
                else if ( E2 )
                    S2
                Else2
    end rule 

Tree rewriting rules are applied to parse trees of the grammar (their scope) searching for instances of the nonterminal they rewrite (their target) under control of a RewritingStrategy, typically attribute evaluation or functional programming.

-- JamesCordy

Tree rewriting and term rewriting are usually identified, since terms are isomorphic to trees. The presentation of rewrite rules using concrete syntax^? is orthogonal to the definition of rules. In the paper Meta Programming with Concrete Object Syntax it is shown how a language based on rewriting abstract syntax trees^? can be extended to use concrete syntax trees.

-- EelcoVisser - 08 Jun 2002

---

CategorySystem | TransformationSystems | Contributions by JamesCordy, EelcoVisser