Conditional Evaluation in Simple Multi-Visit Attribute-Grammar Evaluators

Attribute grammars are a formalism for specifying computations on context-free languages. Due to the nonstrictness of the if constructs in attribution equations, it is possible to avoid evaluating certain attribute instances in a syntax tree. A dynamic evaluator can easily avoid such useless computations with a demand-driven approach. However, dynamic evaluators are not efficient because they need to keep the attribute dependence graph during evaluation, and they need to decide an evaluation order for each syntax tree. In contrast, a visit-oriented (static) evaluator can carefully re-arrange the evaluation order and still avoid unnecessary computations. We propose such a technique in this paper. Key Words: attribute grammars, conditional evaluation, ordered attribute grammars, simple multi-visit attribute grammars - 2 - I. Introduction Since their introduction in 1968 (Knuth, 1968), attribute grammars have attracted much research interest. Attribute grammars are a very convenient an..