### Abstract

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.

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.

Original language | English |
---|---|

Pages (from-to) | 2641-2641 |

Journal | Mathematical reviews |

Volume | MR848436 |

Publication status | Published - 1988 |

### Keywords

- HMI-SLT: Speech and Language Technology

## Fingerprint Dive into the research topics of 'Review of "G. File: Machines for attribute grammars, Inform. and Control 69 (1986) 41-124"'. Together they form a unique fingerprint.

## Cite this

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

*Mathematical reviews*,*MR848436*, 2641-2641.