Conditional Attribute Grammars

by John Boyland.

Abstract

Attribute grammars are a useful formalism for the specification of computations on structured terms. The classical definition of attribute grammars, however, has no way of treating conditionals non-strictly. Consequently, the natural way of expressing many otherwise well-behaved computations involves a circularity. This paper presents conditional attribute grammars, an extension of attribute grammars that enables more precise analysis of conditionals. In conditional attribute grammars, attribute equations may have guards. Equations are active only when their guards are satisfied. The standard attribute grammar evaluation classes are definable for conditional attribute grammars, and the corresponding evaluation techniques can be easily adapted. However, determining membership in standard evaluation classes such as 1-SWEEP, OAG and SNC is NP-hard.

BibTeX Style Reference

@article(boyland:96cond-ag,
  author =      {John Boyland},
  title =       {Conditional Attribute Grammars}
  journal =     TOPLAS,
  volume =	18,
  number = 	1,
  month =       jan,
  year =        1996,
  pages =       {73-108},
  nothing =     {})

How to Get a Copy

Send email to boyland@cs.uwm.edu for a reprint. The article is also available through the ACM digital library.

Errata

The first full paragraph on page 99 incorrectly explains Kastens' algorithm as proceeding from sources to sinks in the graph when it actually does the reverse. It also glosses over the difference between a total order and a sequence of partitions. The paragraph should be replaced with the following:

If the attribute grammar is DNC, Kastens' OAG algorithm extends each of the partial orders R(X) into a sequence of sets of attributes which partition the set of attributes A(X). First all a in S(X) that have no successors are placed in a set at the end of the sequence. These attributes are removed from the partial order, and the set of all a in I(X) without successors are selected to be added to the sequence. This process is continued until all attributes have been handled. The sequence can be extended into a total order O(X) by adding an arbitrary ordering within each attribute set. After all orders have been constructed, one must determine whether they are consistent with the productions. If this test fails, the attribute grammar is not OAG even though it may be l-ordered.


Last Modified: May 15, 2001

Conditional Attribute Grammars / boyland@cs.uwm.edu