2
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – saikat
    Feb 18 '14 at 14:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Feb 18 '14 at 14:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – babou
    Feb 18 '14 at 14:55
  • 1
    $\begingroup$ @saikat How do you like the proof. Does it make it an acceptable answer? - - - - - - - - - - - - - - - - - - By the way, are attributed grammars still used much? Where ? $\endgroup$
    – babou
    Feb 20 '14 at 21:04
  • $\begingroup$ 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. $\endgroup$
    – saikat
    Feb 20 '14 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.