Re: question: attribute grammar

separk wrote:
> I understand that an attribute grammar provides a static semantics of
> a given context-free grammar.
>
> However, I am wondering in general how one determines inherited
> attributes and synthesized attributes for terminals and nonterminals
> of a given context-free grammar.
>
> Is there a rule that tells how those attributes should be determined
> or the determination should be done so that those attributes reflect
> the semantics of the grammar (so, could be arbitrarily defined)?
>
> I would really apperciate any explanation and pointers that I could
> find more information about the subject.


Hi,


Your question is a bit suprising, and I'm not sure to understand what
you are looking for, but I will try to answer.


In fact, there are two problems.


1. Either you want to write an attribute grammar, and then you specify,
for a given CFG which attribute is synthesized (computed top-down) and
which is inherited (computed bottom-up). It's a matter of specification,
or programming. You know that the result of the computation will be the
value of the "last" synthesized attribute occurrence at the root of the
(parsing-)tree representing your input value. For example, if you want
to compute the minimum value of a binary tree's leaves, it is intuitive
that you need a synthesized attribute (min), For example:
(I note "nt.a" for the the attribute "a" occurrence on the non terminal
"nt")
(I note "constructor-name -> non-term1 non-term2 ..." for the CFG
productions)
root -> tree
root.min = tree.min
node -> left right
node.min = (left.min<right.min) ? left.min : right.min
leaf -> n
leaf.min = n
Then, the result of your computation will be found in root.min; an
attribute grammar system is able to find the suitable order to compute
all attribute occurrences until getting this value (that is, an
attribute evaluator).


Now, if you suppose you've got a value, says V, and a tree T, and you
want to construct a tree isomorphic to T with V at each leaves. You then
need an inherited attribute (h) to propagate the value V from the root
to the leaves, and a synthesised attribute (s) to construct the
resulting tree. For example:
root -> tree
tree.h = V // initialization of the inherited attribute
root.s = tree.s
node -> left right
left.h = node.h // propagation of the inherited value
right.h = node.h // that is, top-down
node.s = node(left.s , right.s) // construction of the result
(bottom-up)
leaf -> n
leaf.s = leaf(leaf.h) // here, leaf.h will contain V


Concerning your question, you see here that YOU choose which attribute
is synthesized or inherited, w.r.t the computation you want to achieve.
The example above is simple, because the inherited attribute only
propagates a value from root to leaves, without any modification. I show
below the example of building the list of the leaves of a tree.
Intuitively, you begin with nil, and you 'cons' each leaf value with
this list, traversing the tree, from right to left for example.
In this case, you have to travel inside the tree, propagating the
accumulation list in construction in the right part of a node, looking
for a leaf: since you go top down, this is done by an inherited
attribute (lh). But when you have found a leaf, you have to propagate
this list to the left part of the current node: this is done by a
synthesized attribute (ls).
Take a look at the example, and draw a figure for an example to convince
you.
root -> tree
tree.lh = nil
root.ls = list.ls
node -> left right
right.lh = node.lh // first, look at the right part of the node
left.lh = right.ls // next, transmit the acc. list to the left part
node.ls = left.ls // when the left part is visited, you've
// got the complete list for this current node
leaf -> n
leaf.ls = cons(n , leaf.lh) // at each leaf, 'cons' the current
// element to the acc. list


Again, your attribute grammar system will find the suitable order
(satisfying all attribute occurrences dependencies) to compute the
result of this attribute grammar (i.e, root.ls), for a given input tree.


2. The second problem in your question could be the following. Given
some dependencies between attribute occurrences on several productions
of a CFG, is it possible to know which attribute is synthesized and
which is inherited?
This question is of interest. It seems to me that it is possible to
infer such an information, using algorithms like type-inference...


You could find more information in a bibliography available on the Web.
More than 1000 references for attribute grammar articles and a lot of
attribute grammar researchers' home pages are referenced.
http://www-rocq.inria.fr/oscar/www/fnc2/fnc2-eng.htm


By this link, you could also download a powerful attribute grammar
system, FNC-2, developed at INRIA by Didier Parigot, in the Oscar
project:
http://www-rocq.inria.fr/oscar/


Best regards,


Etienne Duris.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.