Using computation sequences to define evaluators for attribute grammars

Abstract

An evaluator for an attribute grammar takes a derivation tree as input and produces a computation sequence for it as output. We give a simple but general construction of an evaluator for any well-defined attribute grammar and we prove its correctness. Evaluators for seueral subclasses of attribute grammars can be constructed by changing a preprocessing stage of the evaluator.