On Defining Semantics by Means of Extended Attribute Grammars

Abstract

The possibilities for defining predicate transformers, denotational semantics, and operational semantics by means of extended attribute grammars are treated. The approach to operational semantics consists of a set of attribute grammar rules that specifies the possible transformations upon a given program. A proposal for defining the domains of an attribute grammar within the formalism is given. It is also shown how an attribute grammar may be reformulated as a tree rewriting system. Finally an efficient evaluator that works for all attribute grammars (including some circular ones) is described. This evaluator constructs during a left-to-right scan of a linear representation of the parse tree (a right-parse) a directed (acyclic) graph that represents the values of the attributes at the root of the parse tree. The parse tree itself need not be constructed. During a (recursive) scan of this graph the attribute values may be evaluated.