Attribute storage optimization by stacks (Q1121674)

Storage optimization is considered for evaluators of simple multi-visit, or (\(\ell\)-)ordered, attribute grammars. A necessary and sufficient condition is formulated which has to be satisfied by such an evaluator to enable it to store the instances of a given attribute on a global stack. A simple algorithm is given that decides this condition in polynomial time. A similar algorithm can be used to decide whether the instances of the attribute can be stored in a global variable. These algorithms are static, i.e., they are used at evaluator construction time.