Modular grammars for programming language prototyping

Programming languages and formal notations are central to computer science. A significant part of computer science research is conducted by constructing programming language prototypes and studying their properties. I argue that the conventional modular structure of language processors as a sequence of phase is ill-suited to language implementation and propose an alternative to phase oriented modularity: to structure the language processor according to the facets of the implemented language. A language should be viewed as a collection of language fragments, each fragment defining an independent and reusable modular component. Given this structure new languages can be built cheaply by using different combinations of language fragments, reusing many existing fragments. Cheap language implementation also makes it feasible to perform language oriented programming where application oriented languages are constructed as abstractions of problem domains enabling concise solutions to be rapidly constructed for particular problems. This report describes how to build language processors from language fragments. Language oriented modular structure is investigated in three arenas: interpreters, parsers and attribute grammars. In the first case each language fragment is embodied in an interpreter. The structure of the interpreters is changed to allow them to be combined. A modular parsing system is developed. Both the interpreters and modular parsers suffer from structure clashes which make some problems difficult to express. This is overcome with modular attribute grammars. A modular attribute evaluator is developed using a lazy functional programming language as a vehicle for experimentation. The resulting system has interesting properties: it allows language fragments to be based on the semantic structure of the language as well as the syntactic structure and includes support for programming by explicit refinement. Finally, I argue that the implementation of languages as collections of component fragments may alter our perception of programming languages themselves.