Topics:
Some basic terminology and an example
Attribute
Synthesized
Inherited
Small Example : Calculate value of expression
| Production | Semantic Rules |
| L --> E n | print(E.val) |
| E --> E + T | E.val := E1.val + T.val |
| E --> T | E.val := T.val |
| T --> T * F | T.val := T1.val x F.val |
| T --> F | T.val:= F.val |
| F --> ( E ) | F.val:= E.val |
| F --> digit | F.val := digit.lexval |
This is a syntax directed translation. This is the model that will be used as we study the next component in the compilation process: type checking and code generation.
Semantic rules compute the value of val for each LHS based on the value of val for the RHS components. For digit, the lexval is associated by the lexical analyzer.
Terminals have only synthesized attributes
Start symbol does not have any inherited attributes
Consider a sample expression , meaning of these rules, and the order the attributes are computed
Basic typing example
| Production | Semantic Rules |
| D --> T L | L.in := T.type |
| T --> int | T.type := integer |
| T --> real | T.type := real |
| L --> L , id | L1.in := L.in addtype(id.entry, L.in) |
| L --> id | addtype(id.entry, L.in) |
Again, consider an example: generate a word in the language and then evaluate the attributes.
| N --> S "." S |
| S --> S B |
| S --> B |
| B --> "0" |
| B --> "1" |
The goal is to determine the value of the binary number.
Attribute Assertions : Synthesized and Inherited
| N sv--> S if sv sl "." S if sv sl |
| S if sv sl --> S if sv sl B if sv |
| S if sv sl --> B if sv |
| B if sv --> "0" |
| B if sv --> "1" |
Semantic Actions
| N --> S "." S | [ v = v1 + v2 ; f1 = 1 ; f2 = 2^-l2 ] |
| S --> S B | [ f1 = 2f ; f2 = f; v = v1 + v2; l = l1 + 1 ] |
| S --> B | [ l = 1; f1 = f; v = v1] |
| B --> "0" | [ v = 0 ] |
| B --> "1" | [ v = f ] |
Goal: associate an attribute that represents the value of the fixed-point binary number
Basics:
Demonstrate::
Attribute Assertions : Synthesized and Inherited
| N sv--> S si sl "." S si sl |
| S si sl --> S si sl B si |
| S si sl --> B si |
| B si --> "0" |
| B si --> "1" |
Semantic Actions
| N --> S "." S | [ v = i1 + 2^-l2 * i2 ] |
| S --> S B | [ i = 2*i1 + i2 ; l = l1 + 1 ] |
| S --> B | [ l = 1; i = i1 ] |
| B --> "0" | [ i = 0 ] |
| B --> "1" | [ i = 1 ] |
Demonstrate::
N : I . F I : I B I : B F : B F F : B B : 1 B : 0 |
{ $$.v = $1.v + $3.v};
{ $$.v = 2 * $1.v + $2.v};
{$$v = $1.v};
{$$v = ($1.v + $2.v) / 2}
{$$v = $1.v / 2};
{$$v = 1};
{$$.v = 0};
|
Demonstrate::
A similar example from the following location::
http://penguin.wpi.edu:4546/course/CS544/PLT6.ex.soln.html
Modified Knuth example (Knuth, 1971a) Consider the following
attribute grammar:
Productions || Semantics
====================================++=====================
0: Number -- > Sign List || (1) List.Scale := 0
|| (2) Number.Value :=
|| IF Sign.Neg THEN -List.Value
|| ELSE List.Value
1: Sign -- > + || (1) Sign.Neg := False
2: Sign -- > - || (1) Sign.Neg := True
3: List -- > BinaryDigit || (1) BinaryDigit.Scale = List.Scale
|| (2) List.Value := BinaryDigit.Value
4: List(0) -- > List(1) BinaryDigit|| (1) List(1).Scale =
|| List(0).Scale + 1
|| (2) BinaryDigit.Scale = List.Scale
|| (3) List(0).Value := List(1).Value
|| + BinaryDigit.Value
5: BinaryDigit -- > 0 || (1) BinaryDigit.Value = 0
6: BinaryDigit -- > 1 || (1) BinaryDigit.Value =
|| 2^(BinaryDigit.Scale)
(a) Identify the attributes and classify the as inherited,
synthesized or intrinsic.
(b) Parse and evaluate the attributes for the string: -1 0 1
(c) What do these attributes do?
********** SOLUTION **********
(a) An attribute is
Inherited if the value of the attribute of the right
hand side of the production is set by the
attribute from the left hand side of the
production (see production 3)
Synthesized is just the opposite of inherited: if
the attributes of the left hand side
production is set by the attributes of the
right hand side.
Intrinsic if a terminal constant is assigned to the
attribute
Attribute | Type
===================+==============
List.Scale | inherited
Number.Value | synthesized
Sign.Neg | intrinsic
BinaryDigit.Scale | inherited
BinaryDigit.Value | inherited (but sometimes intrinsic)
List.Value | synthesized
The reason for the discrepancy in the table above for the
BinaryDigit.Value is that attributes have a type that is
dependent on the current production. Usually all
attributes have the same type no matter what production
they occur in. As shown above, BinaryDigit.Value is an
exception: inherited in production 6 and intrinsic in
production 5
(b) Number (scale = 0)
| (value = -5)
|
|--------------------
| |
Sign (neg = True) List (scale = 0)
| | (value = 5)
| |
| ---------+--------------------
- | |
List (scale = 1) BinaryDigit (scale = 0)
| (value = 4) | (value = 1)
| |
| |
| 1
-----------+-------------
| |
List (scale = 2) BinaryDigit (scale = 1)
| (value = 4) | (value = 0)
| |
| |
| |
BinaryDigit (scale = 2) 0
| (value = 1)
|
|
1
(c) converts signed binary digits to decimal equivalents
-1 0 1 == > -5
Demonstrate::