Analyzing Direct Non-Local Dependencies in 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 paper presents a new technique for analyzing such dependencies. Attribute grammars are extended 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.

This paper describes a technique for rendering the direct non-local dependencies in classical terms, after which well-known attribute grammar scheduling algorithms may be used. The generated classical dependencies use control attributes, attributes used only for scheduling and which involve no run-time computation. Thus the resulting implementations can be efficient: reading a field can be implemented as a simple indirect load; writing a field as an indirect store.

BibTeX Style Reference

@inproceedings(boyland:98fiber,
  author =      {John Tang Boyland},
  title =       {Analyzing Direct Non-Local Dependencies in 
                 Attribute Grammars},
  booktitle =   "CC'98 --- Compiler Construction, 7th International Conference",
  city =        "Lisbon, Portugal",
  date =        mar # " 28--" # apr # " 4",
  editor =      "Kai Koskimies",
  year =        1998,
  series =      "Lecture Notes in Computer Science",
  publisher =   "Springer",
  address =     "Berlin, Heidelberg, New York",
  volume =      "1383",
  pages =       {31--49},
  nothing =     {})

How to Get a Copy

The paper has been accepted to CC '98 (International Conference on Compiler Construction, part of ETAPS '98, held in Lisbon, Portugal , March 30 - April 3, 1998). It appeared in the proceedings published as part of number 1383 of Lecture Notes in Computer Science by Springer. A reprint is available with permission of Springer Verlag which holds the copyright.

Errata

Figure 1 has a couple of typographical errors. First in the rule for decls -> decls decl

	decls_0.msgs = 
	  decls_1.msgs U msgs.decld

	decls_0.msgs = 
	  decls_1.msgs U decl.msgs

	stmt.msgs = ... expr.msgs

	stmt.msgs = ... expr_1.msgs U expr_2.msgs

Last Modified: July 24, 2001