Compilers: Module 6: Semantic Analysis: Attribute Grammars
Problems p. 122 #3,6
p. 137 #3
p. 122, #3
Translate the statement: WHILE ( 1 < P ) AND ( P < 3 ) DO P := P + Q
into:
(a) an abstract syntax tree
(b) quadruples
(c) triples
(d) indirect triples
********** SOLUTION **********
(a) An abstract syntax tree contains only the essential terminal
symbols of a parse tree. Thus terminals that do not contribute
to the syntax (such as parentheses) are left out.
while
|
|---------------------|
| |
AND :=
| |
|----------| |-----|
| | | |
< < P +
| | |
|-----| |-----| |-----|
| | | | | |
1 P P 3 P Q
(b) A quadruple is a form of pseudocode expressed with four
types:
Operation | LT operand | RT operand | Address
==========+============+============+============
| | | label_while
< | 1 | P | label_and
Goto | | | END_PROC
| | | label_and
< | P | 3 | label_do
Goto | | | END_PROC
| | | label_do
+ | P | Q | Temp1
:= | Temp1 | | P
Goto | | | label_while
(c) Triples remove the Address value from the quadruples and
are executed consecutively (unless a "Go" occurs). Special
keyword "IfNT" means "If Not True" and refers to the previous
line for it's condition.
(1) < 1 P
(2) IfNT Go (8)
(3) < P 3
(4) IfNT Go (8)
(5) + P Q
(6) := (5) P
(7) Go (1)
(8)
(d) The problem with triples is that minor changes can force
the entire list to be reevaluated as some jumps may be
non-valid. With indirect triples, an execution order is
given so that changes will have minimal impact on the code.
(1) < 1 P
(2) IfNT Go (8)
(3) < P 3
(4) IfNT Go (8)
(5) + P Q
(6) := (5) P
(7) Go (1)
(8)
Execution Order: 1 2 3 4 5 6 7 8
To show how an indirect triple would actually make a
difference consider if an extra intruction (+ P Z)
were to be inserted in the loop
(1) < 1 P
(2) IfNT Go (8)
(3) < P 3
(4) IfNT Go (8)
(5) + P Q
(6) := (5) P
(7) Go (1)
(8)
(9) + P Z
Execution Order: 1 2 3 4 9 5 6 7 8
Notice the (9) in the execution list. And none of the
links need to be updated! Remember that the order of execution
is dictated by that list of numbers.
p. 122, #6
Modifed 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
attrbute 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
attribut
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
p. 137, #3
Consider the following declaration:
A = record
A1 : array[1..10,0..9] of real;
A2 : boolean;
end
Show a possible symbol table organization.
********** SOLUTION **********
----------------- ------------------ ------------------
| Id Descriptor | |Field Descriptor| |Field Descriptor|
|===============| --- >|================| |================|
| String = "A" | | | Next = ---------- >| Next = ----- |
| Type = record | | | Value = -- | | Value = -- | |
| FieldList = ------ | | | | | | |
| | ------------|----| ------------|--|--
----------------- | | |
| | V
------------------------------ | (NULL)
| |
V V
-------------------- ------------------ -----------------
| Type Descriptor | |Index Descriptor| |Type Descriptor|
|==================| ---- >|================| |===============|
| String = "A1" | | | Next = ----- | | String = "A2" |
| Type = Array | | | Value = -- | | | Type = boolean|
| IndexType = -------- ------------|--|-| -----------------
| ElementType = -- | | |
-----------------|-- | --------------
| | |
---------- | |
| V V
V ----------------- ------------------
----------------- |Type Descriptor| |Index Descriptor|
|Type Descriptor| |===============| |================|
|===============| | Type = Integer| | Next = ----------
| Type = Real | | Min = 1 | | Value = --- | |
----------------- | Max = 10 | | | | |
----------------- -------------|---- |
| |
| V
| (NULL)
V
-----------------
|Type Descriptor|
|===============|
| Type = Integer|
| Min = 0 |
| Max = 9 |
-----------------