Re: question: attribute grammar

Frank Derichsweiler <deri@informatik.unibw-muenchen.de>
3 Apr 1998 17:08:00 -0500

          From comp.compilers

Related articles
question: attribute grammar separk@pollux.usc.edu (1998-03-30)
Re: question: attribute grammar Etienne.Duris@inria.fr (Etienne Duris) (1998-04-03)
Re: question: attribute grammar deri@informatik.unibw-muenchen.de (Frank Derichsweiler) (1998-04-03)
| List of all articles for this month |

From: Frank Derichsweiler <deri@informatik.unibw-muenchen.de>
Newsgroups: comp.compilers
Date: 3 Apr 1998 17:08:00 -0500
Organization: UniBwM, Fakultaet Informatik, Institut 2
References: 98-03-243
Keywords: attribute

separk wrote:
> I understand that an attribute grammar provides a static semantics of
> a given context-free grammar.


IMO more precisely: semantics of a word, which is in the language
described by the 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.


You need a derivation tree for the actual word (which is in the
language)


E.g.
Production S ::= aBC


Rule for foo_syn_attrib_S:
foo_syn_attrib_S := union(syn_attrib_B,syn_attrib_C)


assuming, that foo_syn_attrib_S, syn_attrib_B and syn_attrib_C are sets.


If you have the following part within the derivation tree


          S
      / | \
    a B C


and you know, that syn_attrib_B has value {1,2} and syn_attrib_C {3,4}
the value of foo_syn_attrib_S will have value {1,2,3,4}


Generally speaking, you have to search within the rules for
"executable" ones and then compute new values. Iterating this process
will compute all attributes of the nodes in a derivation
tree. Caution: that is not true for the general case with arbitrary
rules because of possible circles in the dependency graph. There are
special cases, in which you can compute all attributes by a
depth-first-run through the derivation-tree, starting at the root
node.


> 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.


Look for books about compiler construction, e.g. the well known bok of
Aho, Sethi, Ullman, called the dragon book.


HTH,
Frank


mailto:deri@informatik.unibw-muenchen.de
--


Post a followup to this message

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