Principles of Compiler Design

Course Outline
1. Introduction
2. Lexical Analysis
3. Syntax Analysis
4. Syntax Directed Translation
5. Symbol Tables & Type Checking
6. Intermediate Code Generation
7. Run Time Environment
8. Code Generation
9. Code Optimization
By: Yohannes Taye Jemberie 1
Chapter 3: Syntax Directed Translation
Syntax directed definitions
Synthesized Vs Inherited Attributes
Semantic Rules
Dependency Graph
S-Attributed grammars (S-attributed SDT)
 L-Attributed grammars (L-attributed SDT)
 Syntax Directed Translation
• Parsing an input to do nothing about it is
useless.
• Various actions can be performed while doing
parsing.
• These actions are done by semantic actions
associated to the different rules of the
grammar.

By: Yohannes Taye Jemberie 3

 Syntax directed definitions
• SDT=Grammar + Semantic Rules
• A syntax directed definition is a generalization
of the CFG in which each grammar symbol has
an associated set of attributes (synthesized
and inherited).
• An attribute can represent anything we
choose ( a string, a number, a type, a memory
location, etc.)

By: Yohannes Taye Jemberie 4

• Ex: SDT for evaluation of expressions

E->E+T {E.value=E.value + T.value}

/T {E.value= T.value}

T->T*F {T.value=T.value * F.value}

/F {T.value= F.value}

F->num {F.value= num.lvalue}

By: Yohannes Taye Jemberie 5

Eg: For the input 2+3*4, show its
evaluation

By: Yohannes Taye Jemberie 6

• Ex: SDT for Infix to postfix conversion
expressions
E->E+T {print(“+”);}
/T { }

T->T*F {print(“*”);}

/F {}

F->num {print(num.lvalue);}

By: Yohannes Taye Jemberie 7

EX: 2 + 3*4

By: Yohannes Taye Jemberie 8

• Ex: Given the SDT below:

S->xxW {print(“1”);}
/y {print(“1”);}

W->Sz {print(“3”);}

Find the output for the string:

xxxxyzz By: Yohannes Taye Jemberie 9
Ex: SDT for evaluation of expressions

E->E*T {E.value=E.value * T.value}

/T {E.value= T.value}

T->F-T {T.value=F.value - T.value}

/F {T.value= F.value}

F->2 {F.value= 2;}

/4 {F.value= 4;}

W=4-2-4*2 By: Yohannes Taye Jemberie 10

Ex: SDT for evaluation of expressions

E->E#T {E.value=E.value * T.value}

/T {E.value= T.value}

T->T&F {T.value=T.value + F.value}

/F {T.value= F.value}

F->num {F.value= num.lval;}

W=2#3&5#6&4
By: Yohannes Taye Jemberie 11
 Synthesized Vs Inherited Attributes
• 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.

By: Yohannes Taye Jemberie 12

 Semantic Rules
• Semantic rules calculate the values of attributes.
• Hence they setup dependencies between
attributes that will be represented by a graph.
• The dependency graph enables to find an
evaluation order for the semantic rules.
• A parse tree showing the values of the attributes
is called an annotated or decorated parse tree.

By: Yohannes Taye Jemberie 13

 EX: SDT that generates binary numbers
Count no. of 0’s Count no. of 1’s Count no. of bits

N->L {N.count=L.count;} {N.count=L.count;} {N.count=L.count;}

L->LB {L.count=L1.count + {L.count=L1.count + {L.count=L1.count +

B.count} B.count} B.count}

/B {L.count=B.count;} {L.count=B.count;} {L.count=B.count;}

B-> 0 {B.count=1;} {B.count=0;} {B.count=1;}

/1 {B.count=0;} {B.count=1;} {B.count=1;}

By: Yohannes Taye Jemberie 14

 Binary to decimal conversion
Eg:
11 : 3 101:5

1011 10110
11*2+0=22
1*2
+0=2
2*2
+1=5
5*2
+1=11

By: Yohannes Taye Jemberie 15

10111
11*2+1=23

By: Yohannes Taye Jemberie 16

EX: SDT that generates binary numbers

N->L {N.dval=L.dval;}

L->LB {L.dval=L1.dval * 2 + B.dval}

/B {L.dval=B.dval;}

B-> 0 {B.dval=0;}

/1 {B.dval=1;}

Eg: w=1011
By: Yohannes Taye Jemberie 17
 Number with binary point to decimal

Eg: 11.01 = 3 + 1 = 3.25

22

1101.011 = 13 + 3 = 13.375
23

By: Yohannes Taye Jemberie 18

 Example 1
Syntax rules Semantic rules
N  L1. L2 N.dval = L1.dval + L2.dval / (2L2.count)

L1  L2 B L1.dval = 2 * L2.dval + B.dval

L1.count = L2.count + 1

L B L.dval = B.dval
L.count = 1

B 0 B.dval = 0; B.count=1

B 1 B.v = 1;B.count=1
How many attributes are there? Which are synthesized? Which are in
Exercise: Draw the decorated parse tree for input 1011.01
By: Yohannes Taye Jemberie 19
 Example 1 (cont’d)
• In the above example, everything is calculated
from leaves to root
 all attributes (i.e l & v) are synthesized.

By: Yohannes Taye Jemberie 20

 Example 2
Syntax rules Semantic rules
N  L1 . L2 N.v = L1.v + L2.v
L1.s = 0
L2.s = -L2.l

L1  L2 B L1.l = L2.l + 1
L2.s = L1.s + 1
B.s = L1.s
L1.v = L2.v + B.v

L B L.v = B.v
L.l = 1
B.s = L.s

B 0 B.v = 0

B 1 B.v = l * 2B.s

Exercise: Draw the decorated parse tree for input 1011.01

By: Yohannes Taye Jemberie 21
 Formal definition
• In a syntax directed definition, each grammar production A 
α has associated with it a set of semantic rules of the form:
b := f (c1, c2, .... ck) where
– f is a function and
– b, c1, ... ck are attributes of A and the symbols at the right side of the
production.
• We say that:
– b is synthesized attribute of A if c1, c2, ...ck are attributes belonging to
the grammar symbols of the production and,
– b is inherited attribute of one of the grammar symbols on the right
side of the production if c1, c2, ...ck are attributes belonging to the
grammar symbols of the production and,
– In either case, we say that attribute b depends on attributes c1, c2,
...........ck.

By: Yohannes Taye Jemberie 22

 Example 3
Note: num.value is the attribute of num that gives its value.

Syntax Rule Semantic rule

E1  E2 + T E1.v := E2.v + T.v

E T E.v := T.v

T1  T2 * F T1.v := T2.v * F.v

T F T.v := F.v

F  num F.v := num.value

F  (E) F.v := E.v

Exercise: Draw the decorated tree for the input 3 * 2

By: Yohannes Taye Jemberie 23

 Example 4
Syntax Rule Semantic rule
D TL L.in := T.type

T  int T.type := int

T  float T.type := float

L  ident ident.type := L.in

L1  L2, ident L2.in := L1.in

ident.type := L1.in
Note:
Here, the semantic action of an ident may have the side effect of adding
the type in the symbol table for that particular identifier.
Exercise: Draw the decorated tree for the input int x, y

By: Yohannes Taye Jemberie 24

 Evaluation order
• 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) ...)

By: Yohannes Taye Jemberie 25

 Dependency Graph
• Algorithm for the construction of the dependency graph

For each node n in the parse tree do

For each attribute a of the grammar symbol at n do
Construct a node in the dependency graph for a

For each node n in the parse tree do

For each semantic rule b := f (c1, c2, ... ck) associated with the
production used at n do
For i:= 1 to k do
Construct an edge from the node for ci to the
node for b;

By: Yohannes Taye Jemberie 26

 Dependency Graph (cont’d)
• Draw the dependency graphs for Example 3
and Example 4

By: Yohannes Taye Jemberie 27

 Evaluation order
• Several methods have been proposed for evaluating semantic
rules:

• Parse rule based methods: for each input, the compiler finds
an evaluation order. These methods fail only if the
dependency graph for that particular parse tree has a cycle.

• Rule based methods: the order in which the attributes

associated with a production are evaluated is predetermined
at compiler-construction time. For this method, the
dependency graph need not be constructed.

• Oblivious methods: The evaluation order is chosen without

considering the semantic rules. This restricts the class of
syntax directed definition that can be used.

By: Yohannes Taye Jemberie 28

 S-Attributed grammars
(S-attributed SDT)
• An attributed grammar is S-Attributed when
all of its attributes are synthesized. i.e. it
doesn't have inherited attributes.
• Synthesized attributes can be evaluated by a
bottom-up parser as the input is being parsed.
• A new stack will be maintained to store the
values of the attributes as in the example
below.

By: Yohannes Taye Jemberie 29

 S-Attributed grammars (cont’d)
Example:
E  E1 + E2 { E.v = E1.v + E2.v }
Val(newTop) = Val(oldTop) + Val(oldTop – 2)
$$ = $1 + $3 (in Yacc)
• We assume that the synthesized attributes are evaluated just
before each reduction.
• Before the reduction, attribute of E is in Val(Top) and attributes
of E1 and E2 are in Val (Top – 1) and Val(Top - 2) respectively.
• After the reduction, E is put at the top of the State stack and its
attribute values are put at the top of Value stack.

By: Yohannes Taye Jemberie 30

 S-Attributed grammars (cont’d)
• The semantic actions that reference the
attributes of the grammar will in fact be
translated by the Compiler generator (such as
Yacc) into codes that reference the value
stack.

By: Yohannes Taye Jemberie 31

• Summary of S-attributed SDT
1)Uses only synthesized attributes
2)Attributes are evaluated in Bottom Up parsing

By: Yohannes Taye Jemberie 32

 L-Attributed grammars
(L-attributed SDT)
• It is difficult to execute the tasks of the compiler just
by synthesized attributes.
• The L-attributed class of grammars allow a limited
kind of inherited attributes.
Definition: A grammar is L-Attributed if and only if for each
rule X0  X1 X2 ... Xj ... XN, all inherited attributes of Xj depend
only on:
– Attributes of X1, ... Xj-1
– Inherited attributes of X0
• Of course all S-attributed grammars are L-attributed.

By: Yohannes Taye Jemberie 33

 L-Attributed grammars (cont’d)
Example:
A LM { L.h = f1 (A.h)
M.h = f2 (L.s)
A.s = f3 (M.s) }
Does this production contradict the rules?
No  the corresponding grammar may be L-
attributed if all of the other productions
follow the rule of L-attributed grammars.
By: Yohannes Taye Jemberie 34
 L-Attributed grammars (cont’d)
Example:
A QR { R.h = f4 (A.h)
Q.h = f5 (R.s)
A.s = f6 (Q.s) }
Does this production contradict the rules?
Yes, since Q.h depends on R.s
 The grammar containing this production is
not L-Attributed.

By: Yohannes Taye Jemberie 35

• Summary of L(left)-attributed SDT
• Uses both inherited and synthesized attributes
• Each inherited attribute is restricted to inherit
either from parent or left sibling only.

By: Yohannes Taye Jemberie 36

Consider the following SDTs
1)A->LM {L.i=f(A.i) ; A.s=f(M.s);}
2) A->QR {R.i=f(A.i);Q.i=f(R.i);A.s=f(Q.s);}
3)A->BC {B.s=A.s}

By: Yohannes Taye Jemberie 37