Synthesized and inherited functions. A new computational model for syntax-directed semantics (Q1338894)

We introduce a new formal model for the concept of syntax-directed semantics, called macro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree transducers and on macro tree transducers. In the first type of transducer, semantic values are computed by means of meaning names called synthesized attributes, and by means of context names called inherited attributes. Both, synthesized and inherited attributes represent basic semantic values. In the second type of transducer, semantic values are computed by meaning names only which are called states. However, in order to have a means of handling context information, states represent functions over semantic values. The new model integrates attributed tree transducers and macro tree transducers by allowing both, meaning names and context names to represent functions over semantic values. In analogy to the terminology of attributed tree transducers, we call such meaning names and context names also synthesized functions and inherited functions, respectively. We present an inductive characterization of the tree transformation computed by an mat tree transducer. We prove that mat tree transducers are more powerful than both, attributed tree transducers and macro tree transducers. We characterize mat tree transducers by the two-fold composition of attributed tree transducers. This characterization has three consequences: (1) the height of output trees of mat tree transducers is bounded exponentially in the size of the input tree, (2) the composition hierarchy of mat tree transducers is strict, and (3) mat tree transducers are closed under right-composition with top-down tree transducers, but not under left-composition. Moreover, we prove that the addition of inherited attributes does not increase the computational power of macro tree transducers.