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