This paper introduces Composable Attribute Grammars (CAGs), a formalism that extends classical attribute grammars to allow for the modular composition of translation specifications and of translators. CAGs bring to complex translator writing systems the same benefits of modularity found in modern programming languages, including comprehensibility, reusability, and incremental meta-compilation.A CAG is built from several smaller component AGs, each of which solves a particular subproblem, such as name analysis or register allocation. A component AG is based upon a simplified phrase-structure that reflects the properties of its subproblem rather than the phrase-structure of the source language. Different component phrase-structures for various subproblems are combined by mapping them into a phrase-structure for the source language. Both input and output attributes can be associated with the terminal symbols of a component AG. Output attributes enable the results of solving a subproblem to be distributed back to anywhere that originally contributed part of the subproblem, e.g. transparently distributing the results of global name analysis back to every symbolic reference in the source program.After introducing CAGs by way of an example, we provide a formal definition of CAGs and their semantics. We describe a subclass of CAGs and their semantics. We describe a subclass of CAGs, called separable CAGs, that have favorable implementation properties. We discuss the novel aspects of CAGs, compare them to other proposals for inserting modularity into attribute grammars, and relate our experience using CAGs in the Linguist translator-writing system.

This paper presents aspects of a compiler for a new hardware description language (VHDL) written using attribute grammar techniques. VHDL is introduced, along with the new compiler challenges brought by a language that extends an Ada subset for the purpose of describing hardware. Attribute grammar programming solutions are presented for some of the language challenges.

Experience writing a production compiler based on an attribute grammar is related. The compiler is Intel Corporation's Pascal-86 compiler which runs on a microcomputer-based system. An attribute grammar was written describing semantic analysis, storage allocation and translation to intermediate code. Attribute evaluation is done in two alternating passes [J] and the program tree is kept in intermediate files on disk. Various techniques for optimizing the evaluator were tried. Their success is reported and compared with other ideas from the literature.

Program structure is defined in terms of a simple graph grammar, the "semi-structured flow graph grammar," which admits many of the control structure extensions suggested for "structured programming." The grammar defines a set of graph reductions which are shown to have the "Finite Church-Rosser (FCR)" property; i.e., when applied in any order to a graph, the limit (when no further reductions are possible) is unique. In particular, if a given graph is generated by the grammar, repeated application of the reductions will result in a single node regardless of the order in which they are applied. This property gives rise to an algorithm that parses a given program flow graph in time linear in the size of the graph. The resulting parse is used in a global data flow analysis algorithm which requires a number of bit-vector steps which is also linear in the size of the given graph.