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