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.

See also

• AttributeGrammars
• FunctionalTransformation^?
• GraphRewriting^?

---

CategorySystem | TransformationSystems | Contributions by JamesCordy