Finding Circular Attributes in Attribute Grammars

Michael Rodeh∗ Mooly Sagiv†

Abstract

The problem of finding the circular attributes in an attribute grammar is considered. Two

algorithms are proposed: the first is polynomial but yields conservative results while the second

is exact but is potentially exponential. It is also shown that finding the circular attributes is

harder than testing circularity.

Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—compilers,run-time environments; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumer-ical algorithms and Problems—computations on discrete structures; F.4.2 [Mathematical Logicand Formal Languages]: Grammars and Other Rewriting SystemsGeneral Terms: Algorithms, Language, Performance, TheoryAdditional Key Words: attribute grammar, circularity problem, computational complexity

1 Introduction

In this article the problem of finding the circular attributes in an attribute grammar (AG) is consid-ered. Four results are presented.

1. An algorithm for finding which attributes are circular. The algorithm is an extension of Knuth’salgorithm for circularity testing [17] and is the first of its kind. The worst case time and spacecomplexity of the algorithm is exponential in the size of the AG . This result is in line with theintrinsically exponential complexity of circularity testing [10, 9, 5, 6].

2. A conservative polynomial approximation algorithm for finding the circular attributes, i.e., allcircular attributes are discovered, but some non circular attributes may be reported as circular.The algorithm is an extension of Knuth’s original algorithm for circularity testing [16]. Ourtechnique yields exact results on most practical AGs.

3. Farrow’s algorithm [7] to find the circular attributes is shown to be flawed since it yieldsnon-exact results even for AGs in which Knuth’s conservative algorithm [16] is exact.

4. It is shown that the problem of finding the circular attributes, which is in general at least as hardas circularity testing, is actually harder. This is done by showing that the problem of findingthe circular attributes is NP-hard even for AGs in which Knuth’s polynomial algorithm [16]is exact. Thus, Farrow’s algorithm cannot be fixed while preserving polynomiality unlessP = NP .

1.1 Motivation

AGs were introduced by Knuth [16] as a means for defining the semantics of programming languages.He considered circular AGs (CAGs) to be meaningless, and therefore presented an algorithm for find-ing whether an AG is circular. For every grammar symbol Z his algorithm computes a summaryinput/output relation from inherited to synthesized attributes of Z. Knuth’s algorithm is conser-vative, i.e., every CAG is detected as such but it may also declare non-circular AGs (NCAGs) ascircular. Knuth also presented an exact algorithm for finding whether an AG is circular [17]. His main

∗Dept. of Computer Science, Technion, Haifa 32000, Israel and IBM Haifa Research Lab,

rodeh@haifa.vnet.ibm.com.†Dept. of Computer Science, School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978,

sagiv@math.tau.ac.il

1

idea was to use, for each grammar symbol Z, a detailed input/output relation instead of the abovementioned summary input/output relation. Unfortunately, the size of the detailed input/outputrelations may be exponential. Recently, circular AGs (CAGs) were shown to be useful for specifyingdata flow analysis problems ([7], [19]) and VLSI design ([12]). Moreover, if the functions defining thecircular attributes are monotonic relative to some partial order and if their domains do not includeinfinite chains, then the values of the attributes may be computed effectively. We see that in orderto make good use of CAGs, it is beneficial to be able to identify the circular attributes, so as toverify the desired properties of their defining functions and domains.

1.2 Results and Comparison to Previous Works

The fact that circularity testing is inherently exponential immediately implies that the problemof computing circular attributes is also exponential. Farrow [7, pp 95] presented a polynomialconservative algorithm to find the circular attributes. Thus, Farrow’s algorithm may be used toidentify which functions need to be monotonic and which of the domains do not include infinitechains. However, the fact that the algorithm sometimes reports non-circular attributes as circular,may lead to unnecessary difficulties.

1.2.1 The Negative Results

Farrow claims that for AGs in which the summary input/output relations do not contain superfluousdependencies, his algorithm is exact [7, Theorem 3]. In this article we give a counter-example to thisclaim. We also define a sub-class of AGs called lower uniform in which all the summary input/outputdependencies are simultaneously exhibited by some trees. Knuth’s conservative algorithm is exacton lower uniform AGs. We show that the problem of finding whether a given attribute is circularis NP-hard even for lower uniform AGs. Thus, under the assumption that P 6= NP no polynomialalgorithm exists for computing the circular attributes in lower uniform AGs. This proves that theproblem of finding the circular attributes cannot be solved in polynomial time even for the so calledpractical AGs in which circularity testing is easy.

1.2.2 An Exact Algorithm

In order to develop an exact algorithm for finding the circular attributes, we maintain not only de-tailed input/output relations from inherited to synthesized attributes but also detailed output/inputrelations from synthesized to inherited attributes. Knuth’s exact algorithm does not need the out-put/input relations since in order to find if an AG is circular, it is sufficient to find the uppermostproduction in a tree in which circularity occurs. However, to find the circular attributes themselves,we need to propagate this information down along the tree edges.

1.2.3 Conservative Algorithms

To reduce the complexity of our algorithm we have to compromise exactness. We extend the approachused in Knuth’s conservative algorithm by maintaining for every grammar symbol not only thesummary input/output relation but also a summary output/input relation.

While detailed output/input relations were never used in the literature, summary output/inputrelations were defined elsewhere [4, pp. 16]. For reasons of efficiency, systems which convert NCAGsinto programs such as GAG [15], compute a summary relation which includes both summary in-put/output relation and summary output/input relation for every grammar symbol Z (see [14, 2]).It can be shown that such an approach may also be used to conservatively compute the set of circularattributes. Naturally, the results will be more conservative than those obtained by keeping the tworelations separate.

Our conservative algorithm yields exact results on most practical AGs. The accuracy of thealgorithm is in general incomparable with that of Farrow’s but they can be combined to yield asuperior algorithm.

1.3 Outline of the Article

In Section 2 we give a short introduction to AGs which includes a definition of CAGs, input/outputrelations and lower uniform AGs. In Section 3 we show that Farrow’s algorithm is not exact evenfor lower uniform AGs. In Section 4 we show that it is NP-hard to find whether a given attribute in

2

a lower uniform AGs is circular. In Section 5 we give an exact exponential algorithm for computingthe circular attributes while in Section 6 we give two conservative polynomial algorithms.

2 Attribute Grammars

An attribute grammar consists of the following components:

1. A reduced context-free grammar where each production p has the form: p:Z → Z1Z2 · · ·Zn,where Z is a non-terminal and each Zi is a grammar symbol.

2. A fixed set Attr [Z] of attribute names associated with each grammar symbol Z. Each attributehas a domain over which it is defined. We will not make any assumptions regarding thesedomains and therefore ignore them altogether. The set Attr [Z] of Z is partitioned into the setInh[Z] of inherited attributes and the set Syn[Z] of synthesized attributes.

3. A set of semantic equations associated with every production p:Z → Z1Z2 · · ·Zn. Let Attr [p]be the distinct appearances of attributes in p. To avoid cumbersome notation we assume thatZi 6= Zj for every i 6= j. By definition, Attr [p] may be partitioned into two subsets Input [p]and Output [p] where:

Output [p]def= {Z.a|a ∈ Syn[Z]} ∪ {Zi.a|1 ≤ i ≤ n, a ∈ Inh[Zi]}

Input [p]def= {Z.a|a ∈ Inh[Z]} ∪ {Zi.a|1 ≤ i ≤ n, a ∈ Syn[Zi]}

The semantic equations associated with p consist of a unique semantic equation for everyattribute in Output [p] which uses some of the attributes in Attr [p].

An AG is normalized when the semantic equations associated with every production p use onlyattributes from Input [p]. Figure 1 contains an example AG. The AG in this example and in all thefollowing ones are normalized. Also, we use ambiguous grammars without terminals, so as to makethe AGs smaller.

p1: S → X{

X.a = X.cX.b = X.d

}

p2: X → ǫ{

X.d = X.aX.c = X.b

}

p3: X → Y

Y.a = X.aY.b = X.bX.d = Y.dX.c = Y.c

p4: Y → ǫ{

Y.d = Y.aY.c = constant

}

Figure 1: An example AG

The attributes in this AG are:

Inh[S] = φ Syn[S] = φInh[X] = {a, b} Syn[X] = {c, d}Inh[Y ] = {a, b} Syn[Y ] = {c, d}

Let Z be a grammar symbol. A Z-derivation tree is a syntax tree with a root of type Z and withboth terminals and non-terminals in the leaves. A derivation tree is a Z-derivation tree for some Z.Let S be the start symbol of the grammar. A terminal tree is an S-derivation tree where each of itsleaves is either a terminal symbol or an ǫ. For a vertex u ∈ T , Tu denotes the subtree Tu of T rootedat u.

3

u1S p1

?u2X p2

?u3ǫ

A terminal tree for theAG of Figure 1

u2.a u2.b u2.c u2.d? ?

66

The compound dependency relationfor the tree of the left

Figure 2: An example for terminal tree and its compound dependency relation

2.1 Dependencies Among Attributes

To define properties of attributes, we first need some further notation. Let R ⊆ A × A and let(a, b) ∈ R. We say that a is used in R and b is defined in R. The relations R+, R∗ ⊆ A×A denotesthe transitive closure of R and the reflexive transitive closure of R, respectively. We say that bdepends on a in R if (a, b) ∈ R+. Similarly, b reflexively depends on a in R if (a, b) ∈ R∗. For B ⊆ A,

R+/Bdef= {(a, b)|a, b ∈ B, (a, b) ∈ R+}.

Next, let us define D[p], the local dependency relation of a production p. D[p] is a subset ofAttr [p]× Attr [p] s.t. (Z1.a1, Z2.a2) ∈ D[p] if Z1.a1 is used in the semantic equation associated withp which defines Z2.a2.

Let T be a derivation tree. The set Attr(u) of attribute occurrences of a vertex u of a tree T

of type Z is defined by Attr(u)def= {u.a|a ∈ Attr [Z]}. The set Attr(T ) of attribute occurrences

in T is the union of all Attr(u), u ∈ T . The compound dependency relation D(T ) ⊆ Attr(T ) ×Attr(T ) is obtained by pasting together all the local dependency relations of all the occurrencesof productions in T . Figure 2 contains a terminal tree for the AG of Figure 1 together with itscompound dependency relation. In that figure we denote the dependencies of D[p1] by thick upperarrows and the dependencies of D[p2] by thin lower arrows.

2.2 Circular Attribute Grammars

Consider a production p:Z0 → Z1Z2 · · ·Zn. An attribute Zi.a ∈ Attr [p] is circular in p if there existsa terminal tree T and vertex u ∈ T of type Zi s.t. u.a depends on itself in D(T ) and p is applied at uor at the ancestor of u. The set of circular attributes of p is denoted by CAttr[p]. An AG is circularif it contains a production with circular attributes.

Using the AG of Figure 1, only two distinct terminal trees may be derived. One of these trees isshown in Figure 2. In this tree p1 and p2 are applied and all the attributes participate in a singlecycle. In the other tree, where p3 and p4 are applied, no attribute appears in a cycle. Therefore,

CAttr[p1] = {X.a, X.b, X.c, X.d}CAttr[p2] = {X.a, X.b, X.c, X.d}CAttr[p3] = φCAttr[p4] = φ

2.3 Input/Output Relations

Knuth’s conservative algorithm computes the summary input/output relation IO[Z] ⊆ Attr [Z] ×Attr [Z] for every grammar symbol Z [16]. The algorithm proceeds iteratively in a bottom-up manner.It starts with IO[Z] = φ. For every production p:Z → Z1Z2 · · ·Zn it iteratively adds to IO[Z] thedependencies in (D[p] ∪ ∪ni=1IO[Zi])

+/Attr [Z].

4

For every grammar symbol Z, only synthesized attributes of Z are defined in IO[Z]. Also, if theAG is normalized then only inherited attributes of Z are used in IO[Z]. Therefore, in a normalizedAG, IO[Z] contains only dependencies from inherited to synthesized attributes of Z.

Applying Knuth’s algorithm to the AG of Figure 1 we get:

IO[S] = φIO[X] = {(X.a, X.d), (X.b, X.c)}IO[Y ] = {(Y.a, Y.d)}

Knuth’s conservative algorithm tests whether an AG is circular by checking whether (D[p] ∪∪n

i=1IO[Zi]) contains a cycle. Every circular AG is thereby detected as such since IO[Z] indeedsummarizes all the input/output relations of Z as stated in the following theorem.

Theorem 2.1 [16] For every Z-derivation tree Tu, D+(Tu)/Attr(u) ⊆ IO[Z].

Unfortunately, for some AGs equality in Theorem 2.1 never holds. An AG is lower uniform ifequality does hold for at least one tree, i.e., for every grammar symbol Z there exists a Z-derivationtree Tu s.t. D+(Tu)/Attr(u) = IO[Z]. By definition, Knuth’s conservative algorithm yields exactresults for every lower uniform AG. The AG of Figure 1 is lower uniform. The X-derivation treewhich contains only p2 exhibits the dependencies of IO[X]. The Y -derivation tree which containsonly p4 exhibits the dependencies of IO[Y ].

In [17] an exact algorithm is given which solves the circularity problem by maintaining detailedinput/output relations IO[Z] ⊆ 2Attr [Z]×Attr [Z] which are actually sets of input/output relations.The algorithm starts with IO[Z] = {φ}. For every production p:Z → Z1Z2 · · ·Zn and relationsR[Zi] ∈ IO[Zi], the algorithm adds to IO[Z] the relation (D[p] ∪ ∪ni=1R[Zi])

+/Attr [Z]. Thus, incontrast to the conservative algorithm, dependencies from different relations are not combined. Fora complete procedural description of the algorithm see [1, pp. 335]. Unfortunately, the cardinalityof IO[Z] may be exponential in the size of the AG. Applying Knuth’s exact algorithm to the AG ofFigure 1 yields:

IO[S] = {φ}IO[X] = {φ, {(X.a, X.d), (X.b, X.c)}, {(X.a, X.d)}}IO[Y ] = {φ, {(Y.a, Y.d)}}

Knuth’s exact algorithm tests whether an AG is circular by checking if (D[p] ∪ ∪ni=1R[Zi]) con-

tains a cycle for some R[Zi] ∈ IO[Zi]. The following theorem guarantees the exactness of Knuth’salgorithm.

Theorem 2.2 [17] There exists a Z-derivation tree Tu s.t. R[Z] = D+(Tu)/Attr(u) if and only ifR[Z] ∈ IO[Z].

3 Farrow’s Algorithm for Finding the Circular Attributes

In this section we give a brief description of a slight variation of Farrow’s algorithm [7, pp. 95] andshow that it is not exact even for lower uniform AGs.

For every production p, Farrow’s algorithm computes a set M [p] ⊆ Attr [p] of attributes whichare suspected to be circular in p. The algorithm employs the set MIO[Z] ⊆ IO[Z] of input/outputdependencies for every grammar symbol Z. The algorithm proceeds in a top-down manner. Initially,M [p] = φ and MIO[Z] = φ for every p and Z. The algorithm processes one production p:Z →Z1Z2 · · ·Zn in every iteration. It adds attributes to M [p] and dependencies to MIO[Zi] according tothe functions Direct Mark and Indirect Mark described below.

1. Direct Mark(p) adds to M [p] and MIO[Zi] respectively the attributes and dependencies inD[p] ∪ ∪n

i=1IO[Zi] which appear on cycles.

2. Indirect Mark is invoked for every dependency (Z.a1, Z.a2) ∈ MIO[Z] individually. Indirect Mark(p, (Z.a1, Z.a2))adds to M [p] and MIO[Zi] respectively the attributes and dependencies in D[p] ∪ ∪n

i=1IO[Zi]which appear on some paths from Z.a1 to Z.a2.

Let us demonstrate Farrow’s algorithm by applying it to the AG of Figure 1.

1. When p1 is processed, Direct Mark(p1) sets M [p1] = {X.a, X.b, X.c, X.d} and MIO[X] ={(X.a, X.d), (X.b, X.c)}. Since MIO[S] = φ, Indirect Mark is not invoked.

5

2. When p2 is processed, Direct Mark(p2) adds nothing since D[p2] is acyclic. Indirect Mark(p2, (X.a, X.d))sets M [p2] = {X.a, X.d} and since the right hand side of p2 is empty, it does not add new de-pendencies. Similarly, Indirect Mark(p2, (X.b, X.c)) sets M [p2] = {X.a, X.d, X.b, X.c}.

3. When p3 is processed, Direct Mark(p3) adds nothing since D[p3]∪IO[Y ] is acyclic. Indirect Mark(p3, (X.a, X.d))sets M [p3] = {X.a, Y.a, Y.d, X.d} and MIO[Y ] = {(Y.a, Y.d)}. Since there exists no path fromX.b to X.c in D[p3] ∪ IO[Y ], Indirect Mark(p4, (X.b, X.c)) does not add new attributes ordependencies.

4. When p4 is processed, Direct Mark(p4) adds nothing since D[p4] is acyclic. Indirect Mark(p4, (Y.a, Y.d))sets M [p4] = {Y.a, Y.d}.

5. The algorithm converges when it processes p1, p2, p3 and p4 for the second time.

Farrow claims that his algorithm is exact under the assumption that for every dependency inIO[Z] there exists a Z-parse tree which exhibits this dependency [7, Theorem 3]. The AG of Table 1shows that Farrow’s algorithm is not exact even for lower uniform AGs (for which all the dependenciesare simultaneously exhibited). For example, M [p4] = {Y.a, Y.d} and yet CAttr[p4] = φ. Indeed,Indirect Mark is not necessarily exact even for lower uniform AGs. The fact that (Z.a, Z.b) appearson a cycle above a production p:Z → Z1Z2 · · ·Zn does not necessarily imply that it must appear ona cycle in p since it can occur when some other production p′:Z → α is applied. In the followingsection we show that the fact that Farrow’s algorithm is not exact in not accidental.

4 The Negative Result

Let G = (V, E) be a finite directed graph. A path π in G is Hamiltonian if every v ∈ V appearsin π once. The Hamiltonian path problem is to decide whether G contains a Hamiltonian path.The problem is a well known NP-complete [8, pp. 60]. A variant of this problem, namely, findingwhether a Hamiltonian path exists from a specific vertex s to another specific vertex t is obviouslyNP-complete too. In this section we present a reduction from the Hamiltonian path problem to theproblem of finding whether a given attribute in a lower uniform AG is circular, thereby proving thatthe latter problem is NP-hard.

Let G = (V, E) be a directed graph for which we are interested in the existence of a Hamiltonianpath between two points s and t. Without loss of generality, we shall assume that:

1. V = {0, 1, . . . , n} where n > 1.

2. s = 0 and t = n.

3. The vertex 0 is a source and the vertex n is a sink , i.e., for every k, (k, 0), (n, k) 6∈ E.

Given G, Figure 3 contains a parametric AG AG(G) in which the attribute Xn.11 is circular if andonly if G has a Hamiltonian path from 0 to n. The non-terminals in AG(G) are X0, X1, . . . , Xn whereX0 is the start non-terminal. The derivation trees in AG(G) simulate paths in G and the attributedependencies are used to guarantee that no vertex appears twice on path. For every 0 < i ≤ n,Inh[Xi] = {aj |0 < j < n} and Syn[Xi] = {0j , 1j ||0 < j < n}. Intuitively, the semantic equations ofAG(G) guarantee that Xi.aj depends on Xi.0j if j does not appear on some path to i in G. Similarly,Xi.aj depends on Xi.1j if j appears once on some path to i in G.

As an example, consider the graph in Figure 4. It contains a unique Hamiltonian path (0, 2, 1, 3).The corresponding terminal tree and its compound dependency relation is shown in Figure 5. Indeed,this is the unique compound dependency relation in which X3.11 depends on itself. More specifically,for j = 1 and j = 2, u4.aj depends on u4.1j , and thus the vertices 1 and 2 appear once in (0, 2, 1, 3).

The number of attributes and semantic equations in AG(G) is O(n2). Also, the productions ci

guarantee that AG(G) is indeed lower uniform as stated in the following lemma.

Lemma 4.1 AG(G) is a lower uniform AG.Proof: In AG(G), pn is the only production in which Xn appears on the left. Therefore, only pn hasto be considered when computing IO[Xn]. However, the right hand side of pn is empty. Therefore,there exists a unique Xn-derivation tree and this tree exhibits the dependencies of IO[Xn].

6

p(0,j): X0 → Xj : (0, j) ∈ E{

Xj .ak = Xj .0k : 0 < k < n}

p(i,j): Xi → Xj : (i, j) ∈ E, i, j 6= 0, i 6= n

Xj .ak = Xi.ak : 0 < k < nXi.0k = Xj .0k : 0 < k < n, k 6= iXi.1k = Xj .1k : 0 < k < n, k 6= iXi.0i = Xj .1i

Xi.1i = constant

pn: Xn → ǫ

Xn.1k+1 = Xn.ak : 0 < k < n− 1Xn.11 = Xn.an−1

Xn.0k = constant : 0 < k < n

ci: Xi → ǫ : 0 < i < n

Xi.0k+1 = Xi.ak : 0 < k < n− 1Xi.1k+1 = Xi.ak : 0 < k < n− 1Xi.01 = Xi.an−1

Xi.11 = Xi.an−1

Figure 3: A parametric AG AG(G) for G = ({0, 1, . . . , n}, E)

0 1

23

-

@@

@@

@@

@@

@R?

��

��

��

��

�

6

�

Figure 4: An example of a directed graph

7

u1X0p(0,2)

?u2X2

p(2,1)

?u3X1

p(1,3)

?u4X3 p3

?u5ǫ

The terminal tree which correspondsto the path (0, 2, 1, 3) in thegraph shown in Figure 4

u2.a2 u2.a1 u2.11 u2.12 u2.01 u2.02

u3.a2 u3.a1 u3.11 u3.12 u3.01 u3.02

u4.a2 u4.a1 u4.11 u4.12 u4.01 u4.02

? ?

??

? ?

6

��

��

��

��36

6 6

��

��

��

��36 6

The compound dependency relationfor the terminal tree on the left

Figure 5: The terminal tree which corresponds to the path (0, 2, 1, 3) and its compound dependencyrelation

It is easy to show that for every 0 ≤ i ≤ n,

IO[Xi] ⊆ {(Xi.ak, Xi.0k+1), (Xi.ak, Xi.1k+1)|0 < j < n}∪{(Xi.an−1, Xi.01), (Xi.an−1, Xi.11)} = D[ci]Therefore, the Xi-derivation tree in which only ci is applied exhibits IO[Xi].

All the derivation trees of AG(G) have a shape of a string. Therefore, we denote derivation trees inAG(G) by a sequence of vertices (u1, u2, . . . , um) where u1 is the root and um is the leaf. Notice thatonly the type of um may be ǫ. Let ind(ui) be the vertex G which corresponds to ui, i.e., ind(ui) = j ifthe type of ui is Xj . For convenience reasons we denote by ind(ui) = −1 the case in which the type of

ui is ǫ. The (possibly empty) path π(T ) of T is defined by π(T )def= (ind(u1), ind(u2), . . . , ind(um−1)).

Notice that the leaf of T is not included in π(T ).

Lemma 4.2 There exists an Xi-derivation tree T = (u1, u2, . . . , um) in AG(G) if and only if thereexists a path π(T ) from i to ind(um−1) in G.Proof: Straightforward by induction on |T |, using the fact that 0 is a source and n is a sink.

The basic property of the attribute dependencies of AG(G) is stated in the following lemma.

Lemma 4.3 For every X0-derivation tree T = (u, u1, u2, . . . , um) in AG(G) s.t. ind(um) 6= −1 andfor every 0 < k < n, exactly one of the following conditions hold:(i) k does not appear in π(T ), um.ak depends on um.0k, and um.ak does not depend on um.1k inD(T ).(ii) k appears in π(T ) once, um.ak depends on um.1k, and um.ak does not depend on um.0k in D(T ).(iii) k appears more than once in π(T ) and um.ak does not depend on um.0k neither does it dependon um.1k in D(T ).Proof: By induction on m.Basis: For m = 1, π(T ) = (ind(u)) = (0). Therefore, no vertex 0 < k < n appears in π(T ). Also,

8

for every k, u1.ak depends only on u1.0k in D[p(0,ind(u1))] which implies that (i) holds.

Induction hypothesis: Assume that for some m and for every X0-derivation tree T = (u, u1, . . . , um)in AG(G) s.t. ind(um) 6= −1 and 0 < k < n, either (i), (ii) or (iii) holds.Induction step: Let T = (u, u1, . . . , um, um+1) be an X0-derivation tree in AG(G) s.t. ind(um+1) 6=−1. Let i← ind(um), j ← ind(um+1) and T ′ ← (u, u1, . . . , um). Notice that i 6= 0. We shall use thisfact in the sequel. Pick an integer, 0 < k < n. By definition, π(T ) = (π(T ′), i). We proceed by caseanalysis.Case 1 : k does not appear in π(T ′). By the induction hypothesis, (i) holds. Therefore, um.ak

depends on um.0k and does not depend on um.1k in D(T ′). Also, um+1.ak depends on um.ak inD[p(i,j)] and on no other attributes. Hence, um+1.ak depends on um.0k in D(T ) and does not dependon um.1k. Two subcases arise.Subcase 1.1 : k = i. In D[p(i,j)], um.0k depends on um+1.1k. Therefore, um+1.ak depends on um+1.1k

in D(T ). Also, since um+1.0k is not used in D[p(i,j)], um+1.ak does not depend on um+1.0k in D(T ).Finally, since k appears once in π(T ), we conclude that (ii) holds.Subcase 1.2 : k 6= i. In D[p(i,j)], um.0k depends on um+1.0k. Therefore, um+1.ak depends on um+1.0k

in D(T ). Also, since um+1.1k is only used in D[p(i,j)] for defining um.1k, we conclude that um+1.ak

does not depend on um+1.1k in D(T ). Finally, since k does not appear in π(T ), we conclude that (i)holds for k in T .Case 2 : k appears once in π(T ′). By the induction hypothesis (ii) holds for k in T ′. Therefore,um.ak depends on um.1k and does not depend on um.0k in D(T ′). Also, um+1.ak only depends onum.ak in D[p(i,j)]. Hence, um+1.ak depends on um.1k and does not depend on um.0k in D(T ). Twosubcases arise.Subcase 2.1 : k = i. Since um+1.0k is not used in D[p(i,j)], it is obvious that um+1.ak does notdepend on it in D(T ). Also, since um+1.1k is only used in D[p(i,j)] for defining um.0k, um+1.ak doesnot depend on um+1.1k in D(T ) either. Finally, since k appears in π(T ) twice, we conclude that (iii)holds for k in T .Subcase 2.2 : k 6= i. In D[p(i,j)], um.1k depends on um+1.1k. As shown above, um+1.ak dependson um.1k. Therefore, um+1.ak depends on um+1.1k in D(T ). Also, since um+1.0k is only used inD[p(i,j)] for defining um.0k, um+1.ak does not depend on um+1.0k in D(T ). Finally, since k appearsin π(T ) once, we conclude that (ii) holds for k in T .Case 3 : k appears more than once in π(T ′). By the induction hypothesis, (iii) holds for k in T ′.Therefore, um.ak does not depend on um.0k neither does it depend on um.1k in D(T ). Also, um+1.ak

depends on um.ak in D[p(i,j)] and on nothing else. Hence, um+1.ak does not depend on um.0k neitherdoes it depend on um.1k in D(T ). Since in D[p(i,j)] um+1.0k and um+1.1k may only be used to defineum.0k and um.1k, we conclude that um+1.ak does not depend on um+1.0k neither does it depend onum+1.1k in D(T ). This implies (iii) and the lemma is proven.

Let T = (u, u1, u2, . . . , um) be a terminal tree in AG(G) s.t. ind(um−1) = n. In Lemmas 4.4–4.7below we show that um−1.an−1 depends on um−1.11 in D(T ) if and only if for every 0 < j < n,um−1.aj depends on um−1.1j . Combining with Lemma 4.3 (ii), we conclude that um−1.an−1 dependson um−1.11 in D(T ) if and only if for every 0 < j < n, j appears in π(T ) once, and thus π(T ) is aHamiltonian path.

Lemma 4.4 For every 0 < i, j < m, 0 < k, l < n and attribute occurrence b = uj .1l or b = uj .0l,ui.ak depends on b in D(T ) if and only if u1.ak depends on b.Proof: Straightforward by induction on i.

Lemma 4.5 For every 0 < i, j < m, 0 < k < n − 1, 0 < l < n, and attribute occurrence b = uj .1l

or b = uj .0l,(i) in D(T ), ui.1k+1 depends on b if and only if um−1.ak depends on b and ui.1k+1 reflexively dependson um−1.1k+1.(ii) in D(T ), ui.0k+1 depends on b if and only if um−1.ak depends on b and ui.0k+1 depends onum−1.1k+1.Proof: By induction on i, i = m− 1, m− 2, . . . , 1.Basis: For i = m − 1, ind(um−1) = n. By the construction, um−1.0k+1 does not depend on anyattribute in D[pn]. Therefore, (ii) vacuously holds. To show that (i) holds, observe that um−1.1k+1

9

reflexively depends on itself in D(T ). Also in D[pn], um−1.1k+1 depends only on um−1.ak. Therefore,in D(T ), um−1.1k+1 depends on b if and only if um−1.ak depends on b.Induction hypothesis: Assume that (i) and (ii) hold for some 2 ≤ i ≤ m− 1.Induction step: Let us show that (i) and (ii) hold for i− 1, by case analysis.Case 1 : k+1 = ind(ui−1). (i) vacuously holds for i−1 since in D[p(ind(ui−1),ind(ui))

] ui−1.1k+1 does

not depend on any attribute. Let us show that (ii) holds. In D[p(ind(ui−1),ind(ui))], ui−1.0k+1 only

depends on ui.1k+1. Therefore, in D(T ), ui−1.0k+1 depends on b if and only if ui.1k+1 depends onb. Applying (i) of the induction hypothesis, we find that this holds if and only if um−1.ak dependson b and ui−1.0k+1 depends on um−1.1k+1.Case 2 : k + 1 6= ind(ui−1). By (i) of the induction hypothesis, in D(T ), ui.1k+1 depends onb if and only if um−1.ak depends on b and ui.1k+1 reflexively depends on um−1.1k+1. Also, inD[p(ind(ui−1),ind(ui))

], ui−1.1k+1 only depends on ui.1k+1. Therefore, in D(T ), ui−1.1k+1 depends

on b if and only if um−1.ak depends on b and ui−1.1k+1 depends on um−1.1k+1. Hence, (i) holds fori− 1. Similarly, since (ii) holds for i, it also holds for i− 1.

Lemma 4.6 For every 0 < k < n − 1, in D(T ), um−1.ak+1 depends on um−1.11 if and only ifum−1.ak depends on um−1.11 and um−1.ak+1 depends on um−1.1k+1.Proof of the only-if direction: Let 0 < k < n − 1 s.t. um−1.ak+1 depends on um−1.11 in D(T ).Applying Lemma 4.4 to i ← m − 1 and b ← um−1.11, we conclude that in D(T ), u1.ak+1 dependson um−1.11. Also, in D[p(0,ind(u1))

], u1.ak+1 only depends on u1.0k+1. Therefore, in D(T ), u1.0k+1

depends on um−1.11. Applying Lemma 4.5 (ii) to i ← m − 1 and b ← um−1.11, we conclude thatin D(T ), um−1.ak depends on um−1.11 and u1.0k+1 depends on um−1.1k+1. Also, in D[p(0,ind(u1))

],

u1.ak+1 depends on u1.0k+1. Hence, u1.ak+1 depends on um−1.1k+1 in D(T ). Applying Lemma 4.4to i← m− 1 and b← um−1.11, we conclude that in D(T ), um−1.ak+1 depends on um−1.1k+1.Proof of the if direction: Let 0 < k < n−1 s.t. in D(T ) um−1.ak depends on um−1.11 and um−1.ak+1

depends on um−1.1k+1. In D[pn], um−1.1k+1 depends on um−1.ak which implies that um−1.1k+1

depends on um−1.11 in D(T ). Since um−1.ak+1 depends on um−1.1k+1 in D(T ), we conclude thatum−1.ak+1 depends on um−1.11 in D(T ).

Lemma 4.7 For every 0 < k < n, um−1.ak depends on um−1.11 in D(T ) if and only if for every0 < j ≤ k, um−1.aj depends on um−1.1j.Proof: Straightforward application of Lemma 4.6 by induction on k.

Proposition 4.8 There exists a Hamiltonian path from 0 to n in G if and only if Xn.11 ∈ CAttr[pn].Proof of the if direction: Assume that Xn.11 ∈ CAttr[pn]. Then, there exists a terminal treeT = (u, u1, u2, . . . , um) in AG(G) s.t. ind(um−1) = n, the production applied at um−1 is pn andum−1.11 depends on itself in D(T ). By Lemma 4.2 π(T ) is a path from 0 to n. Since um−1.11

depends on itself in D(T ) and since um−1.11 depends only on um−1.an−1 in D[pn], um−1.an−1 mustdepend on um−1.11 in D(T ). Applying Lemma 4.7 to k ← n−1, we conclude that for every 0 < j < n,um−1.aj depends on um−1.1j in D(T ). Applying Lemma 4.3 to m← m− 1 and k ← j, we find thatconditions (i) and (iii) of the lemma are false. Therefore, (ii) holds, i.e., j appears in π(T ) once.Therefore, π(T ) is a Hamiltonian path in G.Proof of the only-if direction: Let π be a Hamiltonian path in G from 0 to n. By Lemma 4.2,there exists an X0-derivation tree T = (u, u1, u2, . . . , um) s.t. π = π(T ) and ind(um−1) = n. Inparticular, T is a terminal tree. Applying Lemma 4.3 (ii) to m ← m − 1, we observe that forevery 0 < k < n, um−1.ak depends on um−1.1k in D(T ). Applying Lemma 4.7 to k = n − 1, weconclude that um−1.an−1 depends on um−1.11 in D(T ). Since um−1.11 depends on um−1.an−1 inD[pn], um−1.11 ∈ CAttr[pn].

Theorem 4.9 Given a lower uniform AG, a production p and an attribute a, it is NP-hard to decidewhether a ∈ CAttr[p].

5 Finding the Circular Attributes

In Section 5.1 we give an algorithm to compute the detailed output/input relations. In Section 5.2we use these relations together with the detailed input/output relations to compute the circularattributes.

10

5.1 Output/Input Relations

5.1.1 An Iterative Algorithm

We now give an algorithm to compute the detailed output/input relations OI[Z] ⊆ 2Attr [Z]×Attr [Z]

for every grammar symbol Z. The algorithm proceeds iteratively in a top-down manner. It startswith OI[Z] = {φ}. In every iteration, the algorithm processes one production p:Z → Z1Z2 · · ·Zn.For every 1 ≤ j ≤ n, R[Z] ∈ OI[Z] and R[Zi] ∈ IO[Zi], it adds to OI[Zj ] the relation

(R[Z] ∪ D[p] ∪ ∪ni=1,i 6=jR[Zi])+/Attr [Zj] (1)

Let us apply the algorithm to the AG of Figure 1.

1. When p1 is processed, the algorithm sets OI[X] = {φ, {(X.c, X.a), (X.d, X.b)}}.

2. Since the right hand side of p2 is empty, the algorithm does nothing for p2.

3. When p3 is processed, the algorithm sets OI[Y ] = {φ, {(Y.c, Y.a), (Y.d, Y.b)}}.

4. Since the right hand side of p4 is empty, the algorithm does nothing for p4.

5. When the algorithm processes p1, p2, p3 and p4 for the second time, convergence is detected.

The AG of Figure 1 has only unit or ǫ productions. Therefore the union operation ∪ni=1,i 6=jR[Zi] is

empty. Thus, in this example the IO relations are not used to determine the OI relations. Also, inthis example there is only one non-empty output/input relation. As another example, the IO andOI relations for AG(G) of Figure 3 where G is the graph of Figure 4 are shown below:

IO[X3] =

{

φ,{(X3.a1, X3.12), (X3.a2, X3.11)}

}

IO[X1] =

φ,{(X1.a1, X1.12), (X1.a1, X1.02), (X1.a2, X1.11), (X1.a2, X1.01)},{(X1.a1, X1.12), (X1.a2, X1.01)}

IO[X2] =

φ,{(X2.a1, X2.02), (X2.a2, X2.11), (X2.a2, X2.01)},{(X2.a1, X2.02), (X2.a2, X2.01)},{(X2.a1, X2.12), (X2.a1, X2.02), (X2.a2, X2.11), (X2.a2, X2.01)},{(X2.a1, X2.02), (X2.a2, X2.11)}

IO[X0] = {φ}OI[X0] = {φ}

OI[X2] =

{

φ,{(X2.01, X2.a1), (X2.02, X2.a2)}

}

OI[X1] =

φ,{(X1.01, X1.a1), (X1.02, X1.a2)},{(X1.01, X1.a1), (X1.12, X1.a2)}

OI[X3] =

φ,{(X3.01, X3.a1), (X3.02, X3.a2)},{(X3.01, X3.a1), (X3.12, X3.a2)},{(X3.11, X3.a1), (X3.02, X3.a2)},{(X3.11, X3.a1), (X3.12, X3.a2)}

5.1.2 Properties of Detailed Output/Input Relations

Output/input relations are dual to the input/output relations in the same sense that synthesizedattributes are dual to inherited attributes. For every grammar symbol Z and R[Z] ∈ OI[Z], onlyinherited attributes are defined in R[Z]. Also, if the AG is normalized then only synthesized attributesare used in R[Z]. Therefore, in a normalized AG, R[Z] only contains dependencies from synthesizedto inherited attributes. In Lemma 5.2 and 5.3 below we present results which are dual to Theorem 2.2.

In the sequel, Tu denotes the subtree of T obtained be deleting the descendants of u from T .

Lemma 5.1 Let T be a derivation tree and u0 be an internal vertex in T . Let p:Z0 → Z1Z2 · · ·Zn

be the production applied at u0 and u1, u2, . . . , un be the children of u0. Then, for every 0 ≤ j ≤ n,

D+(T)/Attr(uj) = ((D(Tu0)/Attr(u0)) ∪ D[p] ∪ ∪ni=1D(Tui)/Attr(ui))

+/Attr(uj) (2)Proof: Immediate from the definition of D(T ) since all the dependencies are local.

11

Lemma 5.2 For every derivation tree T with a leaf u of type Z, D+(T )/Attr(u) ∈ OI[Z].Proof: For a leaf u, let distanceT (u) be the distance between u and the root of T . We prove thelemma by induction on distanceT (u).Basis: For distanceT (u) = 0, T is the Z-derivation tree which only includes u. Therefore, D+(T)/Attr(u) =φ ∈ OI[Z].Induction hypothesis: Assume that for every derivation tree T with a leaf u of type Z s.t. distanceT (u) =k, D+(T)/Attr(u) ∈ OI[Z].Induction step: Let T be a derivation tree and u be a leaf of type Z in T s.t. distanceT (u) = k+1. Letu0 be the ancestor of u. Let p:Z0 → Z1Z2 · · ·Zn be the production applied at u0 and let u1, u2, . . . , un

be the children of u0. Thus, for some 1 ≤ j ≤ n, u = uj and Z = Zj . We have to show thatD+(T)/Attr(uj) ∈ OI[Zj ]. Since uj is a leaf in T , D+(Tu)/Attr(u) = φ. Using D+(Tu)/Attr(u) = φin (2) of Lemma 5.1 we get

D+(T)/Attr(uj) = ((D+(Tu0)/Attr(u0)) ∪D[p] ∪ ∪ni=1,i 6=jD

+(Tui)/Attr(ui))+/Attr(uj)

Since distanceTu0

(u0) = k, by the induction hypothesis R[Z0]def= D+(Tu0)/Attr(u0) ∈ OI[Z0]. By

Theorem 2.2, for every 1 ≤ i ≤ n, R[Zi]def= D+(Tui)/Attr(ui) ∈ IO[Zi]. The proof is completed by

noting that the algorithm of Section 5.1.1 adds the relation (1) to OI[Zj ].

Lemma 5.3 For every grammar symbol Z and R[Z] ∈ OI[Z] there exists a derivation tree T witha leaf u of type Z s.t. D+(T)/Attr(u) = R[Z].Proof: Let OIk[Z] denote the value of OI[Z] at the end of the k-th iteration of the algorithm ofSection 5.1.1. We proceed by induction on k.Basis: Clearly, for the derivation tree Tu which includes only u, D+(Tu)/Attr(Z) = φ = OI0[Z].Induction hypothesis: Assume that in the k-th iteration, for every grammar symbol Z and R[Z] ∈OIk[Z] there exists a derivation tree T with a leaf u of type Z s.t. D+(T)/Attr(u) = R[Z].Induction step: Let p:Z0 → Z1Z2 · · ·Zn be the production processed in the k + 1st iteration andlet 1 ≤ j ≤ n. Let R[Z] ∈ OI[Z], R[Zi] ∈ IO[Zi] and 1 ≤ j ≤ n. Let R[Zj ] = R[Z0] ∪D[p] ∪ ∪n

i=1,i 6=jR[Zi])+/Attr [Zj ] be the relation added to OIk[Zj ] in the k + 1-iteration to yield

OIk+1[Zj ]. By the induction hypothesis, there exists a derivation tree Tu0with a leaf u0 of type Z0

s.t. D+(Tu0)/Attr(u0) = R[Z0]. By Theorem 2.2, for every 1 ≤ i ≤ n, there exists a Zi-derivationtree Tui

s.t. D+(Tui)/Attr(ui) = R[Zi]. Also, let Tujbe the Zj-derivation tree which includes only

uj . Let Tujbe the derivation tree obtained by attaching Tu1

, Tu2, . . . , Tun

as children of u0 in Tu0.

By Lemma 5.1, D+(Tuj)/Attr(uj) = R[Zj ].

5.1.3 Complexity Analysis

We now derive an upper bound on the complexity of computing the OI relations which is similar tothe known bound on computing the IO relations (e.g. see [18]). We use the following notations: pis the number of productions, l is the maximal length of a production, z is the number of grammarsymbols, a = maxZ |Attr [Z]|, io = maxZ |IO[Z]| and oi = maxZ |OI[Z]|.

The initialization phase of the algorithm takes O(z) time. Since the algorithm terminates whenfor every production no relation is added, we conclude that the number of iterations is O(oi× z× p).

When a production p:Z → Z1Z2 · · ·Zn is processed, OI[j] is updated according to (1) for every1 ≤ j ≤ n. To update OI[j], at most ion−1 input/output relations are considered and at most oioutput/input relations. The cost of computing (1) is dominated by the cost of the transitive closureoperation which is O(|Attr [p]|3) = O((n + 1)3 × a3). Therefore, the complexity of updating OI[j] isO(ion−1×oi(n+1)3×a3) = O(iol−1×oi× l3×a3). Hence, the overall complexity of the algorithm is

O((oi× z×p)× l× (iol−1×oi× l3×a3)) = O(iol−1×oi2× z×p× l4×a3). Finally, since io, oi ≤ 2a2

,

the complexity of computing the OI relations is O(2a2×l × z× p× l4 × a3).

5.2 An Algorithm to Find the Circular Attributes

Given a production p:Z0 → Z1Z2 · · ·Zn, the IO and OI relations are used to find the set C[p] ofthe circular attributes. C[p] is the set of attributes Zj .a for which there exist R[Z0] ∈ OI[Z0] andR[Zi] ∈ IO[Zi], 1 ≤ i ≤ n s.t. Zj .a depends on itself in R[Z0] ∪D[p] ∪ ∪n

i=1R[Zi].Let us turn to apply the algorithm to the AG Figure 1.

12

1. Consider p1. The only R[S] ∈ OI[S] is R[S] = φ. For R[X] = {(X.a, X, d), (X.b, X, c)},R[X] ∈ IO[X]. Therefore, the attributes X.a, X.b, X.c and X.d which participate in a cyclein R[S] ∪D[p1] ∪ R[X] belong to C[p1]. Since C[p1] = Attr [p1], no attribute can be added toC[p1].

2. Consider p2. The only non-empty R[X] ∈ OI[X] is R[X] = {(X.c, X, a), (X.d, X, b)}. There-fore, C[p2] contains the attributes which participate in a cycle in R[X] ∪ D[p2], namelyC[p2] = {X.a, X.b, X.c, X.d}. Nothing can be added to C[p2].

3. Consider p3. The only non-empty R[X] ∈ OI[X] is R[X] = {(X.c, X, a), (X.d, X, b)}. There-fore, C[p3] contains the attributes which participate in a cycle in R[X] ∪ D[p3], namelyC[p3] = φ.

4. Consider p4. The only non-empty R[Y ] ∈ OI[Y ] is R[Y ] = {(Y.c, Y, a), (Y.d, Y, b)}. Therefore,C[p4] contains the attributes which participate in a cycle in R[Y ] ∪D[p4], namely C[p4] = φ.

Theorem 5.4 For every production p, C[p] = CAttr[p].Proof: Let p:Z0 → Z1Z2 · · ·Zn be a production. Let us show that C[p] ⊇ CAttr[p]. Let Zj .a ∈CAttr[p]. Then there exists a terminal tree T with a vertex u of type Zj s.t. u.a depends on itself inD(T ) and p is applied either at u or at its ancestor. The dependency of u.a on itself is also evident inD+(T)/Attr(u). Now, let u0 be the vertex in which p is applied and let ui, 1 ≤ i ≤ n, be the childrenof u0. Applying Lemma 5.1 to uj ← u, we conclude that u.a depends on itself in (2), implying thatu.a depends on itself in D+(Tu0)/Attr(u0) ∪ D[p] ∪ ∪n

i=1D+(Tui)/Attr(ui). Applying Lemma 5.2 to

Z ← Z0 and T ← Tu0, we conclude that R[Z0]

def= D+(Tu0)/Attr(u0) ∈ OI[Z0]. For every 1 ≤ i ≤ n,

applying Theorem 2.2 to Z ← Zi and u← ui, we conclude that R[Zi]def= D+(Tui)/Attr(ui) ∈ IO[Zi].

Therefore, Zj .a depends on itself in R[Z0] ∪D[p] ∪ ∪ni=1R[Zi]. Hence, Zj .a ∈ C[p].

Let us show that C[p] ⊆ CAttr[p]. Let Zj .a ∈ C[p]. Then there exist R[Z0] ∈ OI[Z0] and R[Zi] ∈IO[Zi] for 1 ≤ i ≤ n s.t. Zj .a depends on itself in R[Z0] ∪D[p] ∪ ∪n

i=1R[Zi]. By Theorem 2.2, forevery 1 ≤ i ≤ n, there exists a Zi-derivation tree Tui

s.t. D+(Tui)/Attr(ui) = R[Zi]. By Lemma 5.3,there exists a derivation tree Tu0

with a leaf u0 of type Z0 s.t. D+(Tu0)/Attr(u0) = R[Z0]. Let Tbe the derivation tree obtained by attaching Tu1

, Tu2, . . . , Tun

as children of u0 in Tu0and u be the

vertex in T which corresponds to Zj . By Lemma 5.1, u.a depends on itself in D+(T)/Attr(u), andtherefore it also depends on itself in D(T ). Since the underlying grammar is reduced, T can beexpanded into a terminal tree T ′. Finally, since D(T ) ⊆ D(T ′), u.a depends on itself in D(T ′).

The upper bound on the complexity of the process of finding C[p] is similar to that of thealgorithm of Section 5.1.1 to compute OI.

6 Finding the Circular Attributes Conservatively

In Section 5.2 an exact algorithm to find the circular attributes has been given. Next we presenta conservative polynomial algorithm to find the circular attributes. Our exact and conservativealgorithms are related in the same way that Knuth’s exact algorithm is related to his conservativealgorithm.

6.1 A Conservative Algorithm

The main idea is to develop summary output/input relation OI[Z] ⊆ Attr [Z]×Attr [Z] for every gram-mar symbol s.t. OI[Z] ⊇ ∪

R∈OI [Z]R. This is based on the reasonable assumption that the

summary output/input relation is simillar in different occurrences of Z. The algorithmstarts with OI[Z] = φ. In every iteration, one production p:Z → Z1Z2 · · ·Zn is processed. For every1 ≤ j ≤ n it adds to OI[Zj ] the dependencies in

(OI[Z] ∪D[p] ∪ ∪ni=1,i 6=jIO[Zi])

+/Attr [Zj ] (3)

Let AC[p] ⊆ Attr [p] be the attributes which participate in cycles in (OI[Z] ∪D[p] ∪ ∪ni=1IO[Zi]). In

the following theorem, we show that the algorithm is conservative.

13

Theorem 6.1 For every production p, AC[p] ⊇ CAttr[p].Sketch of Proof: First we need to show that Lemma 5.2 is also true for OI, i.e., for every derivationtree T with a leaf u of type Z, D+(T)/Attr(u) ⊆ OI[Z]. This observation and Theorem 2.1 yield theresult.

In the AG of Figure 1, each of the IO[Z] and OI[Z] contains only one non-empty relation.Therefore, the conservative and the exact algorithms yield the same sets of attributes. Let G′ =({0, 1, 2, 3}, E′) be the graph obtained from the one in Figure 4 by deleting the edge (2, 1). G′ does notcontain a Hamiltonian path and therefore X3.11 6∈ CAttr[p3]. However, OI[X3] = {(X3.11, X3.a1), (X3.12, X3.a2)}.Hence, X3.11 is erroneously detected as circular in p3.

6.2 Complexity Analysis

We now show that the complexity of computing OI relations is polynomial in the size of the inputAG. The initialization takes O(z) time. Since the algorithm terminates when for every productionno dependency is added and since the number of dependencies of every output/input relation is atmost O(a2), we conclude that the number of iterations is O(a2zp).

When a production p:Z → Z1Z2 · · ·Zn is processed, OI[j] is updated for every 1 ≤ j ≤ n.The cost of computing (3) is dominated by the cost of the transitive closure operation which isO(|Attr [p]|3) = O((n+1)3a3). Therefore, the complexity of updating OI[j] is O((n+1)3a3) = O(l3a3).Hence, the overall complexity of the algorithm is O((a2zp) × l × (l3a3)) = O(a5zpl4), which ispolynomial in the size of the AG.

6.3 More Accurate Conservative Algorithms

While our conservative algorithm is better than Farrow’s on AGs such as the one of Figure 1, itis inferior for some other AGs. For example, Farrow’s algorithm yields exact results for the AG ofFigure 6. For this AG, our conservative algorithm yields OI[X] = {(X.c, X.a), (X.d, X.b)} althoughno derivation tree can exhibit this relation. Therefore, AC[p3] = {X.a, X.b, X.c, X.d} although thisAG is non-circular.

p1: S → X{

X.a = X.cX.b = constant

}

p1: S → X{

X.a = constantX.b = X.d

}

p2: X → ǫ{

X.d = X.aX.c = X.b

}

Figure 6: An AG on which Farrow’s algorithm is superior

Lower uniform AGs are AGs for which all the IO relations are simultaneously exhibited on someof their derivation trees. Assume that an additional requirement is imposed, namely that the OIrelations are exhibited simultaneously on some derivation trees. For this subclass of lower uniformAGs it can be shown that our conservative algorithm is exact.

Our conservative algorithm can be combined with Farrow’s. The trivial way to do it is by report-ing circularity only for attributes which are detected as circular by both algorithms, i.e., attributesin M [p]∩AC[p]. A more accurate approach would modify the iteration of Farrow’s algorithm whenit processes a production p:Z → Z1Z2 · · ·Zn. The function Direct Mark would not change since ityields exact results for lower uniform AGs. However, the function Indirect Mark(p, (Z.a, Z.b)) wouldadd dependencies and attributes only if (i) they appear on paths from Z.a to Z.b, and (ii) both Z.aand Z.b participate in a cycle in OI[Z] ∪D[p] ∪ ∪n

i=1IO[Zi].

7 Conclusions

In this article several algorithms for finding the circular attributes were outlined. More work hasto be done to study the practicality of these algorithms. In [18, 3, 13] several heuristics to improve

14

the performance of Knuth’s exact algorithm were presented. These techniques may also be usedto improve our exact algorithm. The empirical results in [18] show that the size of the detailedinput/output relations is typically small in practice. It is interesting to study if the same holds fordetailed output/input relations.

Let p:Z0 → Z1Z2 · · ·Zn be a production. An attribute Zi.a ∈ Attr [p] is transitively circular ifthere exists a terminal tree T with a vertex u of type Zi s.t. u.a reflexively depends on an attributewhich appear on a cycle in D(T ) and p is applied either at u or at its ancestor. The problemof finding the transitively circular attributes is also important since if the functions defining thetransitively circular attributes are monotonic, then an iterative algorithm for attribute evaluation([12, 7]) would yield a unique least (greatest) fixed point. The problem of finding a superset of thetransitively circular attributes may be solved by finding which attribute may depend on a givencircular attribute.

The reduction presented in Section 4 does not use the full power of AGs since all the productionsare unit or ǫ productions. It is not clear whether a more careful reduction would provide a strongerlower bound on the problem of computing whether an attribute in a lower uniform AG is circular.

References

[1] A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1985.

[2] K. Barbar. Etude Comparative de Differentes Classes de Grammaires d’Attributs Ordonnees.PhD thesis, Universite de Bordeaux, 1982.

[3] P. Deransart, M. Jourdan, and B. Lorho. Speeding up circularity tests for attribute grammars.Acta Informatica, 21:375–391, 1984.

[4] P. Deransart, M. Jourdan, and B. Lorho. Attribute Grammars, Definitions Systems and Bibli-ography, volume 323 of LNCS, chapter I: Definitions and Main Results, pages 1–52. Springer-Verlag, 1988.

[5] J.M. Dill. A counter-example for showing the intrinsically exponential complexity of the circu-larity problem for attribute grammars. Journal of ACM, 36:92–96, 1989.

[6] J. Engelfriet and G. Filee. Passes and paths of attribute grammars. Information and Control,49(2):125–169, 1981.

[7] R.W. Farrow. Automatic generation of fixed-point-finding evaluators for circular but well-defined attribute grammars. In SIGPLAN ’86 Symposium on Compiler Construction, pages85–98, 1986.

[8] M.R. Garey and D.S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

[9] M. Jazayeri. A simpler construction for showing the intrinsical exponential complexity of thecircularity problem for attribute grammars. Journal of ACM, 28(4):715–720, 1981.

[10] M. Jazayeri, W.F. Ogden, and W.C. Rounds. The intrinsic exponential complexity of thecircularity problem for attribute grammars. Communications of the ACM, 18(12):696–706,1975.

[11] L.G. Jones. Efficient evaluators of circular attribute grammars. ACM Transactions on Pro-gramming Languages and Systems, 12(3):429–462, 1990.

[12] L.G. Jones and J. Simon. Hierarchical VLSI design systems based on attribute grammars. InACM Symposium on Principles of Programming Languages, pages 58–71, 1986.

[13] M. Jourdan and D. Parigot. More on speeding up circularity tests for attribute grammars.Rapport RR-828, INRIA, Rocquencourt, 1988.

[14] U. Kastens. Ordered attribute grammars. Acta Informatica, 13(3):229–256, 1980.

[15] U. Kastens, B. Hutt, and E. Zimmerman. GAG: a Practical Compiler Generator, volume 141of LNCS. Springer Verlag, 1982.

[16] D.E. Knuth. Semantics of context free languages. Mathematical Systems Theory, 2(2):127–145,1968.

15

[17] D.E. Knuth. Semantics of context free languages. Mathematical Systems Theory, 5(1):95–96,1971. Errata.

[18] K.J. Raiha and M. Saarinen. Testing attribute grammars for circularity. Acta Informatica,17(2):185–192, 1982.

[19] S. Sagiv, O. Edelstein, N. Francez, and M. Rodeh. Resolving circularity in attribute grammarswith applications to data flow analysis. In ACM Symposium on Principles of ProgrammingLanguages, pages 36–48, 1989.

16