Theoretical Issues of the Implementation of Programming Languages

Abstract

This report presents theoretical results about two issues relevant to the implementation of programning languages. The first issue concerns data types in a highly typed algorithmic language such as Algol 68. It has long been known that equivalence of types in such a lanquaqe may be decided by an algorithm analogous to the equivalence algorithm for finite automata. In an earlier paper, we made this analogy precise bv modelling data types with a lattice theoretical mode1 based on ideas of Dana Scott. In chapter I of this work, we use this model to show that the similarity to finite automata no longer holds if parameters may be used in the definition of types. In fact, the types thus defined more closely resemble the deterministic context-free languages. More precisely, the equivalence problem for types defined using parameters is decidable if and only if the equivalence problem for deterministic context-free sets is decidable. The decidability of the latter equivalence problem is a well-known open question. In chapter 2, we consider the definition of programming languages by means oE infinite grammars. We note that many formalisms for defininq programming languages may be viewed as infinite grammars, including van Wijngaarden grammars, the attribute grammars of Knuth, and the indexed grammars of Aho. The definitions of unambiguous and LR(k) grammars may be generalized directly to infinite grammars. We show that if an infinite grammar is specified by an indexed grammar, then parsinq may be carried out by an algorithm analogous to the SLR(l) algorithm of DeRemer. The key to the technique involves showing that the relations and sets of "items" which arise, although infinite, may be represented by finite regular expressions.