Academic Commons


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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-071-83
Published Here
October 25, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.