A Practical Attribute Grammar Circularity Test

Abstract

Efficient implementations for two optimisations to Knuth's attribute grammar circularity test are described. A new method for eliminating useless visits to productions is introduced. This improves upon a somewhat weaker mechanism introduced previously by Deransart et. al. Data structures and algorithms for graph covering and elimination of redundant unions are discussed and proven correct.