Tree Rewriting

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