POST MID-TERM COURSE

Runtime Memory Models; T2 Chapter 6

Activations Records; Activation Chap 7
Stacks
Intermediate Representation; Basic T2 Sections 7.1 to 7.2
Blocks and Conditional Branches; T2 Section 8.2 Chap 07
Instruction Selection; Live-ness T2 Section 9.1 10.1chap 9.4
Analysis
Register Allocation T2 Sections 11.1- 11.3chap 9
Program Structuring; Data T1 Sections 6.1 to 6.5
Abstraction & Information Hiding;
Modules
Objects and Object Orientation; T1 Sections 7.1 to 7.2 ,7.5,
Class-based and Object-based 7.7
Languages 1
 –4–
Semantic Analysis
( Abstract Syntax Trees)
 Objectives
 To Understand
1. The concept of Static Semantic Analysis
2. Syntax Directed Definitions & Construction of Syntax
Trees
3. Bottom up Evaluation of S-attributed Definitions
4. L-attributed Definitions
5. Top Down Translation
6. Bottom up Evaluation of Inherited Attributes
3
 Where are we now ?

Source
characters

Scanner 
tokens

Parse Semantic Abstract

Parser
Tree Actions Syntax Tree
( IR )

4
 Semantic Actions – Why?
 While Parsing checked the syntactical correctness of
the program;
 There is a level of correctness that is not captured by a
grammar
1. Has a variable been declared?
2. Are types consistent in an expression?
3. In the assignment x=y, is y assignable to x?
4. Does a method call have the right number and types of
parameters?
5. In a selector p.q, is q a method or field of class p?
6. Is variable x guaranteed to be initialized before it is used?
etc. etc. etc.
5
 Semantic Actions – What?
 While Parsing checked the syntactical correctness of
the program;
 Semantic Actions include:
1. Symbol table handling
 Maintaining information about declared names
 Maintaining information about types
 Maintaining scopes
2. Checking context conditions
 Scoping rules
 Type checking
3. Invocation of code generation routines
6
 Semantic Actions – when ?
 Key Idea: At significant points during parsing perform
some semantic action
– Typically when a production is reduced (LR) or
– at a convenient point in the parse (LL)
 Semantic actions that can be performed during Parsing
– Build (and return) a representation of the parsed chunk of
the input (compiler)
– Perform some sort of computation and return result
(interpreter)
 Also Known as
Static Semantic Analysis
7
 Static Semantic Analysis – How ?
 Done by a technique called Syntax Directed Definition
– A generalization (or Extension ) of a context free grammar in
which each grammar symbol has an associated set of
attributes
1. Associate information with a programming language
construct by attaching attributes to the grammar symbols
representing the constructs.
2. Values for attributes are computed by “ semantic rules”
associated with the grammar production.
– A node in grammar is a record with fields for holding
information,
8
 1. Attributes in Syntax Directed Definition
 Each nonterminal ( an intermediate node in the parse
tree) has associated properties or attributes
 Example attributes could be:
– Name – Type,
– Memory Location – Font-size, etc
 For each separate instance of the grammar symbol,
there will be separate instance of the attribute.
 A node in the parse tree for the grammar symbol will
be a record holding these attributes as fields
 Value of the attribute is defined by Semantic Rule
associated with the production used at that node
9
 E2 .val
1.1 Types of Attributes
+
1. Synthesized Attributes E1 .val num .val

– An attribute of a grammar symbol is synthesized if it is

computed from the attributes of its children in the parse tree
corresponding to the rightmost derivation
– Example: E --> E + num | num
– E2.val = E1.val + num.val ( val of E2 computed based on
the VAL of E1 and num)
– Used Extensively in LR parsing practice
– A syntax directed Definition that uses Synthesized Attributes
is known as “S – attributed Definition” (S – attributed
Definitions are based on LR Grammar)
10
 D.type
1.2 Types of Attributes
2. Inherited Attributes T.type L.type

– An attribute of a grammar symbol is inherited, if it is

computed from the attributes of its parents and siblings
– D → T {$2.type:=$1.type} L L.type
– L → id , {$3.type:=$1.type} L
– Typical for LL parsing (top down). id , L.type
– Convenient for expressing the dependence of a
programming language construct on the context in which it
appears
– More natural to use with Syntax Directed Definition
(Although it is possible to write a syntax directed Definition
using only synthesized attributes)
11
 2. Semantic Rules in Syntax Directed Defn
 Define the value of an attribute associated with a
grammar symbol
 Associated with the grammar rule used at that node
Production Semantic Rule  Notes:
L→En Print (E: Val)  Associates an integer
valued synthesized
E → E1 + T E.Val = E1.val + T.val
attribute called val with
E→T E.val = T.val each nonterminal E,T, & F
T → T1 *F T.Val = T1.val x F.val  The token digit has a
synthesized attribute lexval
T→F T.val = F.val
whose value will be
F→(E) F.val = E.val supplied by the Lexical
F → digit F.Val = digit.lexval Analyzer 12
 2. Semantic Rules in Syntax Directedn Defn
 Define the value of an attribute associated with i s a
a s
l l ,
y te
grammar symbol n ta b u
id e tt r i
 Associated with the grammar rule rused i nc at that A node
o , z ed
l t
a Notes s i
Production Semantic Rule alc nth : u e
k c Sy
L→En Print (E: Val) d es e s Associates an integer
l e t u s y valued synthesized
E → E1 + T E.Val = sEim1.val +ceT.val ive p i l
a s in l u s attribute called val with
o f n x c
E→T
i o n E.val i t i o= T.val e each nonterminal E,T, & F
i nit f in
e = T1.val x F.val  The token digit has a
T → T1d*F ef T.Val d d
i s
h F ribu te synthesized attribute lexval
TT→ t t T.val = F.val
- a whose value will be
F →S( E ) F.val = E.val supplied by the Lexical
F → digit F.Val = digit.lexval Analyzer 13
 S-attributed definition Example
The Parse Tree for 3* 5+ 4 Using Production rules
below is: L

E
Production
L→En E T
+
E → E1 + T
T F
E→T
T → T1 *F T Digit
* F
T→F
F Digit
F→(E)
F → digit Digit
14
 S-attributed definition Example (Contd.)
 The annotated parse tree with attribute grammer and
synthesized attributes is: L
Semantic Rule
E.ValE= 19
Print (E: Val)
E.Val = E1.val + E.ValE= 15 + T.ValT = 4
T.val
E.val = T.val F.ValF= 4
T.ValT = 15
T.Val = T1.val x F.val digit.lexVal
Digit = 4
T.val = F.val T.ValT = 3 * F.ValF= 5
F.val = E.val F.ValF = 3 digit.lexVal
Digit = 5
F.Val = digit.lexval
digit.lexVal
Digit = 3
15
 Attribute grammar Example
 Consider the following CFG for signed binary numbers:
– (1) Number →Sign List , (2) Sign → + | –
– (3) List → List Bit | Bit , (4) Bit → 0 | 1
 Parse tree for string “ -1” is:  Parse tree for string “ -101” is:
1. Number → Sign List 1. Number → Sign List
2. → Sign Bit 2. → Sign List Bit
3. → Sign 1 3. → Sign List 1
4. →–1 4. → Sign List Bit 1
5. → Sign List 0 1
6. → Sign Bit 0 1
7. → Sign 1 0 1
8. → – 101 16
 Attribute Grammar Example (Contd.)
 Attribute Grammar for the CFG of signed binary numbers
is :

17
Attribute Grammar Example (Contd.)

18
Attribute Grammar Example (Contd.)
Val = – 5
Pos = 0
Neg = True Val = 5
Pos = 0
Val = 1
Pos = 1
Val = 4

Pos = 2
Val =4
Pos = 1
Val = 0
Pos = 2
Val = 4
 Attribute Grammar Example ( Contd.)
Val = – 5  The example on the
Pos = 0 side Shows the
Neg = True Val = 5 decorated parse tree
Pos = 0 with attribute
Val = 1 dependencies shown
Pos = 1
Val = 4 with arrows.
 If the parse tree is
Pos = 2
Val =4 taken out,
Pos = 1  What is left is a
Val = 0
Pos = 2
Val = 4 DEPENDENCY GRAPH
 Dependency Graph
 A directed graph that depicts the interdependencies
among the inherited and synthesized attributes at the
nodes in a parse tree
 Example:
– Consider the grammar production E → E1 + E2 and the
Corresponding semantic rule E.val : = E1.val+ E2.val
– The parse tree would be: Val
The Dependency Graph would ●
– E
be shown separately as

E1 ● + E2 ●
Val Val
21
 Dependency Graph
 A directed graph that depicts the interdependencies
among the inherited and synthesized attributes at the
nodes in a parse tree
 The order in which the semantic rules are evaluated is
decided by the earlier node to the later node.
 The dependency graph is constructed topologically;
– Grammar is used to construct the parse tree from the input
– We then obtain an order of evaluation of semantic rules.
– Translation of the semantic rules in this order yields the
translation of the input string.

22
 Algorithm For constructing Dependency
graph
for each node 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 ci to the node for b;
23
 Abstract Syntax Tree (AST)
 A condensed form of a parse tree useful in representing
language constructs of a programming language
 An intermediate representation that allows translation to
be decoupled from parsing
 For Example: The production: S → if B then S1 else S2
will have a syntax tree as:
 Similarly, 3 * 5 + 4 +
If-then-else will result in
* 4
B S1 S2
3 5
24
 AST versus Parse Tree
 While a parse tree keeps track of all productions used to
build the parse tree, an AST is a condensed form of this
with just the information needed in later stages of
compilation or interpretation.

25
 AST Construction for Expressions
 Similar to the translation of expression into postfix form
 Sub-trees are constructed for the sub-expressions by
creating a node for each operator & operand
 The children of the Operator node are the nodes
representing the sub-expressions constituting the
operands of the operator
 In a node for operator, ( often called the Label of the
node) One field identifies the operator & the rest
contain pointer to the nodes of operands
 Each node in the syntax tree can be represented as a
record with several fields
26
 Constructing AST (Contd.)
 Following functions are used to create the nodes of AST.
( Each function returns pointer to the newly created
node)
1. mknode (op, left,
 Creates right) node with label op and two fields
an operator
containing pointers left and right.

 Creates
2. mkleaf an identifier node with label id and a field
(id, entry)
containing entry , a pointer to the symbol table entry.

 Creates
3. mkleaf (num, entry)
a number node with label num and a field
containing val, the value of the number
27
 Constructing AST – An Example
+ | |  Sentence a – 4 + c

- | | id |

num| 4 to entry for c

id |
p1 := mkleaf (id, entry a)
to entry for a
p2 := mkleaf (num, 4)
 The tree is built bottom-up using
p3 := mknode (‘-’, p1, p2)
the function call sequence →
p4:= mkleaf (id, entry c)
p5 := mknode (‘+’, p3, p4 )
28
 A SDD for Constructing AST
PRODUCTION SEMANTIC RULE
E → E1 + T E.nptr := mknode ( ‘+’ E1.nptr, T.nptr )
E → E1 – T E.nptr := mknode ( ‘–’ E1.nptr, T.nptr )
E→T E.nptr := T.nptr )
T→(E) T.nptr := E.nptr )
T → id T.nptr := mkleaf ( id, id, entry )
T → num T.nptr := mkleaf ( num, num, val)
 Uses underlying productions of the grammar to
NOTE: schedule calls to the functions mknode and mkleaf
 The synthesized attribute nptr for E and T keeps
track of the pointers returned by function calls 29
 A SDD for Constructing AST
E. Nptr - + | | T. nptr
E. Nptr +
id .nptr
- | | T. nptr id |
num .nptr
to entry for c
E. nptr num| 4
T. nptr PRODUCTION SEMANTIC RULE
id .nptr E → E1 + T E.nptr := mknode ( ‘+’ E1.nptr, T.nptr )
E → E1 – T E.nptr := mknode ( ‘–’ E1.nptr, T.nptr )

id | E→T E.nptr := T.nptr )

T→(E) T.nptr := E.nptr )
to entry for a T → id T.nptr := mkleaf ( id, id, entry )
T → num T.nptr := mkleaf ( num, num, val)
30
 Directed A-cyclic graph (DAG)
 Identifies common sub-expressions
 Like syntax tree,
– it has an interior node representing an operator and two
children as operands; left & right.
– The only difference is that the node in a DAG
representing a common sub-expression has more than
one parent in the syntax tree.
 The common sub-expression would be represented
as a duplicated sub-tree
 Can also be used to represent a set of expressions
31
 DAG Usage – An Example
 Consider the expression : a:= b*-c + b*-c  The corresponding
 The corresponding Syntax Tree would be: DAG would be:
assign assign
a + a +
* *
b uminus *
b uminus b uminus
t1 := - c;
c c t2 := b * t1; c
t3 := -c; t1 := - c;
t4 := b* t3; t2 := b * t1;
t5 := t2 + t4; t3 := t2 + t2;
a := t5;
a := t3; 32
 Translators for SDD
 A translator for an arbitrary SDD can be difficult to
build
 However:
1. Large classes of syntax directed Definitions exist for
which it s easier to build a translator
2. SDD’s with synthesized attributes ( A.k.a. S–attributed
definitions) can be evaluated using Bottom-up
EvaluationTechnique
3. SDD’s with Inherited attributes ( A.k.a. L–Attributed
definitions ) are evaluated using top – down method
known as “depth–first order”
33
 Bottom-Up Evaluation of SDD’s
 A translator for an S-attributed definition can often be
implemented with the help of an LR-Parser generator.

 From the S-attributed definition, the parser generator can

construct a translator that can evaluate attributes as it
parses the input.

 One can have extra fields in the parser stack to hold the
values of the synthesized attributes value.

 One can straight away build code segments.

34
Thank you
35
 Syntax Directed Definition Summary
1. SDD is a generalization of the Context Free Grammar.
2. Each symbol can have 2 kinds of attributes
i. synthetic & inherited
3. The value of an attribute is defined by the semantic rule
associated with the production
4. Synthetics computed from the children at the node and
inherited from the siblings and parents of the node.
5. Semantic rules set up the dependency of the attributes
that will be represented as a graph known as
Dependency Graph
………. Contd.
36
 Syntax Directed Definition Summary
6. The Dependency Graph deciding the order of
evaluation of the semantic rules..
7. The evaluation defines the values of the attribute at
the nodes in the parse tree
8. A parse tree showing the attributes at each node is
called an Annotated Parse Tree and the process of
evaluation is called decorating the tree.
9. An SDD with only synthesized attributes exclusively is
called S-attributed definition and can always be
implemented bottom up
37
 Syntax Directed Definition – Another
example
 In this example, an inherited attribute distributes type
information to the various identifiers in the declaration:
Production Semantic Rule  Notes
 The nonterminal T has a
D→TL L.in:= T.type synthesized attribute type
T → int T.Type := integer whose value is determined
by the type declaration
T → real T.Type := real  Associated with the
productions for L call
L → L1, id L1.in := L.in procedure addtype to add
addtype (id.entry, L.in) the type of each identifier to
its entry in the symbol table
L → id addtype (id.entry, L.in)
38
 Syntax Directed Definition – Another example
 The corresponding Decorated Parser tree for the sentence
 real id1, id2, id3

D
Production Semantic Rule
T.type = real L.in = real
D→TL L.in:= T.type

T → int T.Type := integer realL.in = real Id3

,
T → real T.Type := real
L.in = real , Id2
L → L1, id L1.in := L.in
Addtype (id.entry, L.in)
L → id Addtype (id.entry, L.in) Id1
39
 Dependency Graph Example
Dependency Graph for the construct: real id1,id2,id3
Semantic Rule D
L.in:= T.type
T.Type := integer
T.Type := real
4 type in 5
L1.in := L.in
T.type = real L.in = real In 6
addtype (id.entry, L.in) in 7 3 entry
addtype (id.entry, L.in) real L.in = real , id3
in 8
in 9
L.in = real , id2 2 entry
In 10
1,2,3 entry nodes
id1 1 entry 4,5,6,7,9 are internal
8,10 are link nodes40
 Desk Calculator SDD with LR parser
Input Stack Val Production Rule
a * b+ cn - -
* b+ cn a a F  digit Input
* b+ cn F a a*b+c
* b+ cn T a TF
b+ cn T* a L→En
+ cn T*b a,b
+ cn T*F a,b F  digit E → E1 + T
+ cn T ab TT*F E→T
+ cn E ab ET
cn E+ ab , T → T1 *F
n E+c ab , c T→F
n E+F ab , c F  digit
F→(E)
n E+T ab , c TF
n E ab+c EE+T F → digit
En ab+c 41
 L – Attributed Definitions
 A syntax directed definition where each inherited
attribute of Xi for 1 <= i <= n, on the right side of AX1,
X2, Xn, depends only on
– The attribute symbols X1, X2, Xi-1 to the left of Xi in the
production &
– The inherited attributes of A
 Note : Every S-attribute definition is L-attributed since
the restrictions 1 and 2 above applies only to inherited
attributes.
 The order of evaluation of the attributes is the order in
which the nodes of the parse tree are “created” by the
parsing method ( Depth-first order )
42
 DEPTH – FIRST ORDER
 Depth first evaluation order for attributes
 procedure dfvisit (n : node );
 begin
– for each child m of n, from left to right
– do begin
 evaluate inherited attributes of m;
 dfvisit ( m );
– end;
– evaluate synthesized attributes of n;
 end
43
 Parse Tree for 9 – 5 + 2

GRAMMAR
ETR
R addtop T {print ( addtop.lexeme) } | R | 
T num { print ( num,val ) }
E

T R

9 print(‘9’) - T print(‘-’) R

5 print(‘5’) + T print((‘2’) R

2 print(‘2’)
44
 Example 9 - 5 + 2

 Production  Semantic rule

E  E1 + T E. t  E1 .t || T.t ||’+’
E  E1 - T E. t  E1 .t || T.t ||’-’
ET E. t  T.t
T 0 |1 |…..|9 T  ‘0’ |’1’ |…..|’9’
E.t =95-2+
E.t = 95-
E.t= 9 T.t = 2
T.t =5
T.t= 9
9 - 5 + 2
45
 Problem
Consider the problem of translating decimal numbers
between 0 to 99 into their English words / phrases.
Number word / phrase
0 zero
1 One
10 Ten
11….. Eleven
19 Nineteen
20 Twenty
30 Thirty
31 Thirty one
46
 Grammar
1. N := D | D P
2. P := D
D := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
3.
PARSE TREE ANNOTATED
PARSE TREE
N
N .trans
D P .trans
D.val .in P
D
D 1.val
6
6
8
8
47
 Grammar
1. N := D | D P
2. P := D
3. D := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Production Semantic rule
N := D N.trans := spell (D.val)
N := D P P.in := D.val
N.trans := P.trans
P := D P.trans := if D1.val = 0 then decade (P.in)
else if P.in <= 1 then spell (10*p.in + D1.val)
else decade (P.in) || spell (D1.val)
D := 0 D.val := 0 spell ( 1 ) = One
….
----- decade (1) = Ten
……..
decade ( 9 ) = ninety48
48