Review of "G. File: Machines for attribute grammars, Inform. and Control 69 (1986) 41-124"

An attribute grammar is a context-free grammar in which the occurrences of nonterminals in the productions are provided with certain variables, called attributes, over some semantic domain. In addition to each production of this context-free grammar G, so-called semantic rules are given in order to compute the value of the attributes. Each attribute grammar induces a (string-) translation, i.e. a set of pairs (w; s), where w is a sentence of L(G) with derivation tree T and s is the value of some designated attribute of the root of T. This value of s can be computed by applying the semantic rules recursively [cf. D. E. Knuth, Math. Systems Theory 2 (1968), no. 2, 127{145; RZhMat 1971:11 B923; correction, ibid. 5 (1971), no. 1, 95{96; RZhMat 1971:11 B923]. Another translation, called tree-translation, induced by an attribute grammar consists of all pairs (T; s).
In the paper under review two types of machines are introduced to characterize these translations, viz., the temporary [resp. permanent] register tree pushdown transducer. Roughly speaking, they are pushdown transducers extended with registers to compute the values of the attributes. These machines dene the same class of string-translations as attribute grammars, but with respect to three-translations they are more powerful than attribute grammars. Finally, an extended model of attribute grammar is introduced which denes the same class of tree-translations as these machines.