Linear Data Structures for Storage Allocation in Attribute Evaluators

1 March 2002

PhD thesis defence F. J. Sluiman, faculty of Computer Science: ‘Linear Data Structures for Storage Allocation in Attribute Evaluators'

Attribute grammars were introduced in 1968 to specify the semantics of programming languages. Though they gained quick popularity in compilers and translators, the storage space requirements of the generated attribute evaluators remained a problem. This problem is the topic of this investigation.

The practical results of the investigation focus on the necessary and sufficient conditions to decide, at evaluator construction time, whether an evaluator can allocate the instances of an applied occurrence to a number of global variables, stacks and queues. Checking these conditions takes polynomial time for a simple multi-visit evaluator and exponential time for an absolutely non-circular evaluator.

The theoretical results are concerned with the data structures that are required for the global storage allocation of the instances of applied occurrences in simple multi-X evaluators, where X {pass, sweep, visit}. For this purpose, the general class of basic linear data structures is introduced. This class of data structures can also be used to explore the theoretical possibilities and limitations of storage allocation techniques in domains other than attribute grammars.

supervisors: prof. dr. H. Brinksma; prof. dr. ir. A. Nijholt
second supervisor: dr. H. Alblas
information: drs. B. Meijering, telefoon (053) 489 43 85