Unit-4 CD - 05-03-2024
Unit-4 CD - 05-03-2024
Unit-4 CD - 05-03-2024
Intermediate code
Syntax tree , Polish notation and Three Address code ,static single assignment ,
Translation of Expressions ,Control flow Statements and Boolean Expressions
Example:
If ‘X’ is a Grammar Symbol and ‘b’ is one of its Attributes , then X.b denotes the value of ‘b’
at a particular Parse-Tree node labeled as ‘X’. Attributes can be number ,types table
reference or Strings.
num(2) num(3)
E.val=2 + T.val=12
num(2) num(3)
Evaluation order of SDD’s
The useful tool that can be used for determining an evaluation order for the attribute instances in a given parse tree
is Dependency Graph. Annotated parse tree indicates attributes values and Dependency graph helps to
determine how those values can be computed.
Dependency Graph:
Dependency Graph indicates the flow of information among the attributes instances in a
Particular Parse tree : if an edge exists from one attribute instances to another , it means that the value of the first
is needed to compute the second . These edges are used to express the constraints implied by the semantic rules.
Generally,
1.The Dependency Graph has a node for each attribute associated with X ,for each node labeled by Grammar Symbol X.
2.Let ‘P’ be a Production .If a Semantic rule associated with P defines the value of Synthesized attribute A.b in terms of
the value of X.a,then the dependency graph has an edge from X.a to A.b.
3.If a semantic rule associated with P defines the value of inherited attribute B.a interms of the value of X.a,then the
Dependency Graph has an edge from X.a to B.a.
Example: Consider the following production and rule:
PRODUCTION SEMANTIC RULE
E ->E1+ T E.val= E1.val + T.val
At every node N labeled E, with children corresponding to the body of this production ,the synthesized attribute
val at N is computed using the values of val at the two children , labeled E and T. Thus, a portion of the
Dependency graph for every parse tree .we shall show the parse tree edges as dotted lines, while the edges of
the dependency graph are solid.
Types of SDD:
1.S-Attribute SDD or S-Attribute grammar or S-Attribute Definition .
2.L-Attribute SDD or L-Attribute grammar or L-Attribute Definition .
S-Attribute L-Attribute
1.A SDD that uses only Synthesized 1.A SDD that uses both Synthesized and
Attribute is called as S-Attribute SDD Inherited Attribute is called a L-Attributed
Ex: A->BCD SDD,but each Inherited Attribute is
A.val=B.val restricted to inherits from parent or left
A.val=C.val sibling only.
A.val=D.val Ex:A->xyz {y.val=A.val,y..val=x.val}
Wrong-y.val=z.val
2.Semantic Actions are always placed at 2.Semantic Actions are placed any where
right end of the production .It is also called on RHS
as Postfix SDD.
E * T
T F
F - T num(2)
num(4) F - T
num(2) F
num(4)
Exampe 2: S->xxW {print(1);}
S->y {print(2);}
W->Sz {print(3);}
String xxxxyzz
Parse tree: S
x x W
S z
x x W
S z
y Output 23131
• Translation Scheme to convert infix to postfix expression
String 2+3*4
Production Semantic rule parse tree
E->E+T {printf(“+”);} --1 E
E->T { } ---2
T->T*F {printf(“*”);}---3 E + T 1
T->F {}---4
F->num {printf(num.lvalue}—5 T 2 T * F 3
F 4 F 4 num(4) 5
5 3
num(2) num(3)
Applications of SDD
One of the major applications of SDD is the Construction of Syntax trees .
In a Syntax tree,Operators and Keywords do not appear as leaves,but rather they are associated with interior node
would be the parent of those leaves in the parse tree.
The Syntax tree for the Expression 3*4+5 is given by ,
The Following Functions are used to create the nodes of Syntax trees for expressions with binary operators.
1)mknode(op,left,right): Creates an operator node label with op and two fields containing pointers to left and right
operands.
2)mkleaf(id,entry): Creates an identifier node with label id and a field containing entry,which is a pointer to the
Symbol-table entry for the identifier.
3)mkleaf(num,val): Creates a number node with label num and a field containing val ,the value of the number
Example : Constructs Syntax Trees for a simple expression a-4+c ,the sequence of
functions calls are
1)P1:=mkleaf(id,entry a);
2)P2:=mkleaf(num,4);
3)P3:=mknode(‘-’,P1,P2);
4)P4:=mkleaf(id,entry c);
5)P5:=mknode(‘+’,P3,P4);
Syntax Directed Translation Schemes(SDTS)
Syntax-directed translation schemes are a complementary notation to syntax directed definitions. A syntax-directed
translation scheme (SDT) 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 a production
body.
Any SDT can be implemented by first building a parse tree and then performing the actions in a left-to-right depth-
first order; that is, during a preorder traversal. Typically, SDT's are implemented during parsing, without building a
parse tree. To implement SDT's, two important classes of SDD's:
1. The underlying grammar is LR-parsable, and the SDD is S-attributed.
2. The underlying grammar is LL-parsable, and the SDD is L-attributed.
The following are commonly used intermediate code representations(or)Forms of Intermediate Code
1. Syntax Tree
2.Postfix Notation
3. Three-Address Code
1.Syntax Tree:
• Some of the Front-End of compilers translate the input source program into an intermediate form known as
Abstract Syntax tree(AST).
• Here Leaf node represents the Operands like a,b,5 etc.
• The Interior nodes correspond to the Operators like +.- etc.
• The Natural Hierarchical Structure is represented by Syntax Trees.
• The syntax tree not only condenses the parse tree but also offers an improved visual representation of the
program’s syntactic structure,
Example: x = (a + b * c) / (a – b * c)
2.Postfix Notation:
• Also known as reverse Polish notation or suffix notation.
• In the infix notation, the operator is placed between operands, e.g., a + b.
• Postfix notation positions the operator at the right end, as in ab +. For any postfix
expressions e1 and e2 with a binary operator (+) , applying the operator yields e1e2+.
• Postfix notation eliminates the need for parentheses, as the operator’s position and arity allow
unambiguous expression decoding.
• In postfix notation, the operator consistently follows the operand.
Example 1: The postfix representation of the expression
(a + b) * c is : ab + c *
Example 2: The postfix representation of the expression
(a – b) * (c + d) + (a – b) is : ab – cd + *ab -+
3. Three-Address Code:
• A three address statement involves a maximum of three references, consisting of two for operands and one for
the result.
• A sequence of three address statements collectively forms a three address code.
• The typical form of a three address statement is expressed as x = y op z, where x, y, and z represent memory
addresses.
• Each variable (x, y, z) in a three address statement is associated with a specific memory location.
• While a standard three address statement includes three references, there are instances where a statement may
contain fewer than three references, yet it is still categorized as a three address statement.
Example : The three address code for the expression a+b*c+d
T1 = b * c
T2 = a + T1
Example 1: Write Three Address Code for the following expression
a=b+c+d
The Three Address Code for the above expression as
t1=b+c
t2=t1+d
a=t2
Example 2: Write Three Address Code for the following expression
-(a+b)+(c+d)-(a+b+c+d)
The Three Address Code for the above expression as
t1=a+b
t2=uminus t1
t3=c+d
t4=t2+t3
t5=a+b
t6=t3+t5
t7=t4-t6
Representation of Three Address Code :
1.Quadruples 2.Triples 3.Indirect Triples
1.Quadruples: In Quadruples representation each instruction is
splitted into the following 4 different fields
op arg1 arg2 result
Here ,op field used for storing the internal code of the operator
The arg1 and arg2 are used for storing the two operands.
The result field is used for storing the result of the expression.
Example: a=b* -c + b* -c
Three address code as Quadruple representation as
t1=-c Location op arg1 arg2 result
t2=b*t1 (0) - c t1
t3=-c (1) * b t1 t2
(2) - c t3
t4=b*t3
(3) * b t3 t4
t5=t2+t4 (4) + t2 t4 t5
2.Triples : In Triples representation the use of temporary variables are
avoided by refering the pointers in the symbol table.each
instruction is splitted into the following 3 different fields
op arg1 arg2
Here ,op field used for storing the internal code of the operator
The arg1 and arg2 are used for storing the two operands.
Example: a=b* -c + b* -c
Three address code as Triple representation as
t1=-c
Location op arg1 arg2
t2=b*t1 (0) - c
t3=-c (1) * b (0)
t4=b*t3 (2) - c
(3) * b (2)
t5=t2+t4
(4) + (1) (3)
3.Indirect Triples : In this representation the listing of triples is being
done and listing pointers are used instead of using statements.
Example: a=b* -c + b* -c
Three address code as Indirect Triple representation as
t1=-c
t2=b*t1
(0) 100
t3=-c (1) 101
t4=b*t3 (2) 102
t5=t2+t4 (3) 103
(4) 104
Ex1: Translate the following expression to Quadruples,Triples,Indirect Triples
a+b*c/e↑f+b*c
Three address code as 1)Quadruple:
t1=e↑f LOC op arg1 arg2 result
t2=b*c (0) ↑ e f t1
t3=t2/t1 (1) * b c t2
t4=b*a (2) / t2 t1 t3
t5=a+t3 (3) * b a t4
T6=t5+t4 (4) + a t3 t5
2)Triples: (5) + t5 t4 t6
2)Triples:
loc op arg1 arg2 3)Indirect Triples:
op arg1 arg2
(0) + a b (0) (10)
(0) + a b
(1) - c d (1) (11)
(2) * (0) (1) (1) - c d
(2) (12)
(2) * (10) (11)
Ex 3: Translate the following expression to Quadruples,Triples,Indirect
Triples
Example: R=-(a+b)*(c+d)+(a+b+c)
Three address code as 1)Quadruple representation as:
t1:=a+b
t2:=-t1
t3:=c+d LOC op arg1 arg2 result
(0) + a b t1
t4:=t2*t3
(1) - t1 t2
t5:=t1+c
(2) + c d t3
t6:=t4+t5 R:=t6 (3) * t2 t3 t4
(4) + t1 c t5
(5) + t4 t5 t6
(6) = t6 R
R=-(a+b)*(c+d)+(a+b+c)
Three address code as 2)Triples:
t1:=a+b loc op arg1 arg2
t2:=-t1 (0) + a b
t3:=c+d
(1) - (0)
t4:=t2*t3
(2) + c d
t5:=t1+c
t6:=t4+t5 R:=t6 (3) * (1) (2)
3)Indirect Triples: (4) + (0) c
(5) + (3) (4)
Triple no Statement
(6) = R (5)
(0) (10)
(1) (11)
(2) (12)
(3) (13)
(4) (14)
(5) (15)
(6) (16)
Advantages of Intermediate Code Generation:
• Easier to implement: Intermediate code generation can simplify the code generation
process by reducing the complexity of the input code, making it easier to implement.
• Facilitates code optimization: Intermediate code generation can enable the use of
various code optimization techniques, leading to improved performance and
efficiency of the generated code.
• Platform independence: Intermediate code is platform-independent, meaning that it
can be translated into machine code or bytecode for any platform.
• Code reuse: Intermediate code can be reused in the future to generate code for other
platforms or languages.
• Easier debugging: Intermediate code can be easier to debug than machine code or
bytecode, as it is closer to the original source code.
Static Single Assignment:
if else:
S->if(B) then S1 else S2
Semantic rule:
B.true=newlabel()
B.false=newlabel()
S1.next=S.next;
S2.next=S.next;
S.code=B.code||Label(B.true)||S1.code||Label(B.false)||S2.code
While:
S->while E do S1
Semantic rule:
S.start=newlabel();
E.true=newlabel()
E.false=S.next;
S1.next=S.next;
S.code=label(S.begin)||E.code||label(E.true)||S1.code||label(goto
S.start)
Translation of boolean expressions: A Boolean
expression can be Translated into semantic
rules as shown:
1.B->B1||B2
B.code=B1.code||label(B1.false)||B2.code;
2. B->B1&&B2
B.code=B1.code||label(B1.true)||B2.code;
3.B->!B1
B1.true=B.false
B1.false=B.true
Run time Storage
Activation tree:
• The main aim of runtime systems is to map procedures to their
activations.
• Each execution of the procedure is called an activation .
• A procedure Definition associates an identifier with a statement or a
block of statements.
• The identifier to the procedure is called the procedure name
• An activation tree is used to determine the way the control flows
between procedures.
• During program Execution ,the control flow is sequential among
procedures.
• In a procedure ,the execution begins at the starting point of its body .
• Activation tree for the procedure call fib(4) as fib(4)
fib(3) fib(2)
fib(2) fib(1)
Storage organization: It deals with the division of memory into
different areas ,management of the activation records and layout of
the local data.
a.Sub division of run-time memory: The underlying hardware and
operating system provide a division of memory into the following
areas. Heap area
Stack area
Static area
Code area
r value
The value of the Expression is called its r-value. The value contained in a single variables also becomes
an r-value if it appears on the right-hand side of the assignment operator. r-value can always be
assigned to some other variables.
l-value
The location of the memory where an expression is stored is known as the l-value of that expression . It
ialways appears at the left hand side of the assignment operator.
Eg: Week = day * 7
Based on the parameters there are various parameter passing methods , the most common methods
are
1.Pass by value
The actual parameters are evaluated mand their r values are passed to called procedure.
2.Pass by reference
The l value ,the address of parameters passed to the called routines.