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
• Top-Down Evaluation of S-Attributed Definitions
• L-Attributed Definitions
• Translation Schemes
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
 Attribute Grammar
• So, a semantic rule b=f(c1,c2,…,cn) indicates that the
attribute b depends on attributes c1,c2,…,cn.

• In a syntax-directed definition, a semantic rule:

– may just evaluate a value of an attribute or
– it may have some side effects such as printing values.

• An attribute grammar is a syntax-directed definition in which

the functions in the semantic rules cannot have side effects
(they can only evaluate values of attributes).

8
 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.

9
 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

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

 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.

11
 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

• 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).
12
 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 F.val=5 in this example
are of synthesized
F.val=9 attributes

9 + 5 + 2 n 13
 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

14
 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

15
 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

16
 Syntax-Directed Definition: 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 for input:

a - 1011.01
b – 11.1
c – 1001.001
17
 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) ...)
• Algorithm for the construction of the dependency graph

18
 Dependency graph : Algorithm

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;

19
 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.x= (A.a, X.x)

20
 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

21
 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

22
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.
23
 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
24
 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 Id3.entry
8
,

L3.inh = real Id2.entry 2

9 10 ,
Id1.entry
1
25
 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.
26
 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 ε

27
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
Synthesized attribute digit.lexval = 5 ε
Inherited attribute
28
 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
29
 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.

• Note: It is not possible to find such an order for an

acyclic graph.
30
 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 Id3.entry
8
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
31
 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.

32
 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

33
 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
34
 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 
topX.x A A.a
. . . .
35
 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).
36
 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

37
 Bottom-Up Evaluation -- 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
0T35 +3*4n E→T E.val=T.val – do nothing
0E25 +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
0E217 n s7 push empty slot into val-stack
0E2n7 17- $ L→En print(17), pop empty slot from val-stack
0L117 $ acc

38
Top-Down Evaluation of S-Attributed Definitions

Productions Semantic Rules

A→B print(B.n0), print(B.n1)
B → 0 B1 B.n0=B1.n0+1, B.n1=B1.n1
B → 1 B1 B.n0=B1.n0, B.n1=B1.n1+1
B→ B.n0=0, B.n1=0

where B has two synthesized attributes (n0 and n1).

39
Top-Down Evaluation of S-Attributed Definitions
• In a recursive predictive parser, each non-terminal corresponds
to a procedure.

procedure A() {
call B(); A→B
}
procedure B() {
if (currtoken=0) { consume 0; call B(); } B→0B
else if (currtoken=1) { consume 1; call B(); } B→1B
else if (currtoken=$) {} // $ is end-marker B→
else error(“unexpected token”);
}

40
Top-Down Evaluation of S-Attributed Definitions
procedure A() {
int n0,n1; Synthesized attributes of non-terminal B
call B(&n0,&n1); are the output parameters of procedure B.
print(n0); print(n1);
} All the semantic rules can be evaluated
procedure B(int *n0, int *n1) { at the end of parsing of production rules
if (currtoken=0)
{int a,b; consume 0; call B(&a,&b); *n0=a+1; *n1=b;}
else if (currtoken=1)
{ int a,b; consume 1; call B(&a,&b); *n0=a; *n1=b+1; }
else if (currtoken=$) {*n0=0; *n1=0; } // $ is end-marker
else error(“unexpected token”);
}

41
 L-Attributed Definitions
• S-Attributed Definitions can be efficiently implemented.
• We are looking for a larger (larger than S-Attributed
Definitions) subset of syntax-directed definitions which
can be efficiently evaluated.

L-Attributed Definitions

• L-Attributed Definitions can always be evaluated by the

depth first visit of the parse tree.
• This means that they can also be evaluated during the
parsing.

42
 L-Attributed Definitions
• A syntax-directed definition is L-attributed if each
inherited attribute of Xj, where 1jn, on the right side
of A → X1X2...Xn depends only on:
1. The attributes of the symbols X1,...,Xj-1 to the left of Xj in the
production and
2. the inherited attribute of A A.a

A → X1X2
Dependency of X2.x
inherited attributes X1.x

43
 L-Attributed Definitions
• L-attributed definitions allow for a natural order of
evaluating attributes: depth-first and left to right.
A XY
X.i=A.i A.s=Y.s
X.i = A.i A
A.s= Y.s
Y.i= X.s
X Y.i=X.s Y

Every S-attributed definition is L-attributed, the restrictions

only apply to the inherited attributes (not to synthesized
attributes). 44
 A Definition which is NOT L-Attributed
Productions Semantic Rules
A→LM L.in=l(A.i), M.in=m(L.s), A.s=f(M.s)
A→QR R.in=r(A.in), Q.in=q(R.s), A.s=f(Q.s)

• This syntax-directed definition is not L-attributed because the

semantic rule Q.in=q(R.s) violates the restrictions of L-attributed
definitions.
• When Q.in must be evaluated before we enter to Q because it is an
inherited attribute.
• But the value of Q.in depends on R.s which will be available after
we return from R.
• So, we are not be able to evaluate the value of Q.in before we
enter to Q.
45
 Example: L-attributed definition
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.
46
 Exercises
• Suppose that we have a production A → BCD. Each of the
four non-terminals A, B, C, and D have two attributes:
– s is a synthesized attribute, and
– i is an inherited attribute.
• For each of the sets of rules below, tell whether:
(i) the rules are consistent with an S-attributed definition
(ii) The rules are consistent with an L-attributed definition,
and
(iii) whether the rules are consistent with any evaluation
order at all?

47
 Exercises…

1) A.s = B.i + C.c

2) A.s = B.i + C.c and D.i = A.i + B.s
3) A.s = B.s + D.s
4) A.s = D.i, B.i = A.s + C.s, C.i = B.s, and D.i = B.i + C.i

48
 Translation Schemes
• In a syntax-directed definition, we do not say anything about
the evaluation times of the semantic rules (when the semantic
rules associated with a production should be evaluated?).

• A translation scheme is a context-free grammar in which:

– attributes are associated with the grammar symbols and
– semantic actions enclosed between braces { } are inserted
within the right sides of productions.

• Ex: A → { ... } X { ... } Y { ... }

Semantic Actions
49
 Translation Schemes
• When designing a translation scheme, some restrictions should
be observed to ensure that an attribute value is available when
a semantic action refers to that attribute.
• These restrictions (motivated by L-attributed definitions) ensure
that a semantic action does not refer to an attribute that has
not yet computed.
• In translation schemes, we use semantic action terminology
instead of semantic rule terminology used in syntax-directed
definitions.
• The position of the semantic action on the right side indicates
when that semantic action will be evaluated.

50
 Translation Schemes for S-attributed
Definitions
• If our syntax-directed definition is S-attributed, the
construction of the corresponding translation scheme will be
simple.
• Each associated semantic rule in a S-attributed syntax-directed
definition will be inserted as a semantic action into the end of
the right side of the associated production.
Production Semantic Rule
E → E1 + T E.val = E1.val + T.val a production of
a syntax directed definition

E → E1 + T { E.val = E1.val + T.val } the production of the corresponding

translation scheme

51
 A Translation Scheme Example
• A simple translation scheme that converts infix expressions to
the corresponding postfix expressions.

E→TR
R → + T { print(“+”) } R1
R→
T → id { print(id.name) }

a+b+c ab+c+

infix expression postfix expression

52
 A Translation Scheme: Example…
E

T R

id {print(“a”)} + T {print(“+”)} R

id {print(“b”)} + T {print(“+”)} R

id {print(“c”)} 

The depth first traversal of the parse tree (executing the semantic actions in
that order) will produce the postfix representation of the infix expression.
53
 Inherited Attributes in Translation Schemes
• If a translation scheme has to contain both synthesized and inherited
attributes, we have to observe the following rules:
1. An inherited attribute of a symbol on the right side of a production
must be computed in a semantic action before that symbol.
2. A semantic action must not refer to a synthesized attribute of a
symbol to the right of that semantic action.
3. A synthesized attribute for the non-terminal on the left can only be
computed after all attributes it references have been computed (we
normally put this semantic action at the end of the right side of the
production).
• With L-attributed syntax-directed definition, it is always possible to
construct a corresponding translation scheme which satisfies these
three conditions (This may not be possible for a general syntax-
directed translation).
54
 Top-Down Translation
• We will look at the implementation of L-attributed
definitions during predictive parsing.

• We will see how to evaluate inherited attributes (in L-

attributed definitions) during recursive predictive
parsing.
• We will also look at what happens to attributes during
the left-recursion elimination in the left-recursive
grammars.

55
 A Translation Scheme with Inherited
Attributes
D → T id { addtype(id.entry,T.type), L.in = T.type } L
T → int { T.type = integer }
T → real { T.type = real }
L → id { addtype(id.entry,L.in), L1.in = L.in } L1
L→

• This is a translation scheme for an L-attributed

definitions.

56
Predictive Parsing (of Inherited Attributes)
procedure D() {
int Ttype,Lin,identry;
call T(&Ttype); consume(id,&identry){
addtype(identry,Ttype); Lin=Ttype;}
call L(Lin); a synthesized attribute (an output parameter)
}
procedure T(int *Ttype) {
if (currtoken is int) { consume(int); *Ttype=TYPEINT; }
else if (currtoken is real) { consume(real); *Ttype=TYPEREAL; }
else { error(“unexpected type”); } an inherited attribute (an input parameter)
}
procedure L(int Lin) {
if (currtoken is id) { int L1in,identry; consume(id,&identry){
addtype(identry,Lin); L1in=Lin; call L(L1in); }}
else if (currtoken is endmarker) { }
else { error(“unexpected token”); }
}
57
 Eliminating Left Recursion from
Translation Scheme
A → A1 Y { A.a = g(A1.a,Y.y) } a left recursive grammar with
A → X { A.a=f(X.x) } synthesized attributes (a,y,x).

eliminate left recursion

inherited attribute of the new non-terminal
synthesized attribute of the new non-terminal

A → X { R.in=f(X.x) } R { A.a=R.syn }
R → Y { R1.in=g(R.in,Y.y) } R1 { R.syn = R1.syn}
R →  { R.syn = R.in }
58
 Evaluating attributes
A parse tree of left recursive grammar

A Y A.a=g(f(X.x),Y.y)
parse tree of non-left-recursive grammar
X X.x=f(X.x) A

X R.in=f(X.x) R A.a=g(f(X.x,Y.y)

Y R1.in=g(f(X.x),Y.y) R1 R.syn=g(f(X.x),Y.y)

 R1.syn=g(f(X.x),Y.y)

59
Eliminating Left Recursion from Translation
Scheme
• A translation scheme with a left recursive grammar.

E → E1 + T { E.val = E1.val + T.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 }

• When we eliminate the left recursion from the grammar (to get a
suitable grammar for the top-down parsing) we also have to
change semantic actions
60
 Eliminating Left Recursion (cont.)
inherited attribute synthesized attribute

E → T { A.in=T.val } A { E.val=A.syn }
A → + T { A1.in=A.in+T.val } A1 { A.syn = A1.syn}
A → - T { A1.in=A.in-T.val } A1 { A.syn = A1.syn}
A →  { A.syn = A.in }
T → F { B.in=F.val } B { T.val=B.syn }
B → * F { B1.in=B.in*F.val } B1 { B.syn = B1.syn}
B →  { B.syn = B.in }
F → ( E ) { F.val = E.val }
F → digit { F.val = digit.lexval }
61
 Syntax-Directed Definition – Example
Production Semantic Rules
E → E1 + T E.loc=newtemp(), E.code = E1.code || T.code || add E1.loc,T.loc,E.loc
E→T E.loc = T.loc, E.code=T.code
T → T1 * F T.loc=newtemp(), T.code = T1.code || F.code || mult T1.loc,F.loc,T.loc
T→F T.loc = F.loc, T.code=F.code
F→(E) F.loc = E.loc, F.code=E.code
F → id F.loc = id.name, F.code=“”

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

loc and code.
• The token id has a synthesized attribute name (it is assumed
that it is evaluated by the lexical analyzer).
• It is assumed that || is the string concatenation operator.

62
 Translation Scheme - Intermediate Code
Generation
E → T { A.in=T.loc } A { E.loc=A.loc }
A → + T { A1.in=newtemp(); emit(add,A.in,T.loc,A1.in) }
A1 { A.loc = A1.loc}
A →  { A.loc = A.in }
T → F { B.in=F.loc } B { T.loc=B.loc }
B → * F { B1.in=newtemp(); emit(mult,B.in,F.loc,B1.in) }
B1 { B.loc = B1.loc}
B →  { B.loc = B.in }
F → ( E ) { F.loc = E.loc }
F → id { F.loc = id.name }

63
 Bottom-Up Evaluation of Inherited
Attributes

• Using a top-down translation scheme, we can implement any

L-attributed definition based on LL(1) grammar.

• Using a bottom-up translation scheme, we can also implement

any L-attributed definition based on a LL(1) grammar (each
LL(1) grammar is also an LR(1) grammar).

• In addition to the L-attributed definitions based on LL(1)

grammars, we can implement some of L-attributed definitions
based on LR(1) grammars (not all of them) using the bottom-up
translation scheme.

64
 Implementing L-Attributed
Definitions in Bottom-Up Parsers

• More difficult and also requires rewriting L-attributed

definitions into translation schemes
• Insert marker non-terminals to remove embedded actions from
translation schemes, that is
A  X {actions } Y
Is written with marker non-terminal N into
AXNY
N  ε {actions}
• Problem: inserting a marker non-terminal may introduce a
conflict in the parse table

65
 Removing Embedding Semantic Actions
• In bottom-up evaluation scheme, the semantic actions are
evaluated during the reductions.
• During the bottom-up evaluation of S-attributed definitions, we
have a parallel stack to hold synthesized attributes.
• Problem: where are we going to hold inherited attributes?
• A Solution:
– We will convert our grammar to an equivalent grammar to guarantee to
the followings.
– All embedding semantic actions in our translation scheme will be moved
into the end of the production rules.
– All inherited attributes will be copied into the synthesized attributes
(most of the time synthesized attributes of new non-terminals).
– Thus we will be evaluating all semantic actions during reductions, and
we find a place to store an inherited attribute.

66
 Removing Embedding Semantic Actions
• To transform our translation scheme into an equivalent
translation scheme:

1. Remove an embedding semantic action Si, put new a non-

terminal Mi instead of that semantic action.
2. Put that semantic action Si into the end of a new production
rule Mi for that non-terminal Mi.
3. That semantic action Si will be evaluated when this new
production rule is reduced.
4. The evaluation order of the semantic rules are not changed by
this transformation.

67
 Removing Embedding Semantic Actions
A {S1} X1 {S2} X2 ... {Sn} Xn

remove embedding semantic actions

A M1 X1 M2 X2 ... Mn Xn
M1 {S1}
M2 {S2}
.
.
Mn {Sn}

68
 Removing Embedding Semantic Actions
E→TR
R → + T { print(“+”) } R1
R→
T → id { print(id.name) }

remove embedding semantic actions

E→TR
R → + T M R1
R→
T → id { print(id.name) }
M →  { print(“+”) }

69
 Translation with Inherited Attributes
• Let us assume that every non-terminal A has an inherited
attribute A.i, and every symbol X has a synthesized
attribute X.s in our grammar.
• For every production rule A X1 X2 ... Xn ,
– introduce new marker non-terminals M1,M2,...,Mn and
– replace this production rule with A M1 X1 M2 X2 ... Mn Xn
– the synthesized attribute of Xi will not be changed.
– the inherited attribute of Xi will be copied into the synthesized
attribute of Mi by the new semantic action added at the end of
the new production rule Mi.
– Now, the inherited attribute of Xi can be found in the synthesized
attribute of Mi (which is immediately available in the stack).

70
 Translation with Inherited Attributes…

A  {B.i=f1(...)} B {C.i=f2(...)} C {A.s= f3(...)}

A  {M1.i=f1(...)} M1 {B.i=M1.s} B {M2.i=f2(...)} M2 {C.i=M2.s} C {A.s=

f3(...)}
M1 {M1.s=M1.i}
M2 {M2.s=M2.i}

71
 Translation with Inherited Attributes…
S  {A.i=1} A {S.s=k(A.i,A.s)}
A  {B.i=f(A.i)} B {C.i=g(A.i,B.i,B.s)} C {A.s= h(A.i,B.i,B.s,C.i,C.s)}
B  b {B.s=m(B.i,b.s)}
C  c {C.s=n(C.i,c.s)}

S  {M1.i=1} M1 {A.i=M1.s} A {S.s=k(M1.s,A.s)}

A  {M2.i=f(A.i)} M2 {B.i=M2.s} B {M3.i=g(M1.s,M2.s,B.s)} M3 {C.i=M3.s} C {A.s=
h(M1.s, M2.s,B.s, M3.s,C.s)}
B  b {B.s=m(M2.s,b.s)}
C  c {C.s=n(M3.s,c.s)}
M1 {M1.s=M1.i}
M2 {M2.s=M2.i}
M3 {M3.s=M3.i}

72
 Actual Translation Scheme
S  {M1.i=1} M1 {A.i=M1.s} A {S.s=k(M1.s,A.s)}
A  {M2.i=f(A.i)} M2 {B.i=M2.s} B {M3.i=g(M1.s,M2.s,B.s)} M3 {C.i=M3.s} C {A.s= h(M1.s,
M2.s,B.s, M3.s,C.s)}
B  b {B.s=m(M2.s,b.s)}
C  c {C.s=n(M3.s,c.s)}
M1 {M1.s= M1.i}
M2 {M2.s=M2.i}
M3 {M3.s=M3.i}

S  M1 A { s[ntop]=k(s[top-1],s[top]) }
M1  { s[ntop]=1 }
A  M2 B M3 C { s[ntop]=h(s[top-4],s[top-3],s[top-2],s[top-1],s[top]) }
M2  { s[ntop]=f(s[top]) }
M3  { s[ntop]=g(s[top-2],s[top-1],s[top])}
Bb { s[ntop]=m(s[top-1],s[top]) }
Cc { s[ntop]=n(s[top-1],s[top]) } 73
 Evaluation of Attributes
S
S.s=k(1,h(..))
A.i=1
A
A.s=h(1,f(1),m(..),g(..),n(..))

B.i=f(1) C.i=g(1,f(1),m(..))
B C
B.s=m(f(1),b.s) C.s=n(g(..),c.s)

b c

74
 Evaluation of Attributes
stack input s-attribute stack
bc$
M1 bc$ 1
M1 M2 bc$ 1 f(1)
M1 M2 b c$ 1 f(1) b.s
M1 M2 B c$ 1 f(1) m(f(1),b.s)
M1 M2 B M3 c$ 1 f(1) m(f(1),b.s) g(1,f(1),m(f(1),b.s))
M1 M2 B M3 c $ 1 f(1) m(f(1),b.s) g(1,f(1),m(f(1),b.s)) c.s
M1 M2 B M3 C $ 1 f(1) m(f(1),b.s) g(1,f(1),m(f(1),b.s)) n(g(..),c.s)
M1 A $ 1 h(f(1),m(..),g(..),n(..))
S $ k(1,h(..))
75
 Problems
• All L-attributed definitions based on LR grammars cannot be
evaluated during bottom-up parsing.

S  { L.i=0 } L  this translations scheme cannot be implemented

L  { L1.i=L.i+1 } L1 1 during the bottom-up parsing
L   { print(L.i) }

S  M1 L
L  M2 L1 1  But since L   will be reduced first by the bottom-up
L   { print(s[top]) } parser, the translator cannot know the number of 1s.
M1   { s[ntop]=0 }
M2   { s[ntop]=s[top]+1 }

76
 Problems
• The modified grammar cannot be LR grammar anymore.

LLb LMLb
La  La NOT LR-grammar
M

.L, $
S’ 
L . M L b, $
L . a, $
M .,a  shift/reduce conflict

77