Testing attribute grammars for circularity

Summary The problem of deciding whether a given attribute grammar is noncircular is known to require exponential time for infinitely many grammars. Here the time requirement of a simple circularity test is analyzed. It is shown that the reason for the exponential time requirement is the number of graphs in a collection formed for every nonterminal. By practical experiments it is argued that for real grammars the number is very small. Therefore it is feasible to actually perform the circularity test in practice. Different techniques to improve the implementation of the circularity test are discussed, too.