Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators

Rodney Farrow

Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators
Farrow, Rodney
Computer Science
Persistent URL:
Columbia University Computer Science Technical Reports
Part Number:
Department of Computer Science, Columbia University
Publisher Location:
New York
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.
Computer science
Item views
text | xml
Suggested Citation:
Rodney Farrow, , Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ