Copy Rules Elimination

Attribute grammars, and particularly those generated by symbolic composition, may contain many unnecessary attribute copy rules. They are only carrying values or constants around the input structure. However, a simple static global analysis on the attribute grammar can eliminate them in most cases [31].

In the case of the revflat example, the deforestation is due to the fact that the result is already evaluated in the attribute and then passed alone the tree via attribute to . At this point, the symbolic composition is completely semantic preserving, even in the case of partially defined tree, with one infinite branch, for instance. The deforestation is complete in the sense of intermediate data structure elimination. Nevertheless, in safe cases, i.e. totally defined trees without infinite or undefined branch, the last traversal can be removed. In each node, the equality between attributes , and can be proven by structural induction over a tree. So, for this example, the copy rules elimination [31] leads to the attribute grammar below. This last version only constructs the list of the leaves from right to left without useless traversal around the tree. Finally, generating a functional evaluator [18, 29] for this attribute grammar will lead to the deforested function revflat expected in introduction.