The Intrinsically Exponential Complexity of
the Circularity Problem for Attribute Grammars

Attribute grammars are an extension of context-free
grammars devised by Knuth as a mechanism 
for including the semantics of a context-free language
with the syntax of the language.  The circularity 
problem for a grammar is to determine whether the semantics
for all possible sentences (programs) in 
fact will be well defined.  It is proved that this problem
is, in general, computationally intractable. 
 Specifically, it is shown that any deterministic algorithm
which solves the problem must for infinitely 
many cases use an exponential amount of timen improved
version of Knuth's circularity testing algorithm 
is also given, which actually solves the problem within exponential time.

CACM December, 1975

Jazayeri, M.
Ogden, W. F.
Rounds, W. C.

attribute grammars, circularity problem, context-free
grammars, computational complexity, exponential 
time, semantics

4.12 5.25

CA751204 JB January 5, 1978 4:38 PM

2703	4	2703
2703	5	2703
2703	5	2703
2703	5	2703
2886	5	2703