What is a Macro Tree Transducer?

Macro tree transducers were introduced by Engelfriet in [Engelfriet, 1980]. They combine the features of top-down tree transducers [Rounds, 1970] and Fischer's macro grammars [Fischer, 1968]. The first extensive investigation can be found in [Engelfriet and Vogler, 1985]. Deterministic macro tree transducers are investigated in detail in [Fülöp and Vogler, 1998], where they are compared with other formal models of syntax-directed semantics.

In principle, macro tree transducers consist of rules, each of them meaning to transform a node of the input tree depending on the node's label. Subsequent functions are called for the children of the transformed node. This means, a macro tree transducer can be considered as a recursive first-order functional program generating trees, where the choice of functions is triggered by top-down pattern matching an input tree. During a computation, macro tree transducers may accumulate intermediate results in additional parameters, and thus have access to context information. Compared to the top-down tree transducer, the ability of carrying context information to further processing steps makes the macro tree transducer the more expressive model.

Formally, a stay macro tree transducer is defined as follows.

Definition A stay macro tree transducer M is defined by

(Q,Σ,Q₀,R),

• Q is the finite set of function names,
• Σ is the finite ranked set of input and output symbols,
• Q₀ ⊂ Q is the set of initial functions, and
• R is a finite set of rules of the two forms
  1. q(a(x₁,..., x_n), y₁,... y_k) → t or
  2. q(x₀, y₁,... y_k) → t,
  where q ∈ Q is a function with k parameters (i.e. it is of rank k+1), symbol a ∈ Σ is of rank n, each x_i (0≤i≤n) denotes an input variable, each y_j (1≤j≤k) is called accumulating parameter, and t is the right-hand side. Possible right-hand sides are composed as follows:
  1. every y_j is a right-hand side,
  2. if t₁,..., t_n are right-hand sides and a∈Σ, then a(t₁,...,t_n) is also a right-hand side,
  3. if t₁,..., t_k are right-hand sides and q∈Q is of rank k, then q(x_i, t₁,...,t_k) is also a right-hand side.
  Note that only those input variables x_i are allowed in a right-hand side, that are specified in the according left-hand side, i.e. right-hand sides of rules of the second form contain only x₀.

A similar definition can be found in [Maneth, Perst, and Seidl, 2007]. In [Perst, 2007]. additionally a formal definition of the semantics can be found. Since the function calls in right-hand sides can be nested, one has to carefully distinguish between inside-out and outside-in evaluation, because in general, both evaluation modes lead to different results.

The evaluation of a stay macro tree transducer M begins at the root node of the input. Given an input tree s₀, M starts to process by evaluating one of its initial functions for the root node of s₀. A function q∈Q with actual accumulating parameters t₁,...,t_k is applied to a subtree s=a(s₁,...,s_k) by carrying out the following steps. First, it is nondeterministically chosen one of the rules q(a(x₁,..., x_n), y₁,... y_k) → t or q(x₀, y₁,... y_k) → t', for function q. If we have chosen a stay-rule, the current input tree s is substituted for the input variable x₀ and the actual parameter t_j for the accumulating variable y_j in the right-hand side t. Otherwise, we substitute the subterms s_i and t_j for the variables x_i and y_j in t'.

Example The following macro tree transducer M generates an exact copy of its input, where the input is a binary tree consisting of symbols a and b, and with leafs labeled as e, i.e., for an example tree, M performs the follwing transformation: M → M containes the following three rules: q(a(x1,x2)) → a(q(x1),q(x2)) q(b(x1,x2)) → b(q(x1),q(x2)) q(e()) → e() where each rule defines the transformation for a specific input symbol. Macro tree transducers with stay rules, on the other hand, have the ability to generate infinite many output trees for the same input tree. The following stay macro tree transducer, for example: p(a(x1)) → q(x1, a(p(x1)) p(e()) → e() q(x0, y) → b(q(x0)) q(x0, y) → y inserts above every occurrence of an a an arbitrary long sequence of b's (or non at all). If for every symbol a function q evaluates to its parameter y, then the stay mtt copies its input tree. Otherwise, the transducer can generate for the input tree all trees of the form: