Stack automata and compiling
- 1 January 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 14 (1) , 172-201
- https://doi.org/10.1145/321371.321385
Abstract
Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device are noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context-sensitive language is accepted by some (deterministic) stack automaton.Keywords
This publication has 6 references indexed in Scilit:
- One-way stack automataJournal of the ACM, 1967
- Ambiguity in context free languagesJournal of the ACM, 1966
- On the translation of languages from left to rightInformation and Control, 1965
- Regular canonical systemsArchive for Mathematical Logic, 1964
- Sequential formula translationCommunications of the ACM, 1960
- An enumerative technique for a class of combinatorial problemsProceedings of Symposia in Applied Mathematics, 1960