Optimization of Automatically Generated Compilers

摘要

An 'Attribute Grammar' (AG) is a formalism for specifying the ' semantics' of a computer language. Specifically, an AG specifies the rules for creating a 'structure tree' for a string, and evaluating the 'attributes' of the tree. The result of this 'attribute evaluation' (AE) is a 'decorated' tree representing the semantic properties of the string. From a software engineering standpoint, AGs have proven to be very useful in the area of compiler specification and automatic construction. This is due chiefly to three outstanding features: (1) AGs are 'declarative' specifications, which are generally accepted to be easier to write and less error prone than their procedural counterparts, and are also easier to analyze for storage optimizations; (2) AGs can be algorithmically checked to be 'non-circular' and 'complete' which guarantees that all attributes in a structure tree are computable; and (3) AEs can be mechanically derived from AG specifications. These benefits are unavailable to those who write AEs for compilers 'by hand'. Unfortunately, compilers which are automatically generated from AGs often require tremendous amounts of storage. This thesis focuses on the reduction of this storage problem.