Extended macro grammars and stack controlled machines


Engelfriet, Joost and Slutzki, Giora (1984) Extended macro grammars and stack controlled machines. Journal of computer and system sciences, 29 (3). pp. 366-408. ISSN 0022-0000

open access
Abstract:K-extended basic macro grammars are introduced, where K is any class of languages. The class B(K) of languages generated by such grammars is investigated, together with the class LB(K) of languages generated by the corresponding linear basic grammars. For any full semi-AFL K, B(K) is a full AFL closed under iterated LB(K)-substitution, but not necessarily under substitution. For any machine type D, the stack controlled machine type corresponding to D is introduced, denoted S(D), and the checking-stack controlled machine type CS(D). The data structure of this machine is a stack which controls a pushdown of data structures from D. If D accepts K, then S(D) accepts B(K) and CS(D) accepts LB(K). Thus the classes B(K) are characterized by stack controlled machines and the classes LB(K), i.e., the full hyper-AFLs, by checking-stack controlled machines. A full basic-AFL is a full AFL K such that B(K)C K. Every full basic-AFL is a full hyper-AFL, but not vice versa. The class of OI macro languages (i.e., indexed languages, i.e., nested stack automaton languages) is a full basic-AFL, properly containing the smallest full basic-AFL. The latter is generated by the ultrabasic macro grammars and accepted by the nested stack automata with bounded depth of nesting (and properly contains the stack languages, the ETOL languages, i.e., the smallest full hyper-AFL, and the basic macro languages). The full basic-AFLs are characterized by bounded nested stack controlled machines.
Item Type:Article
Copyright:© 1984 Elsevier Science
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/69266
Official URL:https://doi.org/10.1016/0022-0000(84)90006-0
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page