Remote Attribute Grammars

by John Boyland.

Abstract

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 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.

BibTeX Style Reference

@article(boyland:05remote-ag,
  author =      {John Boyland},
  title =       {Remote Attribute Grammars}
  journal =     JACM,
  volume = 	52,
  number = 	4,
  month = 	jul,
  year =        2005,
  pages =       {627--687},
  nothing =     {})

How to Get a Copy

A preprint is available for scholarly and personal use. The definitive version is available through the ACM digital library.

Last Modified: Feb 4, 2006

Remote Attribute Grammars / boyland@cs.uwm.edu