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 [[Stratego.RewritingStrategiesForInstructionSelection][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 [[http://www.google.nl/search?q=tree+rewriting&hl=en&lr=][tree rewriting]]

-- Main.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.

<verbatim>
	 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 
</verbatim>

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 [[Stratego.MetaProgrammingWithConcreteObjectSyntax][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.

-- Main.EelcoVisser - 08 Jun 2002
 
----
CategorySystem | TransformationSystems | Contributions by JamesCordy, Main.EelcoVisser