Attribute Grammar Example: Declaration Semantics

J. Remmers, COSC 337, Fall 2003

In C, C++, and Java, simple declarations begin with a data type name, followed by a comma-separated list of identifiers, followed by a semicolon. For example:

            int alpha, foo, spafon;

The intended meaning of this is that the typename int specifies a particular data type, and that data type becomes an attribute of each identifier in the list. This informal description of the semantics is sufficient explanation for a programmer to be able to write sensible declarations, but for purposes of automating type-checking (such as a compiler would do), a more formal, computational description of the semantics is desirable. In these notes, we show how this semantics can be specified via an attribute grammar.

The attribute grammar that we present will be a mixture of synthesized semantic rules (attribute values of the left side of a production are calculated from attribute values of symbols on the right side) and inherited rules (attribute values of symbols on the right side of a production are calculated from attribute values of the symbol on the left side).

First, the grammar, without any semantic rules. To keep the example short, we include only int, float, and char type specifiers, and allow only lists of identifiers (no arrays, structs, etc.).

Grammar of simple declarations

Terminal symbols:
int float char ID , ;
Nonterminal symbols:
<dlist> <tspec> <rest>
Start symbol:
<dlist>
Productions:
  1. <dlist> -> <tspec> ID <rest> ;
  2. <tspec> -> int
  3. <tspec> -> float
  4. <tspec> -> char
  5. <rest> ->
  6. <rest> -> , ID <rest>

Attribute grammar for declarations

We now extend the above BNF grammar to an attribute grammar by introducing a type attribute for the symbols and giving a set of semantic rules for calculating the values of the attributes.

As always, each semantic rule will be tied to a particular production. However, in this example, some productions will have more than one associated semantic rule.

The type attribute will have three possible values: 32bitInt, SPReal, and Character, that is, 32-bit integer, single-precision real, and character. It is assumed that these concepts are defined elsewhere.

Intrinsic attributes:
Semantic rules:

Here we list the productions again, and with each production, the associated semantic rule or rules.

  1. <dlist> -> <tspec> ID <rest> ;
    • (a) <dlist>.type = <tspec>.type
    • (b) ID.type = <dlist>.type
    • (c) <rest>.type = <dlist>.type
  2. <tspec> -> int
    • (a) <tspec>.type = int.type
  3. <tspec> -> float
    • (a) <tspec>.type = float.type
  4. <tspec> -> char
    • (a) <tspec>.type = char.type
  5. <rest> ->
    • (no associated semantic rules)
  6. <rest> -> , ID <rest>
    • (a) <rest>[2].type = <rest>[1].type
    • (b) ID.type = <rest>[1].type

Self-Test Exercises

(Not to be handed in for credit)

  1. Which of the above semantic rules are synthesized and which are inherited?
  2. Use the given attribute grammar to draw a decorated parse tree for the declaration list 
                  float x, length;