Module -5

Chapter 5 Introduction to Syntax Directed

Translation

Syllabus

2

3

4

5

6

7

SDD V/S SDT

8

9

SDD

SDD with BUP

10

SDD with TDP

11

12

Problem on SDD with BUP

13

1. Construct annotated parse tree for input 3*5+4n(VVIMP)

14

15

16

17

18

19

Home work

20

2. Construct annotated parse tree for input (3+4)*(5+6)n

21

3. Construct annotated parse tree for input 1*2*3*(4+5)n

22

23

24

25

Problem on SDD with TDP

26

Annotated tree and dependency graph

27

28

2. Write grammar and SDD for simple desk calculator and show

annotated parse tree for expression (3+4)*(5+6)n using TDP

29

Annotated parse tree for expression (3+4)*(5+6)n using TDP

3. Construct annotated parse tree for input 1*2*3*(4+5)n using TDP

30

4. Construct annotated parse tree for input (9+8*(7+6)+5)*4n using TDP

31

5. Construct annotated parse tree for input 2*5*3n using TDP

​

• Construct annotated parse tree for input (5-4)*6n using TDP

​

• Construct annotated parse tree for input 15/5+7 using TDP

​

• Home work

SDD for Declaration statement(VVIMP) [Semantic rules with controlled side effects]

32

1.Give SDD to process a variable declaration in C and construct dependency graph for the input real x,y,z

33

Dependency Graph

34

2.Int a,c

35

The structure of a Type (IMP-6M)

• In C, the type int[2][3] ,write the SDD and write annotated parse tree

for about input.

Ans: int [2][3] array of 2 array 3 integers. The corresponding type expression

array(2,array(3,integer) is represented by following tree.

​

Note: Refer class notes for annotated tree and SDD

36

5.3 Application of Syntax Directed Translation(VVIMP)

37

38

39

1.Assuming suitable syntax directed definition construct a syntax tree for

expression a-4+e (10M) (VVVIMP)

Construction of syntax tree using BUP

40

Construction steps for syntax tree

41

P1=new Leaf(id, entry-a); P2=new Leaf(num,4); P3=new Node(‘-’,P1,P2);

P4=new Leaf(id, entry-c);

P5=new Node(‘+’,P3,P4);

42

2 .Assuming suitable syntax directed definition construct a syntax tree for

expression b*3-c

​

• Home work

E🡪E+T E🡪E-T

E🡪T T🡪T*F T🡪T/F T🡪F F🡪(E)

F🡪digit F🡪id

43

3 .Assuming suitable syntax directed definition construct a syntax tree for

expression c+4/5

​

• Home work

E🡪E+T E🡪E-T

E🡪T T🡪T*F T🡪T/F T🡪F F🡪(E)

F🡪digit F🡪id

44

4.Assuming TDP syntax directed definition to construct a syntax tree for

expression a-e+4

• Use below grammar with semantic rule
• E🡪TE’
• E🡪+TE’
• E’🡪-TE’
• E’🡪€
• T🡪FT’
• T🡪*FT’
• T🡪/FT’
• T🡪€
• F🡪(E)
• F🡪id
• F🡪num

[ refer Class Notes]

Syntax Directed Translation scheme(out of syllabus)

45

Postfix SDT for desk calculator-continue..

46

Parser stack implementation of postfix SDT-Continue

47

48

​

Module -5

Chapter 6 Intermediate Code Generation

49

Chapter 6 Intermediate Code Generation

50

• Variants of Syntax tree
• Three Address Code

Intermediate Code Generation

51

52

53

6.1 Variants of Syntax tree

54

6.1.1 Directed Acyclic Graph for Expressions

55

• The syntax tree for an expression, a DAG has leaves corresponding to

atomic operands and interior codes corresponding to operators.

• The difference is that a node ‘N’ in a DAG has more than one parent.
• if ‘N’ represents a common subexpression.
• In a syntax tree , the tree for the common subexpression would be replicated as many times as the subexpression appears in the original expression.
• DAG not only represent expression , it gives the compiler important clues regarding the generation of efficient code to evaluate the expression.

1.write DAG for below expression a+a*(b-c)+(b-c)*d

56

• The leaf for ‘a’ has 2 parents, because ‘a’ appears in the expressions.
• Two occurrence of the common subexpression b-c are represented by one node , he node labeled by –
• That node has 2 parents , representing its two uses in the subexpression

a*(b-c) and (b-c)*d.

• Even though ‘b’ and ‘c’ appears twice in the complete expression, their nodes each have one parent, since both uses are in the common subexpression b-c.

SDD for Directed Acyclic Graph for Expressions

57

58

• We assume that entry-1 points to the symbol table entry for ‘a’ and

similarly for other identifier.

• When the call to leaf(id,entry-1) is repeated at step2, the node created by the previous call is returned so p2=p1.
• Similarly, the nodes returned at step8 and 9 are the same as those returned at step 3 and 4(i.e p8=p3, p9=p4).
• Hence the nodes returned at step 10 must be the same at that returned at step5. ie p10=p5.

6.1.2 The value number method for constructing DAG

59

• The nodes of a syntax tree or DAG are stored in an array of records as

shown in below figure.

• Ex: Nodes of a DAG i=i+10 allocated in an array.
• Each row of the array represents one record and therefore one node.
• In each record, the first field is an operation code, indicating the label of the node.
• Fig b leaves have one additional field ,which holds the lexical value(either a symbol table pointer or constant) and interior nodes have two additional fields indicating the left and right children.

60

• In this array , we refer to nodes by giving the integer index of the record for that

node within the array.

• This integer historically has been called the value number for the node or for the expression represented by the node.
• Above figure ,the node labeled + have value number 3 and its left and right children

have number 1 and 2 respectively.

• Use pointer to record or reference to objects instead of integer indexes ,but we shall still refer to the reference to a node as its “valve No” .If stored in an appropriate data structure, value number helps us construct expressions DAG efficiently.

61

Algorithm for value number method for constructing DAG

Input: Label op,node l,and node r

Output: The value number of a node in the array with

signature <op,l,r >

Problems on DAG and value number method

1. ((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))

2. Construct the DAG and identify the value number for the sub expression

of the following expressions, assuming + associates from left.

1. a+b+(a+b)
2. a+b+a+b

c) a+a+(a+a+a+(a+a+a+a))

62

6.2 Three Address Code

63

6.2.1 Address and Instruction

64

Instruction of 3-address code

65

Continue

66

Example of three address instruction

67

68

Consider the statement do i=i+1;while(a[i]<v);write 2possible translation of above statement using three address code instruction.

Note: the multiplication i*8 is appropriate for an array of elements that each take

8 units of space.

1.Difference between syntax tree and DAG for x=(a+b*c)/(a-b*c)

69

2.Difference b/w syntax tree &DAG for a+b*c-d/b*c

70

6.2.2 Quadruples

71

• The description of 3-address instruction specify the components of each type of instruction, but it does not specify the representation of these instruction in a data structure.
• Ina compiler, these instruction can be implemented as objects or as records

with fields for the operator and operands.

• Three such representation are called “Quadruple”, “Triples”, and “Indirect

Triples”.

72

Example of different form of records

73

Example for 3-address code

74

Quadruple

75

• A “Quadruple” has 4 fields, which we call op,arg1,arg2 and result.
• Op field contains an internal code for the operator.
• Ex: 3-address instruction x=y+z is represented by ‘+’ in op, y in arg1,z in arg2 and ‘x’ in result.
• The following are some exception to this rule
• Instructions with unary operator like x=minus y or x=y do not use arg2. note that for a copy statement like x=y, op is = while for most other operations, the assignment operator is implied.
• Operator like param use neither arg2 nor result.
• Conditional and unconditional jumps put the target label in result.

1.Write the 3-addres code for the assignment a=b*-c+b*-c and also quadruple.(VVVVIMP)

76

77

2 Write the 3-addres code for the assignment (a+b*c)-(d/b*c) and also

quadruple.

3.Write the 3-addres code for the assignment a=b+c*d and

also quadruple.

78

6.2.3 Triples

79

• A Triple has only 3 fields, which we call op,arg1, and arg2.
• The result field in a quadruples is used primarily for temporary names. Using triples we refer to the result of an operation x op y by its position, rather than by an explicit temporary name.
• Instead of the temporary ‘t1’ in quadruple , a triple representation would refer to position(0).
• Parenthesized numbers represents pointer into the triple structure itself.

Write syntax tree and triples for expression a+a*(b-c)+(b-c)*d

80

• We construct syntax tree in fig a and fig b shows Triples.

2 Write the 3-addres code for the assignment (a+b*c)-(d/b*c) and also

Triples

81

• Triples shown in figure

3.Write the 3-addres code for the assignment a=b+c*d and also Triples.

82

Indirect Triples

83

• In this, an optimizing compiler can move an instruction by reordering the instruction list, without affecting the triples themselves.
• When implemented in java, an array of instruction objects is analogous to an indirect triple representation, since JAVA treats the array elements as reference to objects.

Examples of Indirect Triples for (a+b*c)-(d/b*c)

84

Translate the arithmetic expression a+-(b+c) into

85

a) Syntax tree b) Quaduples c)Triples d)Indirect Triples

​

​

• Home work

6.2.4 Static single Assignment Form(SSA)

86

• SSA is an optimization.

intermediate

representation

that

facilities

certain

code

• Two distinctive aspects distinguish SSA from 3 address code.
• All assignment in SSA are to variables with distinct names; Hence the term

static single assignment .

• Below figure shows the same intermediate program in 3 address code and in static single assignment form .subscripts distinguish each definition of variables p and q in the SSA representation.

87

The same variable may be defined in 2 different control flow path in a program.

88

89

• The source program,
• If(flag) x=-1;else x=1;
• Y=x*a;
• Has two control flow paths in which the variable ‘X’ gets defined.
• If we use different names for X in the true part and the false part of the conditional statement , then which name should we use in assignment y=x*a?

90

• Here is where the 2^nd distinctive aspect of SSA comes into play?
• SSA uses a notational convention called the ᶲ function to combine the two definition of x:

If(flag) x1=-1;else x2=1; X3= ᶲ(x1,x2);

Here, ᶲ(x1,x2) has value ‘x1’ if the control flow passes through the true part of the conditional and the value x2 if the control flow passes through the false part.

i.e ᶲ-function returns the value of its argument that corresponds to the control flow path that was taken to get to the assignment statement containing the ᶲ-function.

THANK YOU

91

THANK YOU

92