The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions


You are here:Open notes-->VTU-->COMPAILER-DESIGN-10CS63-VTU-NOTES-UNIT-5

COMPAILER DESIGN 10CS63 VTU NOTES UNIT-5

SYLLABUS:
 Syntax-directed definitions;
 Evaluation orders for SDDs;
 Applications of syntax-directed translation;
 Syntax-directed translation schemes
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 64
Overview
input parse tree dependency graph attribute evaluation order
* 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:
o may generate intermediate codes
o may put information into the symbol table
o may perform type checking
o may issue error messages
o may perform some other activities
o in fact, they may perform almost any activities.
* An attribute may hold almost anything.
o a string, a number, a memory location, a complex record.
Attributes for expressions:
type of value: int, float, double, char, string,
type of construct: variable, constant, operations,
Attributes for constants: values
Attributes for variables: name, scope
o Attributes for operations: arity, operands, operator,
* When we associate semantic rules with productions, we use two notations:
o Syntax-Directed Definitions
o Translation Schemes
* Syntax-Directed Definitions:
o give high-level specifications for translations
o Hide many implementation details such as order of evaluation of semantic
actions.
o We associate a production rule with a set of semantic actions, and we do
not say when they will be evaluated.
* Translation Schemes:
o Indicate the order of evaluation of semantic actions associated with a
production rule.
o In other words, translation schemes give a little bit information about
implementation details.
Syntax directed definition (SDD) :
* To translate a programming language construct compiler has to keep track of
many quantities such as the type of the construct, location of the first instruction
in target code or the number of instructions generated.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 65
* A formalist called as syntax directed definition is used fort specifying translations
for programming language constructs.
* A syntax directed definition is a generalization of a context free grammar in
which each grammar symbol has associated set of attributes and each and each
productions is associated with a set of semantic rules
Definition of (syntax Directed definition ) SDD :
SDD is a generalization of CFG in which each grammar productions X???? is
associated with it a set of semantic rules of the form
a: = f(b1,b2..bk)
Where a is an attributes obtained from the function f.
* 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.
* 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.
The two attributes for non terminal are :
1) synthesized attribute (S-attribute) : (??)
An attribute is said to be synthesized attribute if its value at a parse tree node is
determined from attribute values at the children of the node
2) Inherited attribute : (??,??)
An inherited attribute is one whose value at parse tree node is determined in
terms of attributes at the parent and | or siblings of that node.
* The attribute can be string, a number, a type, a, memory location or
anything else.
* The parse tree showing the value of attributes at each node is called an
annotated parse tree.
The process of computing the attribute values at the node is called annotating
or decorating the parse tree.
Terminals can have synthesized attributes, but not inherited attributes.
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.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 66
* Of course, the order of these computations depends on the dependency graph
induced by the semantic rules.
Ex1:
1) Synthesized Attributes :
Ex: Consider the CFG :
S EN
E E+T
EE-T
E T
T T*F
TT/F
TF
F??(E)
Fdigit
N??;
Solution :
The syntax directed definition can be written for the above grammar by using
semantic actions for each production.
Production rule Semantic actions
S EN S.val=E.val
E E1+T E.val =E1.val + T.val
EE1-T E.val = E1.val * T.val
ET E.val =T.val
TT*F T.val = T.val * F.val
TT|F T.val =T.val | F.val
F??(E) F.val =E.val
T F T.val =F.val
Fdigit F.val =digit.lexval
N??; can be ignored by lexical Analyzer as; is
terminating
Symbol.
For the Non-terminals E,T and F the values can be obtained using the attribute Val.
The taken digit has synthesized attribute lexval.
In SEN, symbol S is the start symbol. This rule is to print the final answer of
expressed.
Following steps are followed to Compute S attributed definition.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 67
1. Write the SDD using the appropriate semantic actions for corresponding
production rule of the given Grammar.
2. The annotated parse tree is generated and attribute values are computed. The
Computation is done in bottom up manner.
3. The value obtained at the node is supposed to be final output.
PROBLEM 1:
Consider the string 5*6+7; Construct Syntax tree, parse tree and annotated tree.
Solution :
The corresponding annoted parse tree is shown below for the string 5*6+7;
Syntax tree:
Parse tree:
The corresponding annoted parse tree is shown below for the string 5*6+7;
+
S
E N
F
E + T
T
T * F
F
digit
digit
digit 6
7
5
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 68
Advantages: SDDs are more readable and hence useful for specifications
Disadvantages: not very efficient.
Ex2:
PROBLEM : Consider the grammar that is used for Simple desk calculator. Obtain
the Semantic action and also the annotated parse tree for the string
3*5+4n.
LEn
EE1+T
ET
TT1*F
TF
F??(E)
Fdigit
Solution :
Production rule Semantic actions
LEn L.val=E.val
EE1+T E.val=E1.val + T.val
ET E.val=T.val
TT1*F T.val=T1.val*F.val
TF T.val=F.val
F??(E) F.val=E.val
Fdigit F.val=digit.lexval
The corresponding annotated parse tree U shown below, for the string 3*5+4n.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 69
Fig:Annotated parse tree
Exercise :
For the SDD of the problem 1 give annotated parse tree for the Following expressions
a) (3+4)*(5+6)n
b) 1*2*3*(4+5)n
c) (9+8*(7+6)+5)*4n
Solution: a)
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 70
b)
c)
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 71
Dependency Graphs
Note: should be in Figure 5.6
Dependency graph and topological sort:
1. For each parse-tree node, say a node labeled by grammar symbol X, the
dependency graph has a node for each attribute associated with X.
2. If a semantic rule associated with a production p defines the value of
synthesized attribute A.b in terms of the value of X.c. Then the
dependency graph has an edge from X.c to A.b .
3. If a semantic rule associated with a production p defines the value of
inherited attribute B.c in terms of the value X.a. Then , the dependency
graph has an edge from X.a to B.c.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 72
Evaluation Orders for SDDs
* Dependency graphs * are a useful tool for determining an evaluation order for the
attribute instances in a given parse tree.
* A dependency graph depicts the flow of information among the attribute instances
in a particular parse tree.
* An edge from one attribute instance to another means that the value of the
first is needed to compute the second. Edges express constraints implied
by the semantic rules.
Edges express constraints implied by the semantic rules
2) Inherited attributes :
Consider an example and compute the inherited attributes, annotate the parse
tree for the computation of inherited attributes for the given string int a, b, c
Ex:
STL
Tint
Tfloat
Tchar
Tdouble
LL,id
L id
The steps are to be followed are:
1) Construct the syntax directed definition using semantic action.
2) Annotate the parser tree with inherited attributes by processing in top down
fashion.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 73
The SDD is given below:
Production rule Semantic actions
S  TL L.inh =T.type
Tint T.type = int
Tfloat T.type =float
Tchar T.type =char
Tdouble T.type=double
LL,id T.type = L, inh
Add*type (id.entry,L.inh)
Lid Add * type (id.entry,L.inh)
string int a, b,c
Fig: Annotated parse tree.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 74
String float id1, id2, id3
Ex2: PROBLEMS: consider the following context free grammar for evaluating
arithmetic expressions with operator *
T* FT
T * *FT
T ???
F *digit
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 75
Dependency graph above example:
T 9 val
F 3 val inh 5 T 8 syn
Digit 1 lexval * F 4 val inh
6 T 7 syn
digit 2 lexval 
A topological sort of the above graph gives the order of evaluation of the SDD. One of
the topological sort order is (1,2,3,4,5,6,7,8 and 9) another topological sort order is
(1,2,5,2,4,6,7,8,9)
Advantages: dependency graph helps in computing the order of evaluation of the
attributes
Disadvantage: it cannot give the order of evaluation of attributes if there is a cycle
formation in the graph. However, this disadvantage can be overcome by using S *
attributed and L * attributed definitions.
Problems on SDD, Annotated parse tree, Dependency graph, evaluation of order:
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 76
1. E *TE
E * +TE
E *
T *FT
T * *FT
T *
F ?(E)
F * id
String (i) id +id*id (ii) (id
+ id* id)
2. T * BC
B * int
B * float
C * [num]C
C *
String (i) int[2][3] (note: int
[2][3] should be passed as array(2,
array(3, integer)))
(ii) float [3] (iii) float
[3][3][2]
S-Attributed Definitions
* Syntax-directed definitions are used to specify syntax-directed translations.
* To create a translator for an arbitrary syntax-directed definition can be difficult.
* 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 syntaxdirected
definitions.
* L-Attributed Definitions: in addition to synthesized attributes, we may
also use inherited attributes in a restricted fashion.
* To implement S-Attributed Definitions and L-Attributed Definitions are easy (we
can evaluate semantic rules in a single pass during the parsing).
* Implementations of S-attributed Definitions are a little bit easier than
implementations of L-Attributed Definitions
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
* A syntax-directed definition is L-attributed if each inherited attribute of Xj,
where 1jn, 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
* Every S-attributed definition is L-attributed, the restrictions only apply to the
inherited attributes (not to synthesized attributes).
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 77
Semantic Rules with Controlled Side effects
* Permit incidental side effects the do not constrain attribute evaluation
* Constrain the allowable evaluation orders, so that the same translation is produced
foer any allowable order.
* Ex: For production L* En Semantic Rule is print(E.val)
Applications of Syntax-Directed Translation
* Construction of syntax Trees
* The nodes of the syntax tree are represented by objects with a suitable
number of fields.
* Each object will have an op field that is the label of the node.
* The objects will have additional fields as follows
* If the node is a leaf, an additional field holds the lexical value for
the leaf. A constructor function Leaf (op, val) creates a leaf object.
* If nodes are viewed as records, the Leaf returns a pointer to a new
record for a leaf.
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 78
* If the node is an interior node, there are as many additional fields
as the node has children in the syntax tree. A constructor function
Node takes two or more arguments:
Node (op , c1,c2,..ck) creates an object with first field op and k additional fields for
the k children c1,c2,..ck
SDD- To construct syntax tree for a simple expression
Production Semantic Rules
E → E1 + T E.node = new Node (+, E1 .node, T.node)
E → E1 - T E.node = new Node (-, E1 .node, T.node)
E → T E. node= T.node
T → ( E ) T.node = E.node
T → id T.node= new Leaf (id, id.entry)
T → num T.node= new Leaf (num, num.val)
This is an example for S-attributed definition
L-attributed definition for Simple Expression
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 79
Syntax-Directed Translation Schemes
A SDT scheme is a context-free grammar with program fragments embedded within
production bodies .The program fragments are called semantic actions and can appear at
any position within the production body.
Any SDT can be implemented by first building a parse tree and then pre-forming the
actions in a left-to-right depth first order. i.e during preorder traversal.
The use of SDTs to implement two important classes of SDDs
1. If the grammar is LR parsable, then SDD is S-attributed.
2. If the grammar is LL parsable, then SDD is L-attributed.
Postfix Translation Schemes
The postfix SDT implements the desk calculator SDD with one change: the action for
the first production prints the value. As the grammar is LR, and the SDD is S-attributed.
L * E n {print(E.val);}
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 }
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 80
F → digit { F.val = digit.lexval }
Syntax Trees
Postfix SDT's
 Leftmost: the leftmost nonterminal is always chosen for expansion at each step of
derivation.
L-attributed SDT's
 Shows a graphical depiction of a derivation.
Bottom-Up Evaluation of S-Attributed Definitions
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 81
Production Semantic Rules
L → E return {print(stack[top-1].val); top =top * 1;}
E → E1 + T {stack[top-2].val = stack[top-2].val + stack[top].val; top =
top * 2;}
E → T
T → T1 * F {stack[top-2].val = stack[top-2].val * stack[top].val; top =
top * 2;}
T → F
F → ( E ) { stack[top-2].val = stack[top-1].val ; top = top * 2;}
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).
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?).
* 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
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 82
* 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.
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
SDT for infix *to- prefix translation during parsing
L* E n
E → {print(+);} E1 + T
E → T
T → {print(*);} T1 * F
T → F
F → ( E )
F → digit { print( digit.lexval); }
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 83
A Translation Scheme Example
* A simple translation scheme that converts infix expressions to the
corresponding postfix expressions.
E → T R
R → + T { print(+) } R1
R → 
T → id { print(id.name) }
a+b+c * ab+c+
infix expression postfix expression
Inherited Attributes in Translation Schemes
* If a translation scheme has to contain both synthesized and inherited attributes, we
have to observe the following rules:
COMPILER DESIGN [10CS63] UNIT * V SDD
DEPT. OF CSE, SJBIT Page 84
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).
4. With a 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).
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 definition.



Editors




You might like this video:Watch more here

Watch more videos from this user Here

Learn how to upload a video and start earning here