1983 Reports

Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators

Farrow, Rodney

A terminology and notation, semantically-trivial covers, is introduced for describing a class of meaning-preserving transformations of attribute grammars. Two elements of this class, p-split and c-split, are studied in some detail and it is shown that for any non-circular attribute grammar G, p-split “¢ c-split(G) is a uniform attribute grammar. The class of uniform attribute grammars is of interest because particularly efficient attribute evaluators can be built for them: straight-line evaluators. Using these transformations to build a uniform grammar constructs a straight-line evaluator for the result as a side-effect. The class of uniform attribute grammars properly includes those attribute grammars that can be evaluated in left-to-right passes, alternating passes, sweeps, and also includes the class of ordered attribute grammars. The straight-line evaluator for p-split(G) can be translated into a evaluator for G, which is not a straight-line evaluator but is nearly as efficient. This protocol-evaluator is compared to the evaluator of Kennedy and Warren and Nielson's direct evaluator. It can be viewed as an optimized, pre-compiled version of the latter, and is in some ways better and some ways worse than the Kennedy-Warren evaluator. From the comparison of the relative strengths and weaknesses of the protocol-evaluator and the Kennedy-Warren evaluator a new evaluator is derived, the sub-protocol-evaluator, which is more efficient than either.