<h2>How can inherited attributes be simulated with synthesized ones: an example.</h2>

<p>The way of doing it is to postpone the evaluation of any attribute
that uses directly or indirectly an inherited attribute, by
abstracting it into a function that takes the inherited attribute as
argument. There may be several such arguments.</p>

<p>Here is a fragment of a simple example, on the grammar rule $T\rightarrow T\; v$<br>
 for a term in an expression, which is to be type-checked.</p>

<p>Right hand side symbols are subscripted to identify occurrences, so we actually write $T\rightarrow T_1\; v_1$<br>
We use the following attributes:  </p>

<ul>
<li>for $T$ the inherited attribute $symtab$ and the synthesized
attribute $type$;  </li>
<li>for $v$, which is a terminal, the synthesized attribute $name$ which is actually produced by the lexer.</li>
</ul>

<p>The semantic rule  for type checking is:  $type(T)\gets  
 if\; type(T_1)=symtab[name(v_1).type]\; then\; type(T_1)\; else\; typefail$</p>

<p>meaning that the type of the subterm $T_1$ and the type associated with the symtab entry of the $name$ of the variable $v_1$ 
must be the same, and that the name of this common type or $typefail$ is the value for the
synthesized attribute $type$ for $T$. </p>

<p>You replace that semantic rule by the following one:<br>
$type(T)\gets \lambda\; symtab.\;      if\; type(T_1)(symtab)=symtab[name(v_1).type]\;$ $\qquad\qquad\qquad\qquad\;\;\;\;\;\;then \;type(T_1)\; else\; typefail$</p>

<p>The synthesized attribute $type$ is now a function rather than a type
name.  When called, it takes a symtab as argument and checks whether
the expression $T$ is well typed with respect to this symtab, calling
recusively other such functional values of the attribute to actually
do the type checking for subexpressions.</p>

<p>You no longer need to know the symbtab where you do the type checking, so you do not need the inherited attribute $symtab$.
When higher up in the tree you get a synthesized attribute that is the
actual symtab, you simply apply the type attribute with that symtab as
argument to get the type checking done.  Well, it is a bit more
complicated with scope rules.</p>

<p>This can be completely formalized, but I do not have the right papers
handy, and I have no courage or time to redo the complete formal presentation. But I am sure there are books and papers on this</p>

<p>It is a kind of continuation passing style for processing the inherited attributes.</p>

<h2>A proof that inherited attributes are not necessary</h2>

<p>Hypotheses:</p>

<ul>
<li><p>attributes can carry values of any type, though functional types
are not really a requirement (see the proof) despite the example
above.</p></li>
<li><p>any type of computation on the attributes is permitted.</p></li>
</ul>

<p>We assume a CF grammar $G$ with an attribute system, such that
evaluation of attributes on a parse tree $T$ will produce a result
$E(T)$ for a distinguished attribute $\rho$ of the initial symbol
$S$ labeling the root: $\rho(root_T)=E(T)$. Our purpose is to exhibit an attribute system that produces the
same result using only synthesized attributes. Without loss of
generality, we assume that the initial symbol S of the grammar is
never used used in a right-hand side of a rule.</p>

<p><em>Intuition: we make a copy of the tree as a purely synthesized attribute of the root node.</em></p>

<p>In the formalization below $A_i$ denotes an occurence of a symbol in a rule, and
we note $\sigma A_i$ the actual symbol in that occurence.</p>

<p>We have a single synthesized attribute $\theta$ for all terminals and
non-terminals. For terminals, this attribute is initialized to a tree
degenerated to its root node labeled by the terminal. In addition,
there is the attribute $\rho$ for the initial symbol
$S$.</p>

<p>To each grammar rule  $\qquad \sigma A_0 \to \sigma A_1 \dots \sigma A_n$</p>

<p>we associate the following attribute calculation</p>

<p>$\theta(A_0) \leftarrow tree(\sigma A_0, [\theta(A_1), \dots \theta(A_1)])$</p>

<p>where $\theta(s,tt)$ is a function that takes two arguments, a
non-terminal $s$ and a list of trees $tt$, and returns a new tree with
a root labeled with $s$ and all the trees in $tt$ as daughters of the
root, in the same order.</p>

<p>It is easily shown by structural induction that attribute evaluation
of a tree $T$ will thus assign to the attribute $\theta(S)$ a value
that is precisely equal to $T$ (i.e., a copy of $T$ if that is more
intuitive). Since we know from the initial attribute system that there
is an effective procedure to compute the result $E(T)$, we only have
to add one extra attribute rule to be associated with the initial
symbol $S$:
$\rho(S)\leftarrow E(\theta(S))$</p>

<p>Thus, our new attribute system has only synthesized attributes and
computes exactly the same result as the initial system.</p>

<p>Some readers may find the proof a bit unsettling, but it is not a
circular (tautological) proof. We do not have to use the initial
attribute system to actually compute $E(\theta(S))$. The only thing
that matters is that it is computable.</p>

<p>Actually it is very close to the technique used in the example above,
using functional attributes, but it delays computation by passing
syntactic information bottom up, rather than doing it more
semantically by passing a continuation. One could use that functional attribute technique to do the proof, but I suspect it would be technically much more complex.</p>

<p>It shows that what matters to make sure than an evaluation policy can
be used is to check that this evaluation policy is able to duplicate
all the data, in this case the parse tree.</p>

<p>From that perspective, it is easily seen that using only inherited
attributes will not in general be adequate, because the tree cannot be
duplicated with only inherited attributes.</p>

<p>The reason is quite simple: when you are going top-down exclusively
you cannot pass information sideways in the tree. Take the rule
$  A \to B C$. If you are on the $B$ node of an instance of that
rule in the tree and want to compute the inherited attributes, all you see is $A$ above. There is no way you can relate to the $C$ side of the tree. And $A$ cannot look at it since information goes top down only, and $C$ is below $A$. The information on the current node depends only on the path from the root to that node, not on the whole tree.</p>

CC BY-SA 3.0
2014-02-18T14:38:13.477Z
thanks for the nice explanation. So, if we turn the question the other way round, that is if we ask whether a synthesized attribute can be simulated using and inherited attribute, will the same kind of argument hold? Or is it different in that case?
saikat
CC BY-SA 3.0
2014-02-18T14:51:08.100Z
As I recall, it does not work the other way around. The reason is
quite simple: when you are going top-down exclusively you cannot pass
information sideways in the tree. Take the rule A -> B C. Once you are
on the B node of an instance of that rule in the tree and want to
compute the attributes, all you see is A above. There is no way you can
relate to the C side of the tree. And A did not look at it since
information goes top down only, and C is below A. Bottom-up can
collect information from the whole tree and bring it up for the root
to process.
babou
CC BY-SA 3.0
2014-02-18T14:55:48.647Z
Bottom-up can bring a copy of the tree to the root for the root to
process at leisure, including simulating on it any attribute
evaluation procedure. This is sort of the ultimate version of the
suggestion in my answer, and probably an easy way to formally prove
that inherited attributes can be done away with. Top-down cannot make
a copy of the tree anywhere.
babou
CC BY-SA 3.0
2014-02-20T21:04:04.637Z
@saikat How do you like the proof. Does it make it an acceptable answer? - - - - - - - - - - - - - - - - - - By the way, are attributed grammars still used much? Where ?
babou
CC BY-SA 3.0
2014-02-20T21:16:55.873Z
oh...yes, it does...I am so sorry for not marking it earlier..And while taking a course on Programming Languages, this question came to my mind. Thanks a lot for the clear solution. I really appreciate it.
saikat
CC BY-SA 3.0
2014-02-20T21:37:17.663Z
@saikat You mean that attributed grammars are part of your course on compilers?  I was wondering. I did not look at that stuff for a long time.
babou
CC BY-SA 3.0
2014-02-20T22:17:31.503Z
Yeah, its a PhD core course called Programming Language Structures, that covers stuff like attribute grammars, axiomatic and denotational semantics and other such topics, certainly a very interesting subject
saikat
CC BY-SA 3.0
2014-02-18T14:07:07.400Z
2014-02-19T18:55:18.903Z
2014-02-19T18:55:18.903Z
babou
<p>Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized attribute? If yes, what are the changes proposed to the existing attribute grammar? If not, why not? </p>

<pl.programming-languages><grammars><compilers><parsing>
How can an inherited attribute be simulated using a synthesized attribute?
saikat
# How can an inherited attribute be simulated using a synthesized attribute?

(Asked by: username_0 on 2014-02-15)

Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized attribute? If yes, what are the changes proposed to the existing attribute grammar? If not, why not?

**Tags:** pl.programming-languages, grammars, compilers, parsing


---

## 1 answers

### Answer by username_1 on 2014-02-18. Score: 4 | Accepted answer

## How can inherited attributes be simulated with synthesized ones: an example.

The way of doing it is to postpone the evaluation of any attribute
that uses directly or indirectly an inherited attribute, by
abstracting it into a function that takes the inherited attribute as
argument. There may be several such arguments.

Here is a fragment of a simple example, on the grammar rule $T\rightarrow T\; v$  
for a term in an expression, which is to be type-checked.

Right hand side symbols are subscripted to identify occurrences, so we actually write $T\rightarrow T\_1\; v\_1$  
We use the following attributes:

* for $T$ the inherited attribute $symtab$ and the synthesized
  attribute $type$;
* for $v$, which is a terminal, the synthesized attribute $name$ which is actually produced by the lexer.

The semantic rule for type checking is: $type(T)\gets
if\; type(T\_1)=symtab[name(v\_1).type]\; then\; type(T\_1)\; else\; typefail$

meaning that the type of the subterm $T\_1$ and the type associated with the symtab entry of the $name$ of the variable $v\_1$
must be the same, and that the name of this common type or $typefail$ is the value for the
synthesized attribute $type$ for $T$.

You replace that semantic rule by the following one:  
$type(T)\gets \lambda\; symtab.\; if\; type(T\_1)(symtab)=symtab[name(v\_1).type]\;$ $\qquad\qquad\qquad\qquad\;\;\;\;\;\;then \;type(T\_1)\; else\; typefail$

The synthesized attribute $type$ is now a function rather than a type
name. When called, it takes a symtab as argument and checks whether
the expression $T$ is well typed with respect to this symtab, calling
recusively other such functional values of the attribute to actually
do the type checking for subexpressions.

You no longer need to know the symbtab where you do the type checking, so you do not need the inherited attribute $symtab$.
When higher up in the tree you get a synthesized attribute that is the
actual symtab, you simply apply the type attribute with that symtab as
argument to get the type checking done. Well, it is a bit more
complicated with scope rules.

This can be completely formalized, but I do not have the right papers
handy, and I have no courage or time to redo the complete formal presentation. But I am sure there are books and papers on this

It is a kind of continuation passing style for processing the inherited attributes.

## A proof that inherited attributes are not necessary

Hypotheses:

* attributes can carry values of any type, though functional types
  are not really a requirement (see the proof) despite the example
  above.
* any type of computation on the attributes is permitted.

We assume a CF grammar $G$ with an attribute system, such that
evaluation of attributes on a parse tree $T$ will produce a result
$E(T)$ for a distinguished attribute $\rho$ of the initial symbol
$S$ labeling the root: $\rho(root\_T)=E(T)$. Our purpose is to exhibit an attribute system that produces the
same result using only synthesized attributes. Without loss of
generality, we assume that the initial symbol S of the grammar is
never used used in a right-hand side of a rule.

*Intuition: we make a copy of the tree as a purely synthesized attribute of the root node.*

In the formalization below $A\_i$ denotes an occurence of a symbol in a rule, and
we note $\sigma A\_i$ the actual symbol in that occurence.

We have a single synthesized attribute $\theta$ for all terminals and
non-terminals. For terminals, this attribute is initialized to a tree
degenerated to its root node labeled by the terminal. In addition,
there is the attribute $\rho$ for the initial symbol
$S$.

To each grammar rule $\qquad \sigma A\_0 \to \sigma A\_1 \dots \sigma A\_n$

we associate the following attribute calculation

$\theta(A\_0) \leftarrow tree(\sigma A\_0, [\theta(A\_1), \dots \theta(A\_1)])$

where $\theta(s,tt)$ is a function that takes two arguments, a
non-terminal $s$ and a list of trees $tt$, and returns a new tree with
a root labeled with $s$ and all the trees in $tt$ as daughters of the
root, in the same order.

It is easily shown by structural induction that attribute evaluation
of a tree $T$ will thus assign to the attribute $\theta(S)$ a value
that is precisely equal to $T$ (i.e., a copy of $T$ if that is more
intuitive). Since we know from the initial attribute system that there
is an effective procedure to compute the result $E(T)$, we only have
to add one extra attribute rule to be associated with the initial
symbol $S$:
$\rho(S)\leftarrow E(\theta(S))$

Thus, our new attribute system has only synthesized attributes and
computes exactly the same result as the initial system.

Some readers may find the proof a bit unsettling, but it is not a
circular (tautological) proof. We do not have to use the initial
attribute system to actually compute $E(\theta(S))$. The only thing
that matters is that it is computable.

Actually it is very close to the technique used in the example above,
using functional attributes, but it delays computation by passing
syntactic information bottom up, rather than doing it more
semantically by passing a continuation. One could use that functional attribute technique to do the proof, but I suspect it would be technically much more complex.

It shows that what matters to make sure than an evaluation policy can
be used is to check that this evaluation policy is able to duplicate
all the data, in this case the parse tree.

From that perspective, it is easily seen that using only inherited
attributes will not in general be adequate, because the tree cannot be
duplicated with only inherited attributes.

The reason is quite simple: when you are going top-down exclusively
you cannot pass information sideways in the tree. Take the rule
$ A \to B C$. If you are on the $B$ node of an instance of that
rule in the tree and want to compute the inherited attributes, all you see is $A$ above. There is no way you can relate to the $C$ side of the tree. And $A$ cannot look at it since information goes top down only, and $C$ is below $A$. The information on the current node depends only on the path from the root to that node, not on the whole tree.

> **Comments:**
> **username_0**: thanks for the nice explanation. So, if we turn the question the other way round, that is if we ask whether a synthesized attribute can be simulated using and inherited attribute, will the same kind of argument hold? Or is it different in that case?  
> **username_1**: As I recall, it does not work the other way around. The reason is quite simple: when you are going top-down exclusively you cannot pass information sideways in the tree. Take the rule A -> B C. Once you are on the B node of an instance of that rule in the tree and want to compute the attributes, all you see is A above. There is no way you can relate to the C side of the tree. And A did not look at it since information goes top down only, and C is below A. Bottom-up can collect information from the whole tree and bring it up for the root to process.  
> **username_1**: Bottom-up can bring a copy of the tree to the root for the root to process at leisure, including simulating on it any attribute evaluation procedure. This is sort of the ultimate version of the suggestion in my answer, and probably an easy way to formally prove that inherited attributes can be done away with. Top-down cannot make a copy of the tree anywhere.  
> **username_1**: @username_0 How do you like the proof. Does it make it an acceptable answer? - - - - - - - - - - - - - - - - - - By the way, are attributed grammars still used much? Where ?  
> **username_0**: oh...yes, it does...I am so sorry for not marking it earlier..And while taking a course on Programming Languages, this question came to my mind. Thanks a lot for the clear solution. I really appreciate it.  
> **username_1**: @username_0 You mean that attributed grammars are part of your course on compilers?  I was wondering. I did not look at that stuff for a long time.  
> **username_0**: Yeah, its a PhD core course called Programming Language Structures, that covers stuff like attribute grammars, axiomatic and denotational semantics and other such topics, certainly a very interesting subject  

---

