Stack Machines and Classes of Nonnested Macro Languages
Joost Engelfriet, Erik M. Schmidt, Jan Van Leeuwen · Journal of the ACM · 1980
AnSTV.ACT.A new class of generalized one-way stack automata, called s-pd machines, is mvestlgated The machines are obtained by augmenting a stack automaton with a pushdown store, whose bottom is attached to the top of the stack and whose top follows the movements of the stack-pointer into the stack.Motivations for the modal include a possible protocol for macro expansion with intermittent parameter evaluatton.The languages recogmzed by these machmes are characterized by a natural class of grammars, vlz, the 91ass of OI macro grammars with set-parameters and nonnested function calls (the "extended basic" or EB macro grammars) If the stack is required to be nonerasing or checking, then a useful machine characterizatton for the ETOL languages is obtained, together with the known characterization of this family by means of extended "linear" basic or [~LB macro grammars.It follows that the nonerasmg one-way stack languages are (strictly) included m ETOL.It is proved that the family of unrestricted one-way stack languages and ETOL are incomparable, as are the general OI macro languages and the yields of ranges of topdown tree transducers.It follows that ETOL is strictly included m the family of EB macro languages (which, m turn, is strxctly included in the famdy of indexed languages) Certain determuustic restrictions of s-pd machines lead to machine models for famlhes of nonextended macro languages, vlz, for Ftscher's original linear basic macro (i e, EDTOL) and basle macro languages.