Developing Efficient Interpreters Based on Formal Language Specifications

Abstract

The paper reports on extensions to the MAX system enabling the generation and refinement of interpreters based on formal language specifications. In these specifications, static semantics is defined by an attribution mechanism that allows to enrich syntax trees by control flow graphs. The dynamic semantics is defined by evolving algebras, a framework that has been successfully used to specify realistic programming languages. We apply the combined framework to a non-trivial example language and show how the resulting language specification can be refined in order to improve the efficiency of the generated interpreters. The framework provides enough modularity and flexibility so that such refinements can be carried out by local changes. We explain the implementation of the extensions to MAX and discuss applications of the system.