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]

                if ( E1 ) 
                else if ( E2 )
    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

CategorySystem | TransformationSystems | Contributions by JamesCordy

Revision: r1.3 - 20 Dec 2001 - 02:33 - JamesCordy
Transform > TreeRewriting
Copyright © 1999-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback