Algorithm to Find Minimal Sequences of Pass Directions for Attribute Grammars

摘要

A polynomial time algorithm that delivers a shortest sequence of pass directions for several simple multipass grammars is discussed. It starts from a given sequence of pass directions and tries to find a shorter one by considering possible distributions of the attributes over the passes and crossing out empty passes. An extension of the algorithm also reconsiders and possibly changes directions in order to find passes that become empty. The resulting sequences of pass directions are minimal with respect to the subsequence ordering, i.e., no subsequence exists for which an associated distribution of the attributes over the passes meets the simple multipass requirements.