Remote attribute grammars

Describing the static semantics of programming languages with attribute grammars is eased when the formalism allows direct dependencies to be induced between rules for nodes arbitrarily far away in the tree. Such direct non-local dependencies cannot be analyzed using classical methods, which enable efficient evaluation. This article defines an attribute grammar extension ("remote attribute grammars") to permit references to objects with fields to be passed through the attribute system. Fields may be read and written through these references. The extension has a declarative semantics in the spirit of classical attribute grammars. It is shown that determining circularity of remote attribute grammars is undecidable. The article then describes a family of conservative tests of noncircularity and shows how they can be used to "schedule" a remote attribute grammar using standard techniques. The article discusses practical batch and incremental evaluation of remote attribute grammars.