✬ ✩

Compiler Design IIIT Kalyani, WB 1

SDD, Attribute Grammar and SDT

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 2

Translation

• So far we have talked about parsinga of a

language. But our main goal is translation.
• Semantic actions to translate the source
language program to a target language
program often go hand-in-hand with parsing.
It is called syntax-directed translation.
a Even the parsing cannot be completed without some analysis beyond the
context-free structure.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 3

Translation

• To perform semantic actions along with

parsing actions (e.g. reduction), we associate
computation with the production rules.
Computed information is propagated as
attributes of non-terminals.
• An alternative is to be built the parse tree
explicitly, and perform semantic actions by
traversing the tree.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 4

Example

Consider the following production rule of the

classic expression grammar: E → E1 + T a .
We consider three different translations:
• implementation of a simple calculator,
• conversion of an infix expression to a postfix
expression,
• general purpose code generation.
a We

✫ ✪
have used subscript to differentiate between two instances of E.

Lect 9 Goutam Biswas

 ✬ ✩
Compiler Design IIIT Kalyani, WB 5

Example: Calculator

• We have already seen that the only attribute

of E and T required for this translation are
values expressions corresponding to the
sub-trees of E and T .
• Let us call the attribute to be val.
• The semantic action associated with the
given production rule is,
E → E1 + T {E·val = E1 ·val + T ·val}a .
✫ ✪
a In bison this gets translated to $$ = $1 + $3.

Lect 9 Goutam Biswas

 ✬ ✩
Compiler Design IIIT Kalyani, WB 6

Note

• The action may take place when E1 + T is

reduced to E. The computed value is saved
as the attribute of E.
• Alternatively, it may take place during the
postorder traversal of the syntax tree.
• There is no other side-effect of the semantic
action.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 7

Note

• But if we want to keep a provision to store a

value as a named object (variable), we need
a symbol table where the variables names
and their values are stored.
• In that case the semantic action of
ES → id := E will changes the state of the
symbol-table data structure (side effect) by
entering the E·val corresponding to id.name.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 8

Example: Infix to Postfix Conversion

• Here the problem is to convert an infix

arithmetic expression to an equivalent
postfix expression.
• Both the input and output are strings of
characters.
• Let the attribute associated to each
non-terminal be exp of type char *. The
semantic action is the following.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 9

Example: Infix to Postfix

E → E1 + T
{
E.exp=(char*)malloc(strlen(E1.exp)+
strlen(T.exp)+4);
strcpy(E.exp, E1.exp); strcat(E.exp, " ");
strcat(E.exp, T.exp);
strcat(E.exp, " + ");
free(E1.exp); free(T.exp);
}
Again there is no side-effect
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 10

Example: Code Generation

• The main difference of translation for code

generation with two previous translations is
that there is no data value corresponding to
E1 and T available at compilation time.
• Both E1 and T corresponds to two sequences
of translated codes that will compute values
of expressions corresponding to E1 and T
when they are executed.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 11

Example: Code Generation

• The translation for to the rule E → E1 + T

generates code so that the computed values
of E1 and T are added to generate and store
the value of expression for E.
• The computed values of the expressions E1
and T are stored in compiler defined
temporary locations.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 12

Example: Code Generation

• Compiler creates temporary variablesa where

the intermediate values of sub-expressions
are stored. These variable names are also
entered in the symbol table.
• The main attribute of a non-terminal like E
or T is the index of the symbol table
corresponding to its temporary variable
name.
a They

✫ ✪
are also called virtual registers.

Lect 9 Goutam Biswas

 ✬ ✩
Compiler Design IIIT Kalyani, WB 13

Example: Code Generation

The code corresponding to E → E1 + T may

look like,
{
E.loc = newLoc();
codeGen(assignPlus, E.loc, E1.loc, T.loc);
}
where assignPlus means
E.loc = E1.loc + T.loc.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 14

Note

• This action has side-effects, it makes an

entry of the new location in the symbol
table. And the generated code is added in a
data structure.
• As an alternative E and T may store their
code sequences as their attributes.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 15

Associating Information

• Information is associated to syntactic

categories by attaching attributes to the
corresponding non-terminals.
• Computation of these attributes are
associated with the production rules.
• Initial attribute values are supplied by the
scanner.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 16

Definition

• A syntax-directed definition is a context-free

grammar where attributes are associated
with the grammar symbols. Rules for
computing the attributes are associated with
the production rules. There should not be
any circularity in the definition.
• These are called attribute grammars when
the definition does not have any side-effect.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 17

Definition

• A syntax-directed translation is an
executable specification of SDD. Fragments
of programs are associated to different points
in the production rules.
• The order of execution of the code is
important in this case.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 18

Example

A → {Action1 } B {Action2 } C {Action3 }

Action1 : takes place before parsing of the
input corresponding to the non-terminal B.
Action2 : takes place after consuming the input
for B, but before consuming the input for C.
Action3 : takes place at the time of reduction of
BC to A or after consuming the input
corresponding to BC.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 19

Note

• Embedded action may create some problem

in a parser generator like Bison.
• Bison replaces the embedded action in a
production rule by an ε-production and
associates the embedded action with the new
rule.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 20

Note

• But this may change the nature of the

grammar. As an example, the grammar
S → A | B, A → aba, B → abb is LALR.
• An embedded action is introduced as shown,
S → A | B, A → a {action} ba, B → abb.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 21

Note

• Bison modifies the grammar to

S → A|B, A → aM ba, B → abb,
M → ε {action} .
• The modified grammar is no longer LALR.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 22

Attribute Computation: a General Approach

• Construct the parse tree. Compute the

attributes of the non-terminals following the
data-flow in attribute dependence graph.
But construction of complete parse tree is
costly.
• There are restricted SDDs that do not
require explicit construction of parse tree.
They are S-attributed and L-attributed
definitions.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 23

A Simple Example

Consider the following grammar of signed

binary numerals. We wish to translate it to
decimal number.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 24

0 : S′ → N $
1: N → SL
2: S → +
3: S → −
4: L → LB
5: L → B
6: B → 0
7: B → 1
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 25

Note

• We first construct the LR(0) automaton of

the grammar and find that the grammar is
SLR.
• We associate attributes to the non-terminals.
• We also associate SDDs to the production
rules.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 26

LR(0) Automaton

q0 : S ′ → •N $ N → •SL S → •+
S → •−
q1 : S ′ → N • $
q2 : N → S • L L → •LB L → •B
B → •0 B → •1
q3 : S → +•
q4 : S → −•
q5 : N → SL• L → L • B B → •0
B → •1
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 27

LR(0) Automaton

q6 : L → B•
q7 : B → 0•
q8 : B → 1•
q9 : L → LB•

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 28

SLR Parsing Table

S Action Goto
+ − 0 1 $ N S L B
0 s3 s4 1 2
1 Acc
2 s7 s8 5 6
3 r6 r6
4 r7 r7
5 s7 s8 r1 9

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 29

SLR Parsing Table

S Action Goto
+ − 0 1 $ N S L B
6 r5 r5 r5
7 r6 r6 r6
8 r7 r7 r7

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 30

Attributes of Non-Terminals

Following are the attributes of different

non-terminals:
Non-terminal Attribute Type
N val int
S sign char
L val int
B val int
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 31

SDD

0 : S′ → N print N.val
1 : N → SL if (S.sign == ’-’) N.val= - L.val;
else N.val = L.val;
2: S → + S.sign = ’+’;
3: S → − S.sign = ’-’;
4 : L → L1 B L.val = 2*L1.val+B.val;
5: L → B L.val = B.val;
6: B → 0 B.val = 0;
7: B → 1 B.val = 1;

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 32

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Parsing $0 +101$ shift
Value $
Parsing $03 101$ reduce
Value $+
Parsing $02 101$ shift
Value $S S.sign=’+’
Parsing $028 01$ reduce
Value $S1
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 33

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Parsing $026 01$ reduce
Value $SB B.val = 1
Parsing $025 01$ shift
Value $SL L.val = B.val
Parsing $0257 1$ reduce
Value $SL0
Parsing $0259 1$ reduce
Value $SLB B.val = 0
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 34

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Parsing $025 1$ shift
Value $SL L.val = 2*L1.val + B.val
Parsing $0258 $ reduce
Value $SL1
Parsing $0259 $ reduce
Value $SLB B.val=1
Parsing $025 $ reduce
Value $SL L.val = 2*L1.val + B.val
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 35

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Parsing $01 $ Accept
Value $N N.val = +L.val

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 36

Decorated Parse Tree

N N.val=L1.val

S.sign = ’+’ S L1 L1.val=2*L1.val + B2.val

+ L2 B2 B2.val=1
L2.val=2*L3.val+B1.val

L3.val=B0.val L3 B1 1 B1.val=0

B0.val=1 B0 0

1
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 37

Synthesized Attribute

• In this example the value of an attribute of a

non-terminal is either coming from the
scannera or it is computed from the
attributes of its children.
• This type of attribute is known as a
synthesized attribute.
a Attribute of a terminal comes from the scanner.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 38

S-Attributed

• An attributed grammar is called

S-attributed if every attribute is synthesized.
• Attributes in such a grammar can be easily
computed during a bottom-up parsing.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 39

Another Set of Attributes

Non-terminal Attribute Type

N val int
S sign char
L val, pos int, int
B val, pos int, int

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 40

SDD

0 : S′ → N print N.val
1 : N → SL L.pos = 0
if (S.sign == ’-’) N.val= - L.val;
else N.val = L.val;
2: S → + S.sign = ’+’;
3: S → − S.sign = ’-’;
4 : L → L1 B L1 .pos = L.pos+1;
B.pos = L.pos;
L.val = L1 .val+B.val;

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 41

SDD

5 : L → B B.pos = L.pos;
L.val = B.val;
6: B → 0 B.val = 0;
7: B → 1 B.val = 2B.pos ;

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 42

Exercise

Draw the parse tree for −101 and show the flow
of information.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 43

Note

• Attributes of a non-terminal depends on the

nature of translation. But it may also
depend on the nature of the grammar.
• Following is a grammar of integers in 2’s
complement numerals. It is to be translated
to a signed decimal numeral.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 44

Exercise

1: N → L
2: L → LB
3: L → B
4: B → 0
5: B → 1
Associate appropriate attributes to the
non-terminals and give rules of semantic
actions. Write bison specification for the
grammar.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 45

Example

Consider a right-recursive grammar of signed

binary strings:

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 46

0 : S′ → N
1: N → SL
2: S → +
3: S → −
4: L → BL
5: L → B
6: B → 0
7: B → 1
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 47

Attributes of Non-Terminals

We need a new attribute of L to remember the bit

position:

Non-terminal Attribute Type

N val int
S sign char
L val int
pos int
B val int

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 48

Action for Rules

0 : S′ → N print N.val
1 : N → SL if (S.sign == ’-’) N.val=- L.val;
else N.val = L.val;
2: S → + S.sign = ’+’;
3: S → − S.sign = ’-’;
4 : L → BL1 if(B.val)
L.val=pow(2,L1.pos)+L1.val;
else L.val=L1.val;
L.pos=L1.pos+1;

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 49

Actions for Production Rules

5 : L → B L.val = B.val; L.pos = 1

6: B → 0 B.val = 0;
7: B → 1 B.val = 1;

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 50

Example

Consider the following grammar for variable

declaration:
1: D → T L;
2 : T → int
3 : T → double
4 : L → L , id
5 : L → id
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 51

Parse Tree

The parse tree for the string double id, id; is

as follows:

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 52

T L ;

double L , id

id
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 53

Note

When an id is reduced to the non-terminal L,

it is inserted in the symbol table along with its
type informationa . The type information is not
available from any subtree rooted at L. It has
to be inherited from T via the root D.
a The type information is important for space allocation, representation, op-
erations, correctness and other purposes.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 54

SDDefinition

1 : D → T L; L.type = T.type
2: T → int T.type = INT
3: T → double T.type = DOUBLE
4 : L → L1 , id L1.type = L.type
addSym(id.name, L.type)
5 : L → id addSym(id.name, L.type)

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 55

Inherited Attribute

Let B be a non-terminal at a parse tree node

N . Let M be the parent of N . An inherited
attribute B.i is defined by the semantic rule
associated with the production rule of M
(parent).
Inherited attribute at the node N is defined in
terms of M , N and N ’s siblings.
In the previous example the non-terminal L gets
the attribute from T as an inherited attribute.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 56

S-Attributed Definitions

An SDD is S-attributed if every attribute is

synthesized. The attribute grammar may be
called S-attributed grammar.
This definition can be implemented in a
LR-parser as the reduction traverse the
parse-tree in postorder.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 57

L-Attributed Definitions

An SDD is called L-attributed (‘L’ for left) if

each attribute is either
• synthesized, or
• inherited with the following restrictions: if
A → α1 α2 · · · αn be a production rule, and
αk has an inherited attribute ‘a’ computed in
this rule, then the computation may involve
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 58

L-Attributed Grammar

• inherited attribute of A (parent), or

• attributes (inherited or synthesized) of
α1 , α2 , · · · , αk−1 (symbols to the left of αk ),
• attributes of αk , provided no dependency
cyclea is formed.
aA → B { A.s = B.i; B.i = A.s + k }.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 59

Rules

The type definition mentioned earlier is L-attributed.

1 : D → T L; L.type = T.type
2: T → int T.type = INT
3: T → double T.type = DOUBLE
4 : L → L1 , id L1.type = L.type
addSym(id.name, L.type)
5 : L → id addSym(id.name, L.type)

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 60

Note

The question is how to propagate the type

information in a parser generated by bison?
The non-terminal T gets the value of
synthesized type attribute when a T -production
rule is reduced.
But that cannot be propagated as an attribute
of the non-terminal L as this non-terminal is
not present in the stack.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 61

Solution I

An ad hoc solution is to use a global variable to

hold the type value.

T → int type = INT

T → double type = DOUBLE
L → L1 , id addSym(id.name, type)
L → id addSym(id.name, type)

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 62

Solution II

We introduce a different attribute of L, a list of

symbol table entries corresponding to different
identifiers, and initialize their types at the end.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 63

1 : D → T L; initType(L.list, T.type)
2 : T → int T.type = INT
3 : T → double T.type = DOUBLE
4 : L → L1 , id L.list = L 1.list +
mklist(addSym(id.name))
5 : L → id L.list =
mklist(addSym(id.name))
Read ‘+’ as append in the list.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 64

Solution III

We can device another solution from the value

stack. For that we consider the states of LR(0)
automaton of the grammar.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 65

LR(0) Automaton

q0 : S → •D D → •T L; T → •int
T → •double
q1 : S → D•
q2 : D → T • L L → •L, id L → •id
q3 : T → int•
q4 : S → double•
q5 : D → T L•; L → L•, id
q6 : L → id•

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 66

LR(0) Automaton

q7 : L → L, •id
q8 : L → L, id•
q9 : D → T L; •

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 67

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Par $0 int id, id;$ shift
Val $
Par $03 id, id;$ reduce
Val $int
Par $02 id, id;$ shift
Val $T T.type=INT
Par $026 , id;$ reduce
Val $T id
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 68

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Par $025 , id;$ reduce
Val $T L addSym(id.name,L.type)
How does L gets the type information. Note that in
bison L ≡ $$ and id ≡ $1. But the type information is
available in T in the stack, below the handle.

Type Stack → Input→ Action/Value

Par $0257 id;$ shift
Val $T L ,
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 69

Example: Parsing & Value Stack

Type Stack → Input→ Action/Value

Par $02578 ;$ reduce
Val $T L , id
Par $025 ;$
Val $T L addSym(id.name,L.type)
Again the type information is available just below the
handle.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 70

Note

In Bison the attribute below the handle can be

accessed. In this case the non-terminal T
corresponds to $0 and its type attribute is
$0.type.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 71

Note

Often a natural grammar is transformed to

facilitate some type of parsing, and the parse
tree does not match with the abstract syntax
tree of the language.
As an example the left recursion is removed for
LL(1) parsing. How does the original
S-attributed grammar gets modified after the
removal of left-recursion? We consider the
following example.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 72

S-Attributed Expression Grammar

S → E$ { 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 → (F ) { F.val = E.val}
F → ic { F.val = ic.val}

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 73

Decorated Parse Tree of 2 + 3 + 4

E0 .s = E1 .s + T1 .s E0
E1 .s = E2 .s + T2 .s
E1 T1 T1 .s = 4
+
T2 .s = 3
T2 F1 F1 .s = 4
E2 .s = 2 E2 +
F2 .s = 3
F2
T3 .s = 2 T3 ic ic.val=4

F3 .s = 2 F3 ic.val=3 ic
4

ic.val=2 ic 3

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 74

Equivalent LL(1) Grammar

S → E$
E → T E′
E ′ → +T E ′
E′ → ε
T → FT′
T ′ → ∗F T ′
T′ → ε
F → (E)
F → ic
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 75

Parse Tree of LL(1) Grammar

E0

T3 E1′

T3′ + E2′
F3 T2
ε + E3′
T1
ic F2 T2′
ε
F1 T1′
ic ε
2
ic ε
3

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 76

Partially Decorated Parse Tree of LL(1) Grammar

E0

T3 E1′

T3′ + E2′
F3 .s = 2 F3 T2
ε + E3′
T1
F2 T2′
ic.val=2 ic
F2 .s = 3 ε
F1 T1′
ic.val=3 ic ε
2 F1 .s = 4
ic.val=4 ic ε
3

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 77

Note

• Two arguments of ‘+’ are in different

subtrees. It is necessary to pass the value of
T3 .s to the subtree of E1′ .
• It is also necessary for left-associativity of
‘+’, to propagate the computed value down
the tree say from E1′ to E2′ .
• We achieve this by inherited attributes E ′ .i
and T ′ .i of the non-terminals E ′ and T ′ .
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 78

Note

But it is also necessary to propagate the

computed value towards the root. This is done
through the synthesized attributes of E ′ and T ′
i.e. E ′ .s, T ′ .s.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 79

L-Attributed LL(1) Expression Grammar

E → T { E’.ival = T.sval } E ′
{ E.sval = E’.sval }
E ′ → +T { E1’.ival = E’.ival + T.sval } E1′
{ E’.sval = E1’.sval }
E ′ → ε { E’.sval = E’.ival }

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 80

L-Attributed LL(1) Expression Grammar

T → F { T’.ival = F.sval } T ′
{ T.sval = T’.sval }
T ′ → ∗F { T1’.ival = T’.ival * F.sval } T1′
{ T’.sval = T1’.sval }
T ′ → ε { T’.sval = T’.ival }

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 81

L-Attributed LL(1) Expression Grammar

F → (E) { F.sval = E.sval }

F → ic { F.sval = ic.val }

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 82

Decorated Parse Tree of LL(1) Grammar

E0 E0′ .s = E1′ .s = 9
E1′ .i = T3 .s = 2
T3 .s = T3′ .s = 2 T3 E1′ E1′ .s = E2′ .s = 9
T3′ .i = F3 .s = 2 E2′ .i = E1′ .i + T2 .s = 2 + 3 = 5
T3′ + E2′ E2′ .s = E3′ .s = 9
F3 .s = 2 F3 T2
T3′ .s = T3′ .i = 2 E3′′.i = E2′ .i + T1 .s = 5 + 4 = 9
ε + E3
′ T1
F2 T2 E3′ .s = E3′ .i = 9
ic.val=2 ic
F2 .s = 3 ε
F1 T1 ′
ic.val=3 ic ε
2 F1 .s = 4
ic.val=4 ic ε
3

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 83

LL(1) Parsing Table

Non Terminal
Term. + ∗ ( ) ic $
E E → T E′ E → T E′
T T → FT′ T → FT′
F F → (E) F → ic
E′ E ′ → +T E ′ E′ → ε E′ → ε
T′ T′ → ε T ′ → ∗F T ′ T′ → ε T′ → ε

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 84

Example

Consider the leftmost derivation and the parse

tree decorated with attributes. corresponding
to the input 2 + 3 * 4.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 85

Left-most Derivation

1 E 10 → ic + ic ∗ ic T ′ E ′
2 → T E′ 11 → ic + ic ∗ ic ε E ′
3 → F T ′E ′ 12 → ic + ic ∗ ic
4 → ic T ′ E ′
5 → ic ε E ′
6 → ic + T E ′
7 → ic + F T ′ E ′
8 → ic + ic T ′ E ′
9 → ic + ic ∗ F T ′ E ′

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 86

Start
Parsing Stack Input Parsing Stack Input
$E ic + ic * ic $ $ E’ T’ F ic * ic $

$ E’ T ic + ic * ic $ $ E’ T’ ic * ic $

$ E’ T’ F ic + ic * ic $ $ E’ T’ * ic $

$ E’ T’ ic ic + ic * ic $ $ E’ T’ F * ic $

$ E’ T’ + ic * ic $ $ E’ T’ F ic $

$ E’ + ic * ic $ $ E’ T’ ic ic $

$ E’ T + + ic * ic $ $ E’ T’ $

$ E’ T ic * ic $ $ E’ $

End $ $

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 87

Implementation of L-Attributed Translation

The important question is how to implement

L-attributed translation with the top-down
parsing. Following is a general scheme.
• A simple parser stack holds records
corresponding to terminals and
non-terminals.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 88

Implementation of L-Attributed Translation

• But to implement L-attributed translations,

it should also hold records containing pointer
to action (code), synthesize attributes and
inherited attributes.
• For a non-terminal A, the inherited
attributes are kept in the record
corresponding to A itself.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 89

Implementation of L-Attributed Translation

• The pointer to the code to evaluate the

inherited attributes of A are naturally kept
above the record of A.
• Synthesized attributes of A are kept below
the record of A and its inherited attribute.
This record may also contain pointer to
some code to copy the synthesized attributes
in records down the stack (below a fixed
depth).
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 90

Another Example

L-attributed grammars come naturally with

flow-control statements. Following is an
example with if-then-else statement.

IS → if BE then S1 else S2 .

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 91

Attributes of Statement

• Every statement has a natural synthesized

attribute, S.code, holding the code
corresponding to S.
• Also a statement S has a continuation, the
next instruction to be executed after
execution of S. This may be handled as a
jump target (label). But this label is an
inherited attribute of S, S.next, propagated
in the subtree of S.
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 92

Attributes of Boolean Expression

• The boolean expression also has a

synthesized attribute BE.code.
• But it has two inherited attributes, BE.true,
a jump target (label) where the control is
transferred if the boolean expression is
evaluated to true. This is the beginning of
S1 .
Similarly there is BE.false, a label at the
beginning of S2 .
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 93

SDD for if-then-else

IS → if BE l1=newLabel(), l2=newLabel()
then S1 BE.true = l1, BE.false=l2
else S2 . S1 .next = S2 .next = IS.next
IS.code = BE.code + l1’:’ +
S1 .code + l2’:’ + S2 .code

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 94

L-Attributed SDT for if-then-else

IS → if {l1=newLabel(),l2=newLabel()
BE.true = l1, BE.false=l2}
BE {S1 .next = IS.next }
then S1 {S2 .next = IS.next }
else S2 .
{IS.code = BE.code + l1’:’ +
S1 .code + l2’:’ + S2 .code}
✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 95

Note

Afterward we shall see how this is managed in

an actual implementation using back-patching.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 96

SDD for Boolean Expression and

BE → BE1 and BE2 BE1 .true=l=newLabel()

BE1 .false = BE.false
BE2 .true = BE.true
BE2 .false = BE.false
BE.code = BE1 .code +
l’:’ + BE2 .code

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 97

L-Attributed SDT for Boolean Expression and

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 98

BE → { BE1 .true=l=newLabel()
BE1 .false = BE.false }
BE1 and
{ BE2 .true = BE.true
BE2 .false = BE.false }
BE2
{ BE.code = BE1 .code +
l’:’ + BE2 .code }

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 99

Note

Not all definitions can be implemented during

parsing. Consider the following definition to
convert infix-expression to prefix expression.

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 100

Rules

1 : E → { putchar(’+’); } E1 + T
2: E → T
3: T → { putchar(’*’); } T1 ∗ F
4: T → F
5 : F → (E)
6 : F → ic {printf(" \%d ", ic.val);}

✫ ✪
Lect 9 Goutam Biswas
 ✬ ✩
Compiler Design IIIT Kalyani, WB 101

Note

It is not possible to activate any one of the putchar()

operations while parsing without seeing ‘+’ or ‘*’. But if
the whole parse tree is availablea New leaf nodes
corresponding to actions can be added to internal nodes.
Finally a preorder traversal in the modified tree will do
the job.
a The whole parse tree is available only after the parsing is complete.

✫ ✪
Lect 9 Goutam Biswas