Home

Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators

Rodney Farrow

Title:
Covers of Attribute Grammars and Sub-Protocol .Attribute Evaluators
Author(s):
Farrow, Rodney
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-071-83
Abstract:
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.
Subject(s):
Computer science
Item views:
87
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use