\section{Attributed Grammars}

The major benefits of language-sensitive tools as outlined in section \ref{potent}
involve the construction of semantic analysers for the languages under consideration.
The most widespread approaches for this task are the coding of semantic actions and the
formalisation of semantics within the language2s grammar, mainly in the form of attributed
grammars. Both methods use an abstract syntax tree (henceforth abbreviated
by `AST') constructed by a parser.
                                                 
\begin{itemize}
\item {\bf Semantic actions:} Every change of a design object implies the call
of imperative routines that inspect and update the altered context.
Every such routine must have a corresponding ``inverse'' one. The main problem
concerning this approach is to determine the range of changes after the
modification of a program.
Advantageous is the use of global data structures (symbol tables), that
can be read and updated being at an arbitrary node of the syntax tree.
Therefore, the semantic action approach is very efficient concerning space.  
For compiler generating systems or, more generally for all systems that work
on complete source objects and do not need incremental updates, this approach
is still fruitful. 

\item {\bf Attributed Grammars:} They describe properties of a language
by means of {\em semantic equations}. Design objects are represented as attributed
syntax trees.
As opposed to the semantic action approach, the changes needed in case of
a program modification are given imlipicitly in the formalism. The design of
attributed grammars must therefore not consider the internal representation
of a design object. Obtaining a new, consistently attributed tree after a modification
has taken place is not a matter of design, but can be done automatically by
means of an incremental algorithm.   
Various procedures for this task will be described in section
\ref{ag-eval}.
Summarizing, there is no need to consider procedural aspects (see 
section~\ref{ag} and \cite{kn,knc,r83}). 

A major drawback of attributed grammars is their rather tremendous space
consumption. This is due to the fact that every node  lieing on the path
between the node of information creation and the node of information use must
store all the propagated information\footnote{ This problem
seems to be overcome by means of {\em remote attribute updating} \cite{rmt}.
The {\em synthesizer generator} permits a restricted form of such remote access
(compare Section \ref{sgen}).}.
This leads to a great redundance in the storage of information, although the
fact that various nodes share common attribute values alleviates this problem.
\end{itemize}
                
\subsection{On Language Specification: Definitions and Examples}
\label{ag}
                          
\subsubsection{Attributed Grammars and other Specification Formalisms}

The syntax of languages describing computations usually is specified in terms of a
context free grammar, however, the semantics is given by informal texts.
CFG's are used, since they can be parsed in at most polynomial time (as opposed
to context-sensitive grammars). Furthermore, CFG's are well understood. The
disadvantage of CFG's is their unability to describe semantic properties of
such languages.
Therefore, attempts have been made, to catch static semantics with
formalisms which are based on CFG's but have more descriptive power.
 
{\em Definite Clause Grammars} \cite{snt} augment CFG's with additional
test procedures and are therefore very similar to attributed grammars. {\em
Augmented Transition Networks} \cite{ric} are essentially finite automata
with additional storage and function calls.  

Another approach is chosen within the IPSEN project \cite{es} where the
language description is not based on CFG's but on {\em attributed graph
grammars}. Graph grammars are a very powerful and convenient description
tool that gives rise to numerous possibilities to integrate the language
description with other design levels \cite{es,ens}.
But for the time being there are no automatic systems processing attributed
graph grammars. The entire IPSEN system is coded manually, which is an
unsuitable approach for evolving environments.

The use of attributed grammars for the specification of languages
has some important benefits:
\begin{itemize}
\item It is guided by classic compiler techniques, i.e.\ the attribution of syntax
	trees.
\item Important properties like noncircularity and consistency are provable.
\item An attributed grammar constitutes a formal definition of syntax {\em and}
	semantics of a language.  
\item An ``incremental'' workstyle is possible: after specifying basic language
	properties, additional concepts can be gradually included.
\item Attribute evaluation strategies can be generated automatically.
\item Powerful generators that create compilers, interpreters, editors and other
	tools by means of attributed grammars are available.
\end{itemize}

Some well known compiler generators based on attributed grammars are GAG
\cite{kaz}, MUG1 \cite{wil} and MUG2 \cite{grw}\footnote{ This generators
accept ordered, LL-attributed and multi-pass grammars respectively (the
various classes are explained in section \ref{subclasses}).}. MUG2 is
designed to permit specifications of optimizing compilers.

Compared with the task of specifying a compiler, an editor specification
is different in several respects. On the one hand, there is no generation
of executable code (intermediate code). On the other hand there must be
some handling of situations in which a required substructure of a syntax
tree is not yet inserted. Consistent computing of all
attribute values must be ensured as well in such cases. The impacts of these
conditions on an attributed grammar are described in section \ref{ssl}.


\subsubsection{Basic Definitions}

An attributed grammar is a CFG in which every grammar symbol may have associated
sets of {\em inherited} and {\em synthesized} attributes. These sets are
disjoint, i.e.\ no individual attribute can be both synthesized and inherited.
A function of the language defined by the CFG into a {\em semantic
domain}\footnote{ The semantic domain may simply consist of truth values, but
it could also contain the set of all executable programs in a target language.}
is specified by means of these attributes (see \cite{kn} for the original
definition).   

For every production $x_{0} \rightarrow x_{1}\ldots x_{n}$ of the grammar,
semantic rules (attribute computation rules) of the form
\begin{quote} 
$a(x_{i}) = f(b_{1}(x_{i_{1}}),\ldots ,b_{k}(x_{i_{k}}))$ 
\end{quote}
associated with this individual production are defined.
All attributes $a, b_{1}, \ldots b_{k}$ have associated domains (types)
$D_{a}, D_{b_{1}} \ldots D_{b_{k}}$ and $f$ is a mapping of
$D_{b_{1}} \times \cdots \times D_{b_{k}}$ into $D_{a}$. If $i$ equals $0$,
the attribute is synthesized, otherwise it is inherited\footnote{ Every
symbol on the left side (lhs) may derive attributes from its own attributes,
every symbol on the right side (rhs) may inherit attributes of other
rhs-symbols (from ``brothers'').} \cite{c}. For all inherited attributes
of the symbols $x_1,\ldots x_n$ and all synthesized attributes of $x_0$,
exactly one semantic equation must be associated to the related production.
For each appearance of a nonterminal in a syntax tree, a value is selected
from the attribute's domain according to these syntactic rules. 
If $k$ equals $0$, $f$ is a constant function.

Inherited attributes are used to determine the meaning of a symbol with respect
of the symbol's context. Most usually, the definition of an identifier
is an inherited attribute for its applied occurence. Synthesized attributes
are used to determine the meaning of a construct by using the meanings of its
parts. The value or type of an arithmetic expression is a common example for
this. Clearly, the start symbol of the grammar may not possess inherited
attributes and the terminal symbols do not have synthesized attributes.
Attributes can be very complex objects, e.g., symbol tables.       

Furthermore attributed grammars may contain {\em semantic conditions}, i.e.,
mappings from attribute domains into truth values. These mappings do not belong
to a grammar symbol, but are associated with productions. According to the
original definition of attributed grammars \cite{kn}, the following condition
applies: if all mappings of this kind yield the value    
TRUE\footnote{ Equivalently, a distinguished attribute of the start symbol can
be used, the value of this attribute must then equal TRUE.}, the string
derived by the CFG pertains to the
language defined by the attributed grammar (i.e., the string is in L(AG)).

With respect to our approach, the set of programs generated by a CFG is not
restricted by attribute values. Semantic conditions are used merely to compute
values of local attributes, which are no truth values but belong to an
enumeration of error types for instance. This approach enables the
distinction between different errors.
\\[2mm]
An attributed grammar must clearly submit to the condition stating that every
attribute value in an arbitrary tree can be computed in an unique way. In
particular, ciclic dependencies between attribute values must not exist. 

Every set of production applications induces a nonlinear equation system.
The unique computability of all attribute values is equivalent to the
condition that every such equation system has exactly {\em one} solution (and
all attribute values belong to their domaines).
\\[2mm]
Applications areas of attributed grammars, besides programming language
semantics, are natural language parsing
and systems for the realization of semantic preserving transformations on
various languages. Pattern recognition \cite{nie} is a less typical
application area.

In connection with database programming, Niemi \cite{nii} has specified a
multi-level database application whose architecture is oriented towards the
ANSI/\-X3/\-SPARC proposal \cite{tsk}. Within this architecture the mappings
between the individual levels are defined by means of an attributed grammar.   
A proposal of Ridjanovic and Brodie \cite{rib} tries to specify integrity
constraints in the context of semantic data models by attributed
grammars.\footnote{ Both approaches concern specific applications.
Since our approach is to supply a tool tool that is independent of the
application, they are not investigated any further.}


\subsubsection{Examples}
\label{ag-ex}
Subsequently, three characteristic examples of the use of attributed grammars
for the analysis of programs are given. All examples employ EBNF,
semantic equations and conditions are included in ``[...]''. Thereby,
indices as in ``$stmt_{i}$'' denote the i-th occurence of a production's symbol,
whereas the attributes themselves are denoted like record fields.

The examples show that the attribution of a grammar is decomposable into three
tasks: the creation of attribute values, the distribution (i.e., the control
of the information flow), and the use of the values in order to test contextual
constraints.
                                                             
Dependency graphs for typical parses are given for two of the examples.
Dependency graphs consist of labeled nodes representing attribute instances
and directed edges (a,b), whenever a is used directly for the computation of b.
Clearly, the considered grammar is noncircular iff none of the dependency
graphs generated by the grammar contains a cycle. This means that, if none of
the attributes appears in its own transitive closure, the partial order given
by the binary relation can be embedded into a total order. 

Therefore it suffices to construct a binary relation using all attribute
equations and to sort this relation topologically in order to test
noncircularity,.
If the topologic sort algorithm fails, the grammar contains a cycle.

 
\paragraph{Enforcing Declarations}
\label{ag-decl-ex}

In this section, a small grammar is defined, which is suited to check two
contextual constraints: Every applied variable must be defined and every
variable must be defined only once.

The grammar includes two attribute types, {\em id} and {\em env}. {\em id}
denotes a unique representation for each identifier. {\em env} denotes a list
of these representations. {\em env} is a synthesized attribute for
{\em Decl\_List} and an inherited one for {\em Stmt} and {\em Stmt\_List}.
The meaning of the nonterminal {\em Exp} is of no importance here.
\begin{small}
\begin{itemize}
\item[] Program ::= $\;$ Decl\_List {\bf begin} Stmt\_List {\bf end}
\subitem \hspace{18mm}[Stmt\_List.env = Decl\_List.env]
                                         
\item[] Decl\_List ::= $\;${\bf declare} Id            
\subitem \hspace{18mm}[Decl\_List.env = \{Id.id\}] 
                               
\item[]  \hspace{18mm} $|$ {\bf declare} Id Decl\_List 
\subitem \hspace{18mm}[Decl\_List$_1$.env = \{Id.id\} 
				$\cup$  Decl\_List$_2$.env]  
\subitem \hspace{18mm}[check: Id.id $\not\in$ Decl\_List$_2$.env]  

\item[] Stmt\_List ::= $\;$Stmt
\subitem \hspace{18mm}[Stmt.env = Stmt\_List.env]

\item[]  \hspace{20mm} $|$ Stmt Stmt\_List 
\subitem \hspace{18mm}[Stmt.env = Stmt\_List$_1$.env]
\subitem \hspace{18mm}[Stmt\_List$_2$.env = Stmt\_List$_1$.env]

\item[] Stmt ::= $\;$Id {\bf :=} Exp                    
\subitem \hspace{18mm}[check: Id.id $\in$ Stmt.env]
\end{itemize}
\end{small}
The flow of information within an attributed tree is demonstrated by means
of a small program example and the appropriate dependency graph.
\begin{quote}
{\bf declare} x {\bf begin} x {\bf :=} $<$exp$>$ {\bf end}
\end{quote}
The dependency graph is shown in figure~\ref{declare}.
\begin{figure}
\begin{center}              
\setlength{\unitlength}{0.7mm}
\begin{picture}(140,100)
\put(0,0){\framebox(140,100){}}
\put(55.3,89.7){\framebox(21.3,5.3)[]{Program}}
\put(18,71){\framebox(29.3,5.3)[]{Decl\_List}}
\put(92.7,71){\framebox(26.7,5.3)[]{Stmt\_List}}
\put(12.7,47){\framebox(21.3,5.3)[]{declare}}
\put(44.7,47){\framebox(8,5.3)[]{Id}}
\put(100.7,47){\framebox(13.3,5.3)[]{Stmt}}
\put(98,23){\framebox(8,5.3)[]{Id}}
\put(122,23){\framebox(10.7,5.3)[]{Exp}}
\put(49.3,72.3){env}
\put(84,72.3){env}
\put(92,48.3){env}
\put(54,48.3){id}
\put(91.3,24.3){id}
\put(108.7,9.7){check}
\put(56,54.3){\vector(-1,4){4}}
\put(58.3,74.3){\vector(1,0){24}}
\put(87.7,71.7){\vector(1,-2){9}}
\put(93.7,23.7){\vector(4,-3){13.3}}
\put(113.7,31.7){\vector(0,-1){16}}
\put(113.7,31.7){\line(-1,1){16.3}}
\end{picture}
\caption{Dependency graph for the enforcement of declarations}
\label{declare}
\end{center}
\end{figure}
Note that the information flow always has the same direction in this
dependency graph. A grammar
generating dependency graphs of this type is called {\em L-attributed}
(see section \ref{subclasses}). The semantic condition {\em check} can use
arbitrary attributes of nonterminals participating in the respective production.


\paragraph{Enforcing Initializations}
\label{ag-ex-init}

The next example specifies the obligation to initialize a variable before
using it on the right side of an assignment. This example stems from dataflow analysis
and is considerably more difficult than its predecessor, even though only a
very simple case is considered. Furthermore, as mentioned earlier, proper
initialization of variables is generally undecidable.

To denote the variables which have been initialized up to the current statement,
a set valued attribute {\em init} attached to every expression is
needed. The gathering and distribution of information is accomplished by
synthesized attributes attached to {\em Stmt} and {\em Stmt\_List} of the
same type and by an inherited attribute {\em init\_in}.
 
In connection with the example of section~\ref{ag-decl-ex}, the following
grammar sketches a possible procedure (since the information is generated
and used in the derivation tree dominated by {\em Stmt\_List}, only the
subtree rooted at {\em Stmt\_List} is displayed):
\begin{small}
\begin{itemize}
\item[] Program ::= $\;$Decl\_List {\bf begin} Stmt\_List {\bf end}
\subitem \hspace{18mm}[Stmt\_List.init\_in = \{\}]

\item[] Stmt\_List ::= $\;$Stmt
\subitem \hspace{18mm}[Stmt.init\_in = Stmt\_List.init\_in]
\subitem \hspace{18mm}[Stmt\_List.init = Stmt.init]

\item[] \hspace{20mm}  $|$ Stmt Stmt\_List 
\subitem \hspace{18mm}[Stmt.init\_in = Stmt\_List$_1$.init\_in]
\subitem \hspace{18mm}[Stmt\_List$_1$.init = Stmt\_List$_2$.init]
\subitem \hspace{18mm}[Stmt\_List$_2$.init\_in = Stmt.init]

\item[] Stmt ::= $\;$Id {\bf :=} Exp                    
\subitem \hspace{18mm}[Stmt.init = Stmt.init\_in $\cup$ \{Id.id\}]
\subitem \hspace{18mm}[Exp.init = Stmt.init\_in]

\item[] Exp ::= Id
\subitem \hspace{18mm}[check: Id.id $\in$ Exp.init]
\end{itemize}
\end{small}
The existence of constants is ignored for reasons of simplifications. Taking
them into account, the test-expression of the last production had to check
first whether {\em Id.id} is a variable or a constant.

Example:
\begin{quote}
{\bf begin} \hspace{2mm} x {\bf :=} $<$exp$>$ \hspace{2mm} y {\bf :=} x \hspace{2mm} {\bf end}
\end{quote}
The dependency graph enforcing proper initializations is shown in
figure~\ref{init}. 
\begin{figure}
\begin{center}              
\setlength{\unitlength}{0.7mm}
\begin{picture}(140,100)
\put(0,0){\framebox(140,100){}}
\put(46,92){\framebox(26.7,5.3)[]{Stmt\_List}}
\put(78,70.7){\framebox(26.7,5.3)[]{Stmt\_List}}
\put(27.3,70.7){\framebox(13.3,5.3)[]{Stmt}}
\put(92.3,49.3){\framebox(13.3,5.3)[]{Stmt}}
\put(100.7,28){\framebox(10.7,5.3)[]{Exp}}
\put(15,49.3){\framebox(8,5.3)[]{Id}}
\put(40.7,49.3){\framebox(10.7,5.3)[]{Exp}}
\put(10.7,72.7){init\_in}
\put(44,72.7){init}
\put(60,72.7){init\_in}
\put(108,72.7){init}
\put(30,92){init\_in}
\put(74,92){init}
\put(71.3,28){\framebox(8,5.3)[]{Id}}
\put(80.7,30){id}
\put(107.3,6.7){\framebox(8,5.3)[]{Id}}
\put(55,51.3){init}
\put(117,30){init}
\put(85.7,8.7){check}
\put(75,51.3){init\_in}
\put(109,51.3){init}
\put(26.3,51.3){id}                   
\put(11,93.3){\vector(1,0){13.3}}
\put(3,92){\{\}}
\put(34.3,91.3){\vector(-1,-1){14.7}}
\put(110.3,76.7){\vector(-2,1){29}}
\put(118.7,8.7){id}
\put(41.7,65.3){\vector(1,2){2.7}}
\put(44.3,62.7){\vector(1,2){4}}
\put(62.3,81.3){\vector(1,-2){2.7}}
\put(67.7,70){\vector(1,-1){14.7}}
\put(93,0.7){\vector(-1,2){2.7}}
\put(111.7,54.7){\vector(0,1){15.3}}
\put(109,43.3){\vector(1,2){2.7}}
\put(111.7,40.7){\vector(1,2){3.7}}
\put(92.7,17.3){\vector(-1,-2){2.7}}
\put(52.7,38){\vector(1,2){5.3}}
\put(47,76){\line(1,2){2.7}}
\put(49.7,81.3){\line(1,0){12.7}}
\put(17.3,70.7){\line(-4,-5){8}}
\put(9.3,60){\line(0,-1){22}}
\put(9.3,38){\line(1,0){43.3}}
\put(23.3,65.3){\line(-1,2){2.7}}
\put(44,62.7){\line(-1,0){14.7}}
\put(23.3,65.3){\line(1,0){18.7}}
\put(28.7,62.7){\line(-1,-3){2.3}}
\put(108.7,43.3){\line(-1,0){24}}
\put(84.7,43.3){\line(-1,2){2.7}}
\put(111.3,40.7){\line(-1,0){26.7}}
\put(84.7,40.7){\line(-1,-5){1.3}}
\put(93,0.7){\line(1,0){24}}
\put(117,0.7){\line(1,2){2.7}}
\put(79,48.7){\line(-1,-1){13.3}}
\put(65.7,35.3){\line(0,-1){13.3}}
\put(65.7,22){\line(1,0){48}}
\put(113.7,22){\vector(1,2){2.7}}
\put(92.7,17.3){\line(1,0){22.7}}
\put(115.3,17.3){\line(1,2){5.3}}
\end{picture}     
\caption{Dependency graph enforcing proper initializations}
\label{init}
\end{center}
\end{figure}
                 
Note: By means of distinguished initialization sections for each block,
as proposed by Dijkstra \cite{dj}, detection of uninitialized variables
would become very easy. Thereby, only locally defined and locally initialized
variables would have to be compared. Dealing with contemporary programming
languages, the (suspected) non-initialization of variables cannot be treated
as an error but merely as a program anomaly.

\paragraph{Program Verification}
\label{ag-ex-ver}

The last example briefly describes the way that an attributed grammar could be used 
to express the required conditions for the verification of programs. 

The following difficulty should not be withheld: The formalism does indeed
furnish a convenient tool to express verification conditions. However, the
required decision procedures must be implemented as an external theorem
prover.  

In a formalism oriented towards Dijkstra's {\em weakest predicate calculus}
\cite{dj}, but in a different notation (the notation of the substitution is
adopted from \cite{a}), the {\em partial} (there is no loop {\em variant})
correctness of programs is proven. Consequently, statements are considered as
predicate transformers.

{\em pre} and {\em post} are synthesized and inherited attributes of
{\em Stmt} respectively, {\em exp} denotes synthesized attributes of
{\em Cond}, {\em Exp} and {\em Assertion}. All attributes are predicates.
\begin{small}
\begin{itemize}
\item[] program ::= Assertion{\bf [}stmt{\bf ]}Assertion
\subitem \hspace{18mm}[Stmt.post = Assertion$_2$.exp]
\subitem \hspace{18mm}[check: Assertion$_1$.exp $\Rightarrow$ Stmt.pre]
\item[] Stmt ::= $\;$Id {\bf :=} Exp
\subitem \hspace{18mm}[Stmt.pre = {\bf [}Id.id := Exp.exp{\bf ]}Stmt.post]
\item[] Stmt ::= $\;${\bf while} Cond {\bf invariant} Assertion {\bf do} Stmt
\subitem \hspace{18mm}[Stmt$_1$.pre = Assertion.exp]
\subitem \hspace{18mm}[Stmt$_2$.post = Assertion.exp]
\subitem \hspace{18mm}[check: (Assertion.exp $\wedge$ $\neg$ Cond.exp)
$\Rightarrow$ Stmt$_1$.post]  
\subitem \hspace{18mm}[check: (Assertion.exp $\wedge$ Cond.exp)
$\Rightarrow$ Stmt$_2$.pre]
\end{itemize}
\end{small}                                               
Additional material to this topic can be found in \cite{ger}.
                                                                    
\subsubsection{Evaluation Strategies}
\label{subclasses}
Since it requires exponential time to prove that an attributed grammar is
noncircular, several subclasses permitting only restricted kinds of attribute
dependencies were developed. Membership tests for these restricted classes
can be carried out in polynomial or even linear time.
Furthermore, efficient attribute evaluation algorithms are available.

The possible structures of attributed grammars should not be restricted
too much since clearness, simplicity and ease of manipulation could be
lost\footnote{ A result given in \cite{mei} indicates an inherent exponential
blow-up of the size of an arbitrary grammar when transformed into a grammar
containing only synthesized attributes.}.
However, all subsequently mentioned classes have the same descriptive power
and canonical methods for the transformation of arbitrary noncircular grammars into
grammars of a more restricted class are available \cite{e}.  
\\[1.5mm]
\label{ag-eval}
Each attribute evaluation algorithm must handle the dependency relations
between attributes in some way. Many grammar classes are defined with respect
to an applicable evaluation algorithm. Consequently, these classes are
presented together with an outline of their evaluation algorithms.
A special treatment is given to incremental versions of the algorithms,
since changes of attribute values may take place at arbitrary nodes of the
attributed tree within a language sensitive editor. Usually, not all
attributes receive new values during a change. Therefore, only actually
affected attribute values should be recomputed and there should be an efficient
detected way of detecting them. This is opposed to systems computing
always the entire attributed tree.
Efficient (asymptotically optimal) evaluation strategies have in common that
they respect the partial order given by the dependency graph. An algorithm
cannot be optimal otherwise.
\begin{quote}  
{\bf Example:} Let \{$(b,a),(c,a),(b,c)$\} be the dependency graph. If $b$
changes its value, $a$ and $c$ must be recomputed. If $a$ is recomputed first
(with the new value of $b$) and then $c$, $a$ must be recomputed again with
the new value of $c$. 
\end{quote}
Now some well known simple classes together with their evaluation strategies
and the related incremental versions are presented\footnote{ A precise
description of the algorithms is too space consuming to be presented here.
The interested reader is referred to the literature given in the appendix
(e.g. \cite{e,r83,rt88}).}.
For the latter, let
{\em r} be the ``point of change'' from where updates must be propagated.

\vspace*{-3mm}

\subparagraph{S-AG}
They contain only sythesized attributes. Consequently, a derivation tree
generated by an S-AG can be evaluated in {\em one} pass bottom-up. This method
can easily be implemented as a recursive function for the computation of the
tree's root attributes. The algorithm descends down the tree for each
attribute function requiring attributes of its sons as arguments. An
{\em incremental} version only has to follow the path from the root to the node
{\em r} (attributes on other paths have unchanged values) and after reaching
{\em r} proceeds with the subtree rooted at {\em r} in the non-incremental
fashion.

\vspace*{-3mm}

\subparagraph{L-AG}
They contain both synthesized and inherited attributes. The derivation trees
can be evaluated in {\em one} pass {\em top-down left-to-right\/}. 
Thereby, every node (except for the leaves) is visited twice: the
inherited attributes are computed top-down, the synthesized ones bottom up.
Attributes must not depend on an attribute
of a {\em right} brother or on a synthesized attribute of the father.
Otherwise not all attributes could be evaluated with this method.
If the CFG (without attributes) is LL(k), the grammar is called
{\em LL-attributed}. The parse tree including all attributes is
then computable in one pass. {\em Incremental} updates are executed in the same
manner but they start with {\em r} instead of the root and proceed as long
as newly computed attribute values are not equal to the old ones.

\vspace*{-3mm}

\subparagraph{m-PAG}
Derivation trees can be evaluated in {\em m} passes {\em left-to-right\/}.
The procedure described for the L-AG's is carried out {\em m} times. Every
argument of an attribute that is computed in the $i^{th}$ pass must
have been computed in the $i-1^{th}$ pass at the latest.
Consequently, the set of all attributes is partitioned. The design of an
m-PAG must take care of a consistent organization of this partition.
The {\em incremental} version is a genuine extension of the incremental algorithm
for the L-AG's. 

\vspace*{-3mm}

\subparagraph{n-APAG}
Derivation trees can be evaluated in {\em n} pas\-ses alternating
{\em left-to-right/\-right-\-to-\-left\/}. APAG's represent an alternative to
{\em m}-PAG's which is more flexible. Every second pass is executed in reverse
order and therefore, attributes which depend on right brothers can be computed
more easily. As regards the {\em incremental} algorithm, the adaptation is natural
again. 

Obviously, the grammars mentioned constitute a hierarchy. Each class of
this hierarchy is defined by a specific pass structure of the evaluation
algorithm. There are other grammar classes that do not stick to a fixed
number of passes or a fixed order of visiting nodes but nevertheless have
very efficient evaluation algorithms.  

Besides the efficiency of evaluation strategies, the question of automatic
generation of attribute evaluators is of central importance. In the next
two sections, grammar classes with efficient membership tests, efficient
generation of evaluators, and efficient evaluation properties are presented.

\vspace*{-2mm}

\paragraph{Absolutely Noncircular Grammars}
\label{sag}
Absolutely noncircular grammars were introduced by Kennedy and Warren
\cite{kew} to simplify the construction of a distributed attribute
evaluator.
This evaluator consists of a collection of finite automata.  

An attributed grammar is absolutely noncircular, iff the following condition
holds for all nonterminals {\em r\/}: superimposing the dependency graphs
of all syntax trees that can be derived from {\em r}, the resulting dependency
graph must be noncircular. The following example shows the difference between
noncircular and {\em absolutely} noncircular grammars. 
\begin{quote}
{\bf Example:} Let {\em x,y,z} be nonterminals with
the productions $x \rightarrow y$ and $x \rightarrow y z$. Let {\em a} and
{\em b} be attributes of {\em x} and {\em y} respectively. Figure~\ref{sag1}
shows possible noncircular dependency graphs.
Superimposing the two graphs results in the ciclic graph displayed in
figure~\ref{sag2}. 
\end{quote}

\begin{figure}[tb]
\begin{center}              
\setlength{\unitlength}{0.7mm}
\begin{picture}(105,57)
\put(0,0){\framebox(105,57){}}
\put(24.7,45.7){\framebox(5.3,5.3)[]{x}}
\put(78,45.7){\framebox(5.3,5.3)[]{x}}
\put(17.3,12){\framebox(5.3,5.3)[]{y}}
\put(43.3,11){\framebox(5.3,5.3)[]{z}}
\put(77.7,11){\framebox(5.3,5.3)[]{z}}
\put(21.7,46){a}
\put(33,46){b}
\put(75,45.7){a}                                 
\put(84.3,45.7){b}
\put(26.3,12){b}
\put(22.3,45){\vector(-1,-4){7}}
\put(24.7,5.3){\vector(1,2){2.7}}

\put(24.7,5.3){\line(-1,0){8}}
\put(16.7,5.3){\line(-1,2){3}}

\put(28,18.7){\vector(1,4){6.3}}
\put(13.3,12){a}
\put(85.3,45.3){\line(-1,-2){2.7}}
\put(82.7,40){\line(-1,0){5.3}}
\put(77.3,40){\vector(-1,4){1.3}}
\end{picture}
\caption{Noncircular Dependency Graphs}
\label{sag1}
\end{center}
\end{figure}

\begin{figure}[tb]
\begin{center}
\setlength{\unitlength}{0.7mm}
\begin{picture}(105,57)
\put(0,0){\framebox(105,57){}}
\put(24.7,45.7){\framebox(5.3,5.3)[]{x}}
\put(17.3,12){\framebox(5.3,5.3)[]{y}}
\put(43.3,11){\framebox(5.3,5.3)[]{z}}
\put(21.7,46){a}
\put(33,46){b}
\put(26,12){b}

\put(22.3,45){\vector(-1,-4){7}}

\put(24.7,5.3){\vector(1,2){3}}

\put(24.7,5.3){\line(-1,0){8}}
\put(16.7,5.3){\line(-1,2){2.7}}

\put(28,18.7){\vector(1,4){6.3}}
\put(13.3,12){a}
\put(32.3,44){\line(-1,-3){1.3}}
\put(31,40){\line(-1,0){6}}
\put(25,40){\vector(-1,3){1.7}}
\end{picture}
\caption{Obtaining a cycle by superimposing graphs}
\label{sag2}
\end{center}
\end{figure}

The algorithm for the construction of an evaluator works as follows\footnote{
For an exact description see \cite{kew}.}: For every
nonterminal of the grammar, {\em one} evaluation automaton is constructed.
A state transition of such an automaton is either an evaluation instruction
for an attribute\footnote{ Since the grammar is absolutely noncircular,
dependencies of different productions of the same nonterminal can be sorted
(topologically) together. Every single automaton then incorporates a sorted
subset of all attribute dependencies.} or a jump instruction to a state of
another automaton. The procedure begins with starting the root automaton.
Jump instructions (always to the father or to a son of the current node) are
parameterized with the attribute values that have become available since the
last time that this node has been visited\footnote{ Absolute noncircularity
ensures that additional attributes can be evaluated every time a node is
visited. The attributes that have become available could depend on the chosen
derivation.}.
The tree is attributed completely iff all automata have reached their final
states.

The benefits of this method compared to others are:
\begin{enumerate}
\item The evaluation order is computed at generation time and not at run
	time (this is clearly equally true for the simpler classes mentioned
	above but not for arbitrarily attributed grammars)
\item Absolute noncircularity can be tested in polynomial time (in $|$AG$|$).
\item The evaluation algorithm has running time ${\cal O}$($|$attributes$|$).
\item To a large extent, design of the grammar does not depend on the 
	evaluation algorithm, the latter is constructed
	automatically\footnote{A grammar failing the test on
	absolute noncircularity is very likely to be erroneous (i.e. not
	well defined).}.
\end{enumerate}
However, the size of the constructed evaluator (and therefore also the running
time of the construction algorithm) is not bound by a polynom.
This drawback is overcome by ``ordered'' grammars that will be described
later on.

The {\em incremental} version of the algorithm does not start with the root of the
tree but with the ``point of change'' {\em r}. Since not all sucessors (in a
total order embedding the partial order of attribute dependencies) of changed
attributes generally need reevaluation, superfluous evaluation sequences can
be bypassed. In order to find for an arbitrary
node always the appropriate entry point\footnote{ Entry points are the states,
where branches from other automata enter.} into its automaton, the entry
sequences of all automata must be stored in the nodes of the AST. This
sequence is recomputed whenever the actual position in the AST (and therewith
the potential ``point of change'') is altered, because the entry points that
are actually valid depend on the currently chosen derivation.
Furthermore, a distinction between {\em activated} and {\em non-activated}
automata is made. An automata becomes activated if one of its attributes
(i.e., the attributes which are computed by this automata)
depends {\em directly}  on a just updated attribute.

With these preliminaries in mind, we can describe the necessary modifications
for an incremental procedure: a jump instruction is executed only if activated
automata are concerned. After entering the automaton, its states are skipped
until the instruction following immediately the computation of the last
modified attribute is reached. This state is taken as the starting point
for the evaluation.
This method ensures that only those attributes that are actually affected
are reevaluated. Only the corresponding automata are activated. The run time
of this procedure is linear with respect to the number of affected attributes
and it needs a storage amount that is proportional to the size of the abstract
syntax tree \cite{r83}. 

\vspace*{-2mm}

\paragraph{Ordered Grammars}
\label{oag}
The notion of {\em ordered attribute grammars} which were invented by Kastens
\cite{k} can be derived from the Kennedy-Warren construction in the following
manner: 

The dependency graphs constructed for absolutely noncircular grammars are
extended by inserting edges according to the following method:
For every nonterminal {\em r}, the attribute dependencies induced by superimposing
the dependency graphs of all potential predecessors of {\em r} in a derivation tree
are inserted. Furthermore, an edge is inserted between any two attributes of {\em r}
if one of them is inherited and the other is synthesized and if their values are
available at consecutive tree moves.
If the resulting graph is noncircular then the grammar is ordered. Under this
condition, a {\em fixed} partition (i.e., independent from the chosen
derivation) into a sequence of subsets with the following property can be
found for every node's attributes: every subset consists of the attributes
whose values can be evaluated additionally, reaching the node alternately on a
move from the father or from a son. Therefore, the sequence of subsets
alternately contains either only inherited or only synthesized attributes. 
In this fashion, a total order on all attributes of the grammar is constructable
statically.
\begin{quote}
{\bf Example:} With the nonterminals {\em x,y,z} and the productions
$y \rightarrow x$, $z \rightarrow x$ and $x \rightarrow t$, the synthesized
attributes {\em y.e}, {\em z.f}, {\em x.a} and {\em x.c}, the inherited
attributes {\em x.b} and {\em x.d} and the attribute dependencies displayed in
figure~\ref{oag1} the resulting grammar is absolutely noncircular. 
This grammar is not ordered since {\em x.b} depends indirectly
of {\em x.a} and {\em x.d} depends indirectly of {\em x.c}.
Considering {\em both} possible predecessors of {\em x},
the circular evaluation sequence {\em abcda} is obtainable. 
\end{quote}

\begin{figure}
\begin{center}              
\setlength{\unitlength}{0.7mm}
\begin{picture}(90,77)
\put(0,0){\framebox(90,77){}}

\put(22.3,62){\framebox(5.3,5.3)[]{y}}
\put(18.7,62){e}
\put(20.7,61){\vector(1,-4){3.8}}
\put(17.3,42){\framebox(5.3,5.3)[]{x}}
\put(13.7,42){a}
\put(24,42){b}
\put(15,45){\vector(1,4){4}}
\put(62.3,62){\framebox(5.3,5.3)[]{z}}
\put(58.7,62){f}
\put(60.7,61){\vector(1,-4){3.8}}
\put(57.3,42){\framebox(5.3,5.3)[]{x}}
\put(53.7,42){c}
\put(64,42){d}
\put(55,45){\vector(1,4){4}}
\put(27.3,14){\framebox(5.3,5.3)[]{x}}
\put(23.3,14){b}
\put(37.3,14){d}
\put(20.3,14){a}
\put(34.3,14){c}
\put(27.7,7.3){\line(-1,2){2.7}}
\put(25.7,5.3){\vector(-1,2){3.5}}
\put(32.7,7.3){\line(-1,0){5}}
\put(34.7,5.3){\line(-1,0){9}}
\put(32.7,7.3){\vector(1,2){2.7}}
\put(34.7,5.3){\line(1,2){3.3}}
\end{picture}
\caption{Unordered Grammar}
\label{oag1}
\end{center}
\end{figure}

Compared with the method of Kennedy and Warren, the following benefits can
be derived: 
\begin{enumerate}
\item The construction of {\em visit-sequences} depends linearly on the size of
	the grammar (un\-at\-trib\-uted). On the largest number of symbols of a
	production and of the largest number of attributes of a symbol it
	depends according to a polynomial function.
\item The order test needs polynomial time (in $|$AG$|$).
\end{enumerate}
As opposed to the class of absolutely noncircular grammars where the action
taken in order to evaluate attributes depends on the previous one and on a
context dependent set of available attribute values, here the action taken is
{\em uniquely} determined by the previous one and the state transitions of the
evaluation automata are branch free. Concerning the {\em incremental}
procedure, this means that every automaton possesses a {\em unique} sequence
of entry
points which can be computed beforehand and stored globally. Therefore, the
time as well as the space that is spent is decreased by a constant factor. 
