Minimizing the Number of Evaluation Passes for Attribute Grammars
Kari‐Jouko Räihä, Esko Ukkonen · SIAM Journal on Computing · 1981
The problem of constructing multi-pass evaluators for attribute grammars is studied. We show that the construction algorithm used heretofore can in the worst case produce evaluators which perform $2n - 1$ passes over the parse tree, where n is the minimum number of passes required. Furthermore, the problem of constructing an optimal evaluation order is shown to be NP-complete. We then develop a new characterization for attribute grammars evaluable in passes. It can be directly applied as an efficient membership test. Finally, the characterization is used for deriving a polynomial time construction algorithm for a large subclass of pass-oriented attribute grammars. The subclass is argued to be of practical importance.