Abstract
The purpose of this paper is twofold. First we present a denotational
semantics of attribute grammars(AGs) by using Cardelli's record calculus.
The denotational semantics is simple and natural. In our semantics,
an attributed tree is represented by nested records to preserve the
structural information of the attributed tree, while in traditional
denotational semantics AGs are formalized by either valuation mapping
from attributes (often in the root) to their values or mapping from
inherited attributes to synthesized attributes in the root. It is
a positive characteristic of our semantics to deal with attributed
tree as AG's semantics rather than attribute valuation. For the purpose
of describing structure-oriented software development environments,
many computational models based on AGs have already been proposed.
These computational models are usually extended so as to deal with
tree transformation. We believe that our semantics can be a good
formal basis to define these computational models. To show this,
we formalize OOAG(Object-Oriented AGs) and higher order AGs(HAGs)
by extending our denotational semantics of AGs. This is the second
purpose of this paper. Both of them are computational models to deal
with tree transformation depending upon attribute values. As the
result of these formalizations, we can formally discuss the differences
between OOAG and HAGs. For example, we show that tree transformation
in OOAG is modeled as a function to determine the next state, while
that in HAGs is just a static tree construction. This paper is the
revised English version of Ättribute Grammars as Record Calculus"
(Technical Report No.93TR-0047), which is written in Japanese.
Users
Please
log in to take part in the discussion (add own reviews or comments).