CHAPTER FOUR

Syntax-Directed Translation

1
 Outline
• Introduction
• Syntax-Directed Definitions and Translation Schemes
• Syntax-Directed Definitions
• Annotated Parse Tree
• Annotating a Parse Tree With Depth-First Traversals
• Dependency Graph
• Evaluation order
• S-Attributed Definitions
• Bottom-Up Evaluation of S-Attributed Definitions

2
 Introduction
• Grammar symbols are associated with attributes to
associate information with the programming language
constructs that they represent.
• Values of these attributes are evaluated by the semantic
rules associated with the production rules.

• Evaluation of these semantic rules:

– may generate intermediate codes
– may put information into the symbol table
– may perform type checking
– may issue error messages
– may perform some other activities
– in fact, they may perform almost any activities.
3
 Syntax-Directed Definitions and Translation
Schemes
• When we associate semantic rules with productions, we use two
notations:
– Syntax-Directed Definitions
– Translation Schemes
• Syntax-Directed Definitions:
– give high-level specifications for translations
– hide many implementation details such as order of evaluation of semantic
actions.
– We associate a production rule with a set of semantic actions, and we do
not say when they will be evaluated.
• Translation Schemes:
– indicate the order of evaluation of semantic actions associated with a
production rule.
– In other words, translation schemes give more information about
implementation details.
4
 Syntax-Directed Definitions
• A syntax-directed definition is a generalization of a
context-free grammar in which:
– Each grammar symbol is associated with a set of attributes.
– This set of attributes for a grammar symbol is partitioned into two
subsets called synthesized and inherited attributes of that
grammar symbol.
– Each production rule is associated with a set of semantic rules.
• An attribute can represent anything we choose:
– a string, a number, a type, a memory location, intermediate
program representation etc...
– The value of a synthesized attribute is computed from the values
of attributes at the children of that node in the parse tree.
– The value of an inherited attribute is computed from the values of
attributes at the siblings and parent of that node in the parse tree.

5
 Syntax-Directed Definitions…
• Semantic rules set up dependencies between attributes which
can be represented by a dependency graph.
• This dependency graph determines the evaluation order of
these semantic rules.
• Evaluation of a semantic rule defines the value of an attribute.
• But a semantic rule may also have some side effects such as
printing a value.
• A depth-first traversal algorithm traverses the parse tree
thereby executing semantic rules to assign attribute values.
• After the traversal is complete the attributes contain the
translated form of the input.

6
 Syntax-Directed Definition…
• In a syntax-directed definition, each production A → α is
associated with a set of semantic rules of the form:
b=f(c1,c2,…,cn) where f is a function,
and b can be one of the followings:
 b is a synthesized attribute of A and c1,c2,…,cn are
attributes of the grammar symbols in the production
( A → α ). For A  C A.b = C.c
OR
 b is an inherited attribute one of the grammar symbols
in α (on the right side of the production),
and c1,c2,…,cn are attributes of the grammar symbols in the
production ( A → α ). For A C C.c = A.b
7
 Annotated Parse Tree

• A parse tree showing the values of attributes at

each node is called an annotated parse tree.
• The process of computing the attributes values at
the nodes is called annotating (or decorating) of
the parse tree.
• Of course,the order of these computations depends
on the dependency graph induced by the semantic
rules.

8
 Annotating a Parse Tree With
Depth-First Traversals

procedure visit(n : node);

Begin
for each child m of n, from left to right do
visit(m);
evaluate semantic rules at node n
end

9
Example: Synthesized Attributed grammar that calculate the
value of expression

Production Semantic Rules

L→En print(E.val)
E → E1 + T E.val = E1.val + T.val
E→T E.val = T.val
T → T1 * F T.val = T1.val * F.val
T→F T.val = F.val
F→(E) F.val = E.val
F → digit F.val = digit.lexval

 It specifies a simple calculator that reads an input line containing

an arithmetic expression involving:
 digits, parenthesis, the operator + and *, followed by a new line character n,
and
 prints the value of expression.
10
 Example: Synthesized Attributed grammar that
calculate the value of expression
Production Semantic Rules
L→En print(E.val)
E → E1 + T E.val = E1.val + T.val
E→T E.val = T.val
T → T1 * F T.val = T1.val * F.val
T→F T.val = F.val
F→(E) F.val = E.val
F → digit F.val = digit.lexval
Input: 9+5+2n

• Symbols E, T, and F are associated with a synthesized

attribute val.
• The token digit has a synthesized attribute lexval
(it is assumed that it is evaluated by the lexical analyzer).
11
 Depth-First Traversals: Example
Input: 9+5+2n
L print (16)

E.val=16

E.val=14 T.val=2

E.val=9 F.val=2
T.val=5
Note: all attributes
T.val=9 in this example
F.val=5
are of synthesized
F.val=9 attributes

9 + 5 + 2 n 12
 Annotated Parse Tree: Example
Input: 5+3*4 L (print 17)

E.val=17 n

E.val=5 + T.val=12

T.val=5 T.val=3 * F.val=4

F.val=5 F.val=3 digit.lexval=4

digit.lexval=5 digit.lexval=3

13
 Quiz: Synthesized Attributed grammar that
calculate the value of expression

 Given the expression 5+3*4 followed by new line, the

program prints 17.

 Draw the decorated parse tree for input: 1*2n

 Draw the annotated parse tree for input: 5*3+4n

 Draw the annotated parse tree for input: 5*(3+4)n

14
 Exercises : Synthesized Attributed grammar
that calculate the value of expression
• By making use of SDD of slide 11: give annotated parse
trees for the following expressions:

a) (3+4) * (5+6)n
b) 7*5*9*(4+5)n
c) (9+8*(7+6)+5)*4n

15
 Dependency Graphs for Attributed Parse
Trees
• Annotated parse tree shows the values of attributes.
• Dependency graph helps us to determine how those
values can be computed.
• The attributes should be evaluated in a given order
because they depend on one another.
• The dependency of the attributes is represented by a
dependency graph.
• b(j) -----D()----> a(i) if and only if there exists a
semantic action such as a (i) := f (... b (j) ...)

16
 Dependency Graphs for
Attributed Parse Trees Direction of value
dependence
Synthesized A.a
attributes A.a= (X.x, Y.y)
X.x Y.y

A.a
A  XY X.x= (A.a, Y.y)
X.x Y.y

Inherited A.a
attributes
X.x Y.y Y.y= (A.a, X.x)

17
 Annotated Parse Tree: Example
Input: 5+3*4 L (print 17)

E.val=17 n

E.val=5 + T.val=12

T.val=5 T.val=3 * F.val=4

F.val=5 F.val=3 digit.lexval=4

digit.lexval=5 digit.lexval=3

18
 Dependency Graph
Input: 5+3*4 L (print 17)

E.val=17

E.val=5 T.val=12

T.val=5 T.val=3 F.val=4

F.val=5 F.val=3 digit.lexval=4

digit.lexval=5 digit.lexval=3

val is synthesized attribute

19
 Syntax-Directed Definition: Inherited
Attributes Inherited
Production Semantic Rules
D→TL L.inh = T.type
T → int T.type = integer
T → real T.type = real synthesized
L → L1 , id L1.inh = L.inh,
addtype(id.entry,L.inh)
L → id addtype(id.entry,L.inh)

• Symbol T is associated with a synthesized attribute

type.
• Symbol L is associated with an inherited attribute inh.
Input: real id1,id2,id3
20
 A Dependency Graph – Inherited Attributes
Input: real id1,id2,id3

T.type =real L.inh = real

real L.inh = real Id3.entry

Annotated ,
Parse tree
L.inh = real , Id2.entry

Id1.entry
21
 A Dependency Graph – Inherited Attributes
Input: real id1,id2,id3
D
1-10 represents
nodes of T1.type =real 4 5 L1.inh = real 6
Dependency
graph 3
real 7 L2.inh = real 8 Id3.entry
,
L3.inh = real Id2.entry 2
9 10 ,
Id1.entry
1
22
 SDD based on a grammar suitable for top-down
parsing
Production Semantic Rules
T → FT’ T’.inh = F.val
T.val = T’.syn
T’ → *FT1’ T1’.inh = T’.inh X F.val
T’.syn = T1’.syn
T’ → ε T’.syn = T’.inh
F → digit F.val = digit.lexval

• The SDD above computes terms like 3 * 5 and 3 * 5 * 7.

• Each of the non-terminals T and F has a synthesized attribute val;
• The terminal digit has a synthesized attribute lexval.
• The non-terminal T’ has two attributes:
• an inherited attribute inh and
• a synthesized attribute syn.
23
 Annotated parse tree for 3*5

T.val = 15

F.val = 3 T’.inh = 3
T’.syn = 15

digit.lexval = 3 T1’.inh = 15
* F.val = 5 T1’.syn = 15

digit.lexval = 5 ε

24
Dependency graph for the annotated parse tree
of 3*5
T.val = 15 9

F.val = 3 5 T’.inh = 3
3 T’.syn = 15 8

digit.lexval = 3 4 6 T1’.inh = 15
* F.val = 5 T1’.syn = 15 7
1

2
digit.lexval = 5 ε
Synthesized attribute
Inherited attribute
25
 Dependency graph: Exercises
Production Semantic Rules
N → L1.L2 N.v = L1.v + L2.v / (2L2.l)
L1 → L2 B L1.v = 2 * L2.v + B.v
L1.l = L2.l + 1
L→B L.v = B.v
L1.l = 1
B→0 B.v = 0
B→1 B.v = 1

 Draw the decorated parse tree and

 Draw the dependency graph for input:
a - 1011.01
b – 11.1
c – 1001.001
26
 Evaluation Order
• A topological sort of a directed acyclic graph (DAG) is
any ordering m1, m2, …, mn of the nodes of the graph,
such that:
if mi → mj is an edge, then mi appears before mj

• Any topological sort of a dependency graph gives a

valid evaluation order of the semantic rules.

27
 Example Parse Tree with Topologically Sorted
Actions
Topological sort:
1.Get id1.entry D
2.Get id2.entry
3.Get id3.entry
T1.type =real 4 5 L1.in = real
4.T1.type=real 6
5.L1.in=T1.type
6.addtype(id3.entry, 3
L1.in) real 7 L2.in = real 8 Id3.entry
7.L2.in=L1.in ,
8.addtype(id2.entry,
L2.in) L3.in = real Id2.entry 2
9.L3.in=L2.in 9 10 ,
10.addtype(id1.entry,
L3.in) Id1.entry
1
28
 S-Attributed Definitions
• Syntax-directed definitions are used to specify syntax-directed
translations that guarantee an evaluation order.
• We would like to evaluate the semantic rules during parsing
(i.e. in a single pass, we will parse and we will also evaluate
semantic rules during the parsing).
• We will look at two sub-classes of the syntax-directed
definitions:
– S-Attributed Definitions: only synthesized attributes used
in the syntax-directed definitions.
– L-Attributed Definitions: in addition to synthesized
attributes, we may also use inherited attributes.

• These classes of SDD can be implemented efficiently in

connection with top-down and bottom-up parsing.

29
 S-Attributed Definitions
• A syntax-directed definition that uses synthesized
attributes exclusively is called an S-attributed
definition (or S-attributed grammar)

• A parse tree of an S-attributed definition is annotated

with a single bottom-up traversal.
• Bottom-up parser uses depth first traversal.
• A new stack is maintained to store the values of the
attributes as in the following example.

• Yacc/Bison only support S-attributed definitions

30
 Example: Attribute Grammar in Yacc

%{
#include <stdio.h>
void yyerror(char *);
%}
%token INTEGER
%%
program:
program expr '\n' { printf("%d\n", $2); }
|
;
expr:
INTEGER { $$=$1;}
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
; Synthesized
%% attribute of
parent node expr
31
 Bottom-Up Evaluation of S-Attributed
Definitions
• We put the values of the synthesized attributes of the grammar symbols into
a parallel stack.
– When an entry of the parser stack holds a grammar symbol X (terminal
or non-terminal), the corresponding entry in the parallel stack will hold
the synthesized attribute(s) of the symbol X.
• We evaluate the values of the attributes during reductions.

A  XYZ A.a=f(X.x,Y.y,Z.z) where all attributes are synthesized.

stack parallel-stack
top  Z Z.z
Y Y.y
X X.x top A A.a
. . . .
32
 Bottom-Up Eval. of S-Attributed Definitions…
Production Semantic Rules
L→En print(val[top-1])
E → E1 + T val[ntop] = val[top-2] + val[top]
E→T $$ = $1 + $3; in yacc
T → T1 * F val[ntop] = val[top-2] * val[top]
T→F
F→(E) val[ntop] = val[top-1]
F → digit
• At each shift of digit, we also push digit.lexval into val-stack.
• At all other shifts, we do not put anything into val-stack
because other terminals do not have attributes (but we
increment the stack pointer for val-stack).
33
 Canonical LR(0) Collection for The Grammar
.. L . . .
I0: L’→
.
L I1: L’→L I7: L →En I11: E →E+T *

.. .. .
n 9
L→ En T T →T *F
E→
E→
..
E+T E
T
I2: L →E n
E →E +T
+
..
I8: E →E+ T
T → T*F (
F 4

.. ..
5
T→ T*F T→ F d

..
T→ F T I3: E →T F → (E) 6
F→ (E) T →T *F F→ d
F→ d
F . *

.
I4: T →F

. ..
I9: T →T* F F
I12: T →T*F .
(
I5 : F →
E→ .. ( E)
E+T
F → (E)
F → id (
5

..
E→ T E d

..
6

.
T→ T*F
T→
F→
F→
.. F
(E)
d
T
F
3
I10: F →(E )
E →E +T
)
+
I13: F →(E)

4 8
d
I6: F →d . (
d
5
6

34
 Bottom-Up Evaluation of S-Attributed
Definitions in Yacc: Example
• At each shift of digit, we also push digit.lexval into val-stack.
stack val-stack input action semantic rule
0 5+3*4n s6 d.lexval(5) into val-stack
0d6 5 +3*4n F→d F.val=d.lexval – do nothing
0F4 5 +3*4n T→F T.val=F.val – do nothing
0T3 5 +3*4n E→T E.val=T.val – do nothing
0E2 5 +3*4n s8 push empty slot into val-stack
0E2+8 5- 3*4n s6 d.lexval(3) into val-stack
0E2+8d6 5-3 *4n F→d F.val=d.lexval – do nothing
0E2+8F4 5-3 *4n T→F T.val=F.val – do nothing
0E2+8T11 5-3 *4n s9 push empty slot into val-stack
0E2+8T11*9 5-3- 4n s6 d.lexval(4) into val-stack
0E2+8T11*9d6 5-3-4 n F→d F.val=d.lexval – do nothing
0E2+8T11*9F12 5-3-4 n T→T*F T.val=T1.val*F.val
0E2+8T11 5-12 n E→E+T E.val=E1.val*T.val
0E2 17 n s7 push empty slot into val-stack
0E2n7 17- $ L→En print(17), pop empty slot from val-stack
0L1 17 $ acc

35