Syntax directed transduction
- 1 October 1966
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in 7th Annual Symposium on Switching and Automata Theory (swat 1966)
Abstract
A transduction is a mapping from one set of sequences to another. A syntax directed transduction is a particular type of transduction which is defined on the grammar of a context free language and which is meant to be a model of part of the translation process used in many compilers. The transduction is considered from an automata theory viewpoint as specifying the input-output relation of a machine. There is a close relationship between a subclass of these transductions, the simple syntax directed transductions, and push-down machines. This relationship is investigated in detail and conditions for such transductions to be performed on push-down machines are obtained. In addition, some time bounds for transductions on Turing machines are derived.Keywords
This publication has 5 references indexed in Scilit:
- On the translation of languages from left to rightInformation and Control, 1965
- On the Computational Complexity of AlgorithmsTransactions of the American Mathematical Society, 1965
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Automatic syntactic analysis and the pushdown storeProceedings of Symposia in Applied Mathematics, 1961
- A syntax directed compiler for ALGOL 60Communications of the ACM, 1961