Towards a theory of data structures

摘要

A formal idealization of the data structures used in many “list processing” languages is defined. It is then shown that under a natural interpretation, these data structures define exactly the context-free languages of automata theory. Then a generalization in the direction of the “patterns” of SNØBØL is made. It is observed that this generalization models the ability of SNØBØL patterns to represent noncontext-free languages. Finally, it is shown that under certain restrictions, only context-sensitive languages are represented but that in general noncontext-sensitive languages can occur.