Finding circular attributes in attribute grammars

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. © 1999 ACM.