The Vienna Definition Language.

The Vienna Definition Language (VDL) is a programming language for defining programming languages. It allows us to describe precisely the execution of the set of all programs of a programming language. However, the Vienna Definition Language is important not only as one definition technique among many others but as an illustration of a new information-structure-oriented approach to the study of programming languages. The paper may be regarded as a case study in the information structure modeling of programming languages, as well as an introduction to a specific modeling technique. Part 1 includes a brief review and comparison of techniques of language definition, and then introduces the basic data structures and data structure manipulation operators that are used to define programming languages. Part 2 considers the definition of sets of data structures. Part 3 introduces the notation for specifying VDL instructions, and illustrates the definition of a simple language for arithmetic expression evaluation by giving the complete sequence of states (snapshots) that arise during the evaluation of an expression. Part 4 defines a simple block structure language in VDL and considers certain basic design issues for such languages in a more general context. Part 5 introduces an alternative definition of the block structure language defined in Part 4, proves the equivalence of the two definitions, and briefly reviews recent work on proving the equivalence of interpreters. An Appendix considers the definition of VDL in VDL. This paper may be read at a number of different levels. The reader who is interested in a quick introduction to the basic definition techniques of VDL need read only Section 1.3 and Part 3. The reader who is interested in a deeper understanding of block structure languages should emphasize Part 4, while the reader concerned with proofs of equivalence of interpreters will be interested in Part 5. [ABSTRACT FROM AUTHOR]