Principles of Programming Languages

Principles of Programming Languages

h"p://www.di.unipi.it/~andrea/Dida2ca/PLP-16/

Prof. Andrea Corradini

Department of Computer Science, Pisa

•  Intermediate-Code Genera=on

–  Intermediate representa=ons

–  Syntax-directed transla=on to three address code

Lesson 11!

2

Intermediate Code Genera=on (II)

•  Facilitates retarge&ng: enables aGaching a back end for the new machine to an exis=ng front end

Syntax-Directed Defini=ons Syntax-Directed Transla=on Schemes

Back end

Intermediate

code Target

code

Tokens

Summary

•  Intermediate representa=ons

•  Three address statements and their implementa=ons

•  Syntax-directed transla=on to three address statements

–  Expressions and statements

–  Logical and rela=onal expressions

–  Transla=ng short-circuit Boolean expressions and flow-of-

control statements with backpatching lists

4

Intermediate Representa=ons

•  Graphical representa&ons (e.g. AST and DAGs)

•  Pos2ix nota&on: opera=ons on values stored on operand stack (similar to JVM bytecode)

•  Three-address code: (e.g. triples and quads) x := y op z

•  Two-address code:

x := op y

which is the same as x := x op y

Syntax-Directed Transla=on of Abstract Syntax Trees

Produc=on S → id := E E → E

+ E

E → E

* E

E → - E

E → ( E

) E → id

Seman=c Rule

S.nptr := mknode(‘:=’, mkleaf(id, id.entry), E.nptr) E.nptr := mknode(‘+’, E

.nptr, E

.nptr)

E.nptr := mknode(‘*’, E

.nptr, E

.nptr) E.nptr := mknode(‘uminus’, E

.nptr) E.nptr := E

.nptr

E.nptr := mkleaf(id, id.entry)

6

Abstract Syntax Trees

E.nptr

* E.nptr

E.nptr a!

b!

+ E.nptr

*!

a! +!

b! c!

E.nptr c E.nptr

( )

a * (b + c)!

Pro: easy restructuring of code and/or expressions for

intermediate code op=miza=on

Cons: memory intensive

Abstract Syntax Trees versus DAGs

:=

a +

*

uminus b

c

*

uminus b

Tree c

:=

a +

*

uminus b

c DAG

a := b * -c + b * -c!

•  Repeated subtrees are shared

•  Implementa=on: mkleaf and makenode are redefined. They do

8

Pos]ix Nota=on

a := b * -c + b * -c!

iload 2 // push b iload 3 // push c ineg // uminus imul // *

iload 2 // push b iload 3 // push c ineg // uminus imul // *

iadd // +

istore 1 // store a

Bytecode (for example) a b c uminus * b c uminus * + assign

Pos]ix nota=on represents opera=ons on a stack

Pro: easy to generate

Cons: stack opera=ons are more

difficult to op=mize

Three-Address Code (1)

a := b * -c + b * -c!

t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t4 a := t5

Linearized representation of a syntax tree

:=

a +

*

uminus b

c

*

uminus b

Tree c

Three-Address Code (2)

a := b * -c + b * -c!

t1 := - c t2 := b * t1 t5 := t2 + t2 a := t5

Linearized representation of a syntax DAG

:=

a +

*

uminus b

c DAG

Three-Address Statements

“Addresses” are names, constants or temporaries

•  Assignment statements: x:= y op z, x:= op y

•  Indexed assignments: x:= y[i], x[i]:= y

•  Pointer assignments: x:= &y, x:= *y, *x:= y

•  Copy statements: x:= y

•  Unconditional jumps: goto lab

•  Conditional jumps: if x relop y goto lab

•  Function calls: param x… ; call p, n

(or y = call p, n) ; return y

Implementa=on of Three-Address Statements: Quads

# Op Arg1 Arg2 Res

(0) uminus c t1

(1) * b t1 t2

(2) uminus c t3

(3) * b t3 t4

(4) + t2 t4 t5

(5) := t5 a

Quads (quadruples) Pro: easy to rearrange code for global op=miza=on Cons: lots of temporaries

Three-address code

t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t4 a := t5

Sample expression

a := b * -c + b * -c

!

Implementa=on of Three-Address Statements: Triples

# Op Arg1 Arg2

(0) uminus c

(1) * b (0)

(2) uminus c

(3) * b (2)

(4) + (1) (3)

(5) := a (4)

Triples Pro: temporaries are implicit

Three-address code

t1 := - c t2 := b * t1 t3 := - c t4 := b * t3 t5 := t2 + t4 a := t5

Sample expression

a := b * -c + b * -c

!

Implementa=on of Three-Address Statements: Indirect Triples

# Op Arg1 Arg2

(14) uminus c

(15) * b (14)

(16) uminus c

(17) * b (16)

(18) + (15) (17)

(19) := a (18)

Triple container

Pro: temporaries are implicit & easier to rearrange code

# Stmt (0) (14) (1) (15) (2) (16) (3) (17) (4) (18) (5) (19)

Program

Syntax-Directed Transla=on into Three-Address Code

Synthesized attributes:

S.code three-address code for S S.begin label to start of S or nil S.after label to end of S or nil E.code three-address code for E

E.place a name holding the value of E ProducEons

S → id := E

| while E do S | S ; S

E → E + E | E * E | - E | ( E ) | id

| num gen(E.place ‘:=’ E

.place ‘+’ E

.place)

Syntax-Directed Transla=on into Three-Address Code (cont’d)

ProducEons S → id := E S → while E do S₁ E → E₁ + E₂ E → E₁ * E₂ E → - E₁ E → ( E₁ ) E → id E → num S → S₁ ; S₂

Semantic rules

S.code := E.code || gen(id.place ‘:=’ E.place); S.begin := S.after := nil (see next slide)

E.place := newtemp();

E.code := E₁.code || E₂.code || gen(E.place ‘:=’ E₁.place ‘+’ E₂.place) E.place := newtemp();

E.code := E₁.code || E₂.code || gen(E.place ‘:=’ E₁.place ‘*’ E₂.place) E.place := newtemp();

E.code := E₁.code || gen(E.place ‘:=’ ‘uminus’ E₁.place) E.place := E₁.place

E.code := E₁.code E.place := id.name E.code := ‘’

E.place := newtemp();

E.code := gen(E.place ‘:=’ num.value)

S.code := S₁.code || S₂.code S.begin := S₁. begin S.after := S₂.after

Syntax-Directed Transla=on into Three-Address Code (cont’d)

ProducEon

S → while E do S₁

Semantic rule

S.begin := newlabel() S.after := newlabel()

S.code := gen(S.begin ‘:’) ||

E.code ||

gen(‘if’ E.place ‘=‘ ‘0’ ‘goto’ S.after) ||

S₁.code ||

gen(‘goto’ S.begin) ||

…

if E.place = 0 goto S.after S.code

E.code

goto S.begin

S.begin:

S.after:

18

Example (check it at home!)

i := 2 * n + k;


while i do


i := i - k!

t1 := 2

t2 := t1 * n t3 := t2 + k i := t3

L1: if i = 0 goto L2 t4 := i - k

i := t4 goto L1 L2:

How does the code access names?

•  The three-address code generated by the syntax- directed defini=ons shown is simplis=c

•  It assumes that the names of variables can be easily resolved by the back-end in global or local variables

•  We need local symbol tables to record global declara=ons as well as local declara=ons in procedures, blocks, and records (structs) to resolve names

•  We will see all this later in the course

Transla=ng Logical and Rela=onal Expressions

a or b and not c

t1 := not c

t2 := b and t1 t3 := a or t2

if a < b goto L1 t1 := 0

goto L2 L1: t1 := 1 L2:

a < b

Boolean expressions intended to represent values:

Boolean expressions used to alter the control flow:

Short-Circuit Code

•  The boolean operators &&, || and ! are translated into jumps.

•  Example:

if ( x < 100 || x > 200 && x != y ) x = 0;

may be translated into:

if x < 100 goto L2

ifFalse x > 200 goto L1 ifFalse x ! = y goto L1 L2: x=0

L1:

Transla=ng Flow-of-control Statements

22

·˨̊ᗮ

"Đdz 67.XÆ>dz
Ư
 dz

ߖ੎ᗮྲྀအᑌᗮहအྲྀበೊ়੎ᅻᗮዔఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀᗮအ૤ᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበ೔အྲྀበᗮ೔ྲྀዔအᗮዔఀᅻ੎੎Ÿࡐ়়ᅻ੎በበᗮहအ়੎ᗮ

ೊྲྀᗮዔఀ੎ᗮहအྲྀዔ੎ᒏዔᗮအ૤ᗮበዔࡐዔ੎༌੎ྲྀዔበᗮበᎯहఀᗮࡐበᗮዔఀအበ੎ᗮஸ੎ྲྀ੎ᅻࡐዔ੎়ᗮ࣒ᒹᗮዔఀ੎ᗮ૤အเเအᑌ೔ྲྀஸᗮஸᅻࡐ༌༌ࡐᅻгᗮ

ŗ͆ ^ҿ

͆ ҿ

͆ Hҿ

ɼÎ׋^͆æ׋ ^ŗ:͆

ɼÎ׋^͆æ׋ f͆

ɼ %͆

'
ɼ Î׋^͆æ׋ ^:͆

צྮᗮዔఀ੎በ੎ᗮႼᅻအ়Ꭿहዔೊအྲྀበýᗮ࿘အྲྀዔ੎ᅻ༌೔ྲྀࡐเᗮ

ᅻ੎Ⴜᅻ੎በ੎ྲྀዔበᗮࡐᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበೊအྲྀᗮࡐྲ়ྀᗮྲྀအྲྀᔳ ዔ੎ᅻ༌ೊྲྀࡐเᗮ

ᅻ੎Ⴜᅻ੎በ੎ྲྀዔበᗮࡐᗮበዔࡐዔ੎༌੎ྲྀዔȪᗮ

ݫ౵ೊበᗮஸᅻࡐ༌༌ࡐᅻᗮஸ੎ྲྀ੎ᅻࡐเ೔ᔎ੎በᗮዔఀ੎ᗮᅻᎯྲྀྲྀ೔ྲྀஸᗮ੎ᒏࡐ༌Ⴜเ੎ᗮအ૤ᗮᑌఀ೔เ੎ᗮ੎ᒏწᅻ੎በበೊအྲྀበᗮዔఀࡐዔᗮᑌ੎ᗮ

ೊྲྀዔᅻအ়Ꭿह੎়ᗮೊగᗮիᒏࡐ༌Ⴜเ੎ᗮΥȪ ̊ДȪᗮ ӕበᗮೊྲྀᗮዔఀࡐዔᗮ੎ᒏࡐ༌Ⴜเ੎ýᗮ࣒အዔఀᗮԊ ࡐྲ়ྀᗮ

ఀࡐᐕ੎ᗮࡐᗮበᒹྲྀዽఀ੎ᔳ በೊᔎ੎়ᗮࡐዔዔᅻ೔࣒Ꭿዔ੎ᗮ

ᑌఀೊहఀᗮஸೊᐕ੎በᗮዔఀ੎ᗮዔᅻࡐྲྀበเ࡭ዔೊအྲྀᗮೊྲྀዔအᗮዔఀᅻ੎੎Ÿࡐ়়ᅻ੎በበᗮೊྲྀበዔᅻᎯहዔೊအྲྀበȪᗮ

֏အᅻᗮበ೔༌Ⴜเೊह೔ዔᒹýᗮ ᑌ੎ᗮ࣒Ꭿ೔เ়ᗮᎯႼᗮዔఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀበᗮ

ࡐྲ়ྀᗮ

ࡐኪᗮበዔᅻ೔ྲྀஸበýᗮᎯበᔳ

ೊྲྀஸᗮበᒹྲྀዔࡐᒏŸ়೔ᅻ੎हዔ੎়ᗮ়੎୪ྲྀ೔ዔೊအྲྀበȷᗮ ݫఀ੎ᗮበ੎༌ࡐྲྀዔೊहᗮᅻᎯเ੎በᗮ়੎୪ྲྀೊྲྀஸᗮዔఀ੎ ʗᗮ

ࡐዔዔᅻ೔࣒Ꭿዔ੎በᗮ हအᏆเ়ᗮ࣒੎ᗮೊ༌Ⴜเ੎༌੎ྲྀዔ੎়ᗮೊྲྀበዔ੎ࡐ়ᗮ࣒ᒹᗮ࣒Ꭿೊเ়ೊྲྀஸᗮᏅႼᗮ በᒹྲྀዔࡐᒏᗮዔᅻ੎੏በᗮࡐྲ়ྀᗮዔఀ੎ྲྀᗮ੎༌ೊዔዔೊྲྀஸᗮ हအ়੎ᗮ৲Ꭿᅻೊྲྀஸᗮࡐᗮዔᅻ੎਼ᗮዔᅻࡐᐕ੎ᅻበࡐเýᗮအᅻᗮ࣒ᒹᗮࡐྲྀᒹᗮအ૤ᗮዔఀ੎ᗮࡐႼზᅻအࡐहఀ੎በᗮအᎯዔเ೔ྲྀ੎়ᗮೊྲྀᗮܺ੎हዔೊအྯᗮΥȪΥȪᗮ ݫఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀᗮအ૤ᗮ

हအྲྀበ೔በዔበᗮအ૤ᗮ

૤အเเအᑌ੎়ᗮ࣒ᒹᗮ

ࡐበᗮ೔เเᎯበᔳ ዔᅻࡐዔ੎়ᗮೊྲྀᗮ֏ೊஸȪᗮνȪͯΥ

ࡐÃ Ȫᗮ ߖೊዔఀ೔ྲྀᗮ

ࡐᅻ੎ᗮෟᎯ༌Ⴜበᗮ࣒ࡐበ੎়ᗮအྲྀᗮዔఀ੎ᗮᐕࡐเᎯ੎ᗮအ૤ᗮ

צ૤ᗮ

೔በᗮዔᅻᎯ੎ýᗮहအྲྀዔᅻအเᗮ஛အᑌበᗮዔအᗮዔఀ੎ᗮ୪ᅻበዔᗮೊྲྀበዔᅻᎯहዔ೔အྲྀᗮအ૤ᗮ

ࡐྲ়ྀᗮ೔૤ᗮ

ೊበᗮ૤ࡐเበ੎ýᗮहအྲྀዔᅻအเᗮ

஛အᑌበᗮዔအᗮዔఀ੎ᗮೊྲྀበዔᅻᎯहዔೊအྲྀᗮ೔༌༌੎়ೊࡐዔ੎เᒹᗮ૤အเเအᑌ೔ྲྀஸᗮ

ዔအᗮ

(¡ 
͆

ዔအᗮ

ƾ֖֕֗֘ūҿ

( 
͆

ዔအᗮ

ƿ֛֚֙֜

ዔᗮ

(¡
͆

(„ !
͆ ¹͆

: Þ 
͆ (¡ !
͆ ¹͆

2Ŵ  
͆


͆ ¹͆ 'Ϯ  
i!͆

Ï

ࡐÃᗮ೔૤ᗮ

2%  
͆

¡ 
i!͆ ¹͆    ͆

0
 ͆ ¹͆

ዔအᗮ

( 
͆

ዔအᗮ

࣒

ೊ૤Ɖ੎เበ੎ᗮ

( !
͆ ɧ͆

2Ŵ  
͆

'Ϯ0
 ͆

(ď
͆

हÃᗮ ᑌఀ೔เ੎ᗮ

֍ೊிᎯᅻ੎ᗮνȩͯΥюᗮ Ԧအ়੎ᗮ૤အᅻᗮೊ૤Ɓýᗮ೔૤Ÿ੎เበ੎ƅýᗮࡐྲ়ྀᗮᑌఆೊเ੎Ÿበዔࡐዔ੎༌੎ྲྀዔበᗮ

ݫఀ੎ᗮเࡐ࣒੎เበᗮ૤အᅻᗮዔఀ੎ᗮෟᎯ༌Ⴜበᗮ೔ྲྀᗮ

ࡐྲ়ྀᗮ

ࡐᅻ੎ᗮ༌ࡐྲྀࡐஸ੎়ᗮᎯበೊྲྀஸᗮ೔ྲྀఀ੎ᅻೊዔ੎়ᗮ ࡐዔዔᅻೊ࣒Ꭿዔ੎በȪᗮ ߖ೔ዔఀᗮࡐᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበ೔အྲྀᗮ

ᑌ੎ᗮࡐበበအहೊࡐዔ੎ᗮዔᑌအᗮเࡐ࣒੎เበюᗮ

ዔఀ੎ᗮ

Synthesized A"ributes:

S.code, B.Code

Inherited A"ributes:

labels for jumps:

B.true, B.false, S.next

·˨̊ᗮ

"Đdz 67.XÆ>dz
Ư
 dz

ߖ੎ᗮྲྀအᑌᗮहအྲྀበೊ়੎ᅻᗮዔఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀᗮအ૤ᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበ೔အྲྀበᗮ೔ྲྀዔအᗮዔఀᅻ੎੎Ÿࡐ়়ᅻ੎በበᗮहအ়੎ᗮ

ೊྲྀᗮዔఀ੎ᗮहအྲྀዔ੎ᒏዔᗮအ૤ᗮበዔࡐዔ੎༌੎ྲྀዔበᗮበᎯहఀᗮࡐበᗮዔఀအበ੎ᗮஸ੎ྲྀ੎ᅻࡐዔ੎়ᗮ࣒ᒹᗮዔఀ੎ᗮ૤အเเအᑌ೔ྲྀஸᗮஸᅻࡐ༌༌ࡐᅻгᗮ

ŗ͆ ҿ

͆ ҿ

͆ Hҿ

ɼÎ׋^͆æ׋ ^ŗ:͆

ɼÎ׋^͆æ׋ f͆

ɼ %͆

'
ɼ Î׋^͆æ׋^:͆

צྮᗮዔఀ੎በ੎ᗮႼᅻအ়Ꭿहዔೊအྲྀበýᗮ࿘အྲྀዔ੎ᅻ༌೔ྲྀࡐเᗮ^͆ᅻ੎Ⴜᅻ੎በ੎ྲྀዔበᗮࡐᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበೊအྲྀᗮࡐྲ়ྀᗮྲྀအྲྀᔳ ዔ੎ᅻ༌ೊྲྀࡐเᗮ͆ᅻ੎Ⴜᅻ੎በ੎ྲྀዔበᗮࡐᗮበዔࡐዔ੎༌੎ྲྀዔȪᗮ

ݫ౵ೊበᗮஸᅻࡐ༌༌ࡐᅻᗮஸ੎ྲྀ੎ᅻࡐเ೔ᔎ੎በᗮዔఀ੎ᗮᅻᎯྲྀྲྀ೔ྲྀஸᗮ੎ᒏࡐ༌Ⴜเ੎ᗮအ૤ᗮᑌఀ೔เ੎ᗮ੎ᒏწᅻ੎በበೊအྲྀበᗮዔఀࡐዔᗮᑌ੎ᗮ

ೊྲྀዔᅻအ়Ꭿह੎়ᗮೊగᗮիᒏࡐ༌Ⴜเ੎ᗮΥȪ ̊ДȪᗮ ӕበᗮೊྲྀᗮዔఀࡐዔᗮ੎ᒏࡐ༌Ⴜเ੎ýᗮ࣒အዔఀᗮԊ ࡐྲ়ྀᗮ͆ఀࡐᐕ੎ᗮࡐᗮበᒹྲྀዽఀ੎ᔳ በೊᔎ੎়ᗮࡐዔዔᅻ೔࣒Ꭿዔ੎ᗮ
͆ᑌఀೊहఀᗮஸೊᐕ੎በᗮዔఀ੎ᗮዔᅻࡐྲྀበเ࡭ዔೊအྲྀᗮೊྲྀዔအᗮዔఀᅻ੎੎Ÿࡐ়়ᅻ੎በበᗮೊྲྀበዔᅻᎯहዔೊအྲྀበȪᗮ

֏အᅻᗮበ೔༌Ⴜเೊह೔ዔᒹýᗮ ᑌ੎ᗮ࣒Ꭿ೔เ়ᗮᎯႼᗮዔఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀበᗮ^͆
͆ࡐྲ়ྀᗮ^Ɩ͆
͆ࡐኪᗮበዔᅻ೔ྲྀஸበýᗮᎯበᔳ

ೊྲྀஸᗮበᒹྲྀዔࡐᒏŸ়೔ᅻ੎हዔ੎়ᗮ়੎୪ྲྀ೔ዔೊအྲྀበȷᗮ ݫఀ੎ᗮበ੎༌ࡐྲྀዔೊहᗮᅻᎯเ੎በᗮ়੎୪ྲྀೊྲྀஸᗮዔఀ੎ ʗᗮ^ǎ
͆ࡐዔዔᅻ೔࣒Ꭿዔ੎በᗮ हအᏆเ়ᗮ࣒੎ᗮೊ༌Ⴜเ੎༌੎ྲྀዔ੎়ᗮೊྲྀበዔ੎ࡐ়ᗮ࣒ᒹᗮ࣒Ꭿೊเ়ೊྲྀஸᗮᏅႼᗮ በᒹྲྀዔࡐᒏᗮዔᅻ੎੏በᗮࡐྲ়ྀᗮዔఀ੎ྲྀᗮ੎༌ೊዔዔೊྲྀஸᗮ हအ়੎ᗮ৲Ꭿᅻೊྲྀஸᗮࡐᗮዔᅻ੎਼ᗮዔᅻࡐᐕ੎ᅻበࡐเýᗮအᅻᗮ࣒ᒹᗮࡐྲྀᒹᗮအ૤ᗮዔఀ੎ᗮࡐႼზᅻအࡐहఀ੎በᗮအᎯዔเ೔ྲྀ੎়ᗮೊྲྀᗮܺ੎हዔೊအྯᗮΥȪΥȪᗮ ݫఀ੎ᗮዔᅻࡐྲྀበเࡐዔೊအྲྀᗮအ૤ᗮɼǬ"͆:͆हအྲྀበ೔በዔበᗮအ૤ᗮ^{# 
͆}૤အเเအᑌ੎়ᗮ࣒ᒹᗮ^{ŗ:  
͆}ࡐበᗮ೔เเᎯበᔳ ዔᅻࡐዔ੎়ᗮೊྲྀᗮ֏ೊஸȪᗮνȪͯΥ_ÏࡐÃ Ȫᗮ ߖೊዔఀ೔ྲྀᗮ^{# 
͆}ࡐᅻ੎ᗮෟᎯ༌Ⴜበᗮ࣒ࡐበ੎়ᗮအྲྀᗮዔఀ੎ᗮᐕࡐเᎯ੎ᗮအ૤ᗮ^͆ צ૤ᗮ^͆

೔በᗮዔᅻᎯ੎ýᗮहအྲྀዔᅻအเᗮ஛အᑌበᗮዔအᗮዔఀ੎ᗮ୪ᅻበዔᗮೊྲྀበዔᅻᎯहዔ೔အྲྀᗮအ૤ᗮ^{: ͆
͆}ࡐྲ়ྀᗮ೔૤ᗮ^͆ೊበᗮ૤ࡐเበ੎ýᗮहအྲྀዔᅻအเᗮ

஛အᑌበᗮዔအᗮዔఀ੎ᗮೊྲྀበዔᅻᎯहዔೊအྲྀᗮ೔༌༌੎়ೊࡐዔ੎เᒹᗮ૤အเเအᑌ೔ྲྀஸᗮ^{: '͆
͆}

ዔအᗮ^{( !
͆}

(¡ 
͆ ዔအᗮ^(¡ď
͆

ƾ֖֕֗֘ūҿ

( 
͆ ዔအᗮ

ƿ֛֚֙֜

ዔᗮ (¡ !
͆

(¡
͆

(„ !
͆ ¹͆

: Þ 
͆ (¡ !
͆ ¹͆

2Ŵ  
͆


͆ ¹͆ 'Ϯ  
i!͆

ÏࡐÃᗮ೔૤ᗮ (ď
͆ ¹͆

2%  
͆

¡ 
i!͆ ¹͆    ͆

0
 ͆ ¹͆ ዔအᗮ^{(¡ !
͆}

( 
͆ ዔအᗮ^{(¡ď
͆ Ï}࣒_Η׋ೊ૤Ɖ੎เበ੎ᗮ

( !
͆ ɧ͆

2Ŵ  
͆

'Ϯ0
 ͆

(ď
͆ हÃᗮ ᑌఀ೔เ੎ᗮ

֍ೊிᎯᅻ੎ᗮνȩͯΥюᗮ Ԧအ়੎ᗮ૤အᅻᗮೊ૤Ɓýᗮ೔૤Ÿ੎เበ੎ƅýᗮࡐྲ়ྀᗮᑌఆೊเ੎Ÿበዔࡐዔ੎༌੎ྲྀዔበᗮ

ݫఀ੎ᗮเࡐ࣒੎เበᗮ૤အᅻᗮዔఀ੎ᗮෟᎯ༌Ⴜበᗮ೔ྲྀᗮ͆
͆ࡐྲ়ྀᗮ2'͆
͆ࡐᅻ੎ᗮ༌ࡐྲྀࡐஸ੎়ᗮᎯበೊྲྀஸᗮ೔ྲྀఀ੎ᅻೊዔ੎়ᗮ ࡐዔዔᅻೊ࣒Ꭿዔ੎በȪᗮ ߖ೔ዔఀᗮࡐᗮ࣒အအเ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበ೔အྲྀᗮ^͆ᑌ੎ᗮࡐበበအहೊࡐዔ੎ᗮዔᑌအᗮเࡐ࣒੎เበюᗮ ^͆!
͆ዔఀ੎ᗮ

23

˙ -$˙° ˙  $#ZKZ˙= $ ˙

แࡐ࣒੎แᗮዏအᗮᑌఀೊहఀᗮहအྲྀዏᅻအแᗮ஛အᑌበᗮೊ૤ᗮ#͆ೊበᗮዏᅻᎯ੎ûᗮࡐྲ়ྀᗮ#
͆ዏఀ੎ᗮแࡐ࣒੎แᗮዏအᗮᑌఀೊहఀᗮहအྲྀዏᅻအแᗮ

஛အᑌበᗮ ೊ૤ᗮ^#͆ೊበᗮ૤ࡐแበ੎ȩᗮ ߖೊዏఀᗮ ࡐᗮ በዏࡐዏ੎༌੎ྲྀዏᗮ^/͆ ᑌ੎ᗮ ࡐበበအहೊࡐዏ੎ᗮ ࡐྲྀᗮ ೊྲྀఀ੎ᅻೊዏ੎ীᗮ ࡐዏዏᅻೊ࣒Ꭿዏ੎ᗮ

ɣȁϏ
i়͆੎ྲྀအዏೊྲྀஸᗮࡐᗮแࡐ࣒੎แᗮ૤အᅻᗮዏఀ੎ᗮೊྲྀበዏᅻᎯहዏೊအྲྀᗮೊ༌༌੎়ೊࡐዏ੎แᒹᗮ ࡐ૤ዏ੎ᅻᗮዏఀ੎ᗮहအ়੎ᗮ૤အᅻᗮ͆

צྲྀᗮበအ༌੎ᗮहࡐበ੎በûᗮዏఀ੎ᗮೊྲྀበዏᅻᎯहዏೊအྲྀᗮೊ༌༌੎়ೊࡐዏ੎แᒹᗮ૤အแแအᑌೊྲྀஸᗮ͆
͆ೊበᗮࡐᗮෟᎯ༌Ⴜᗮዏအᗮበအཌ੎ᗮ แࡐ࣒੎แᗮ ^@ť ĕťෟᎯ༌ႼᗮዏအᗮࡐᗮෟᎯ༌Ⴜᗮዏအᗮ^ť૤ᅻအ༌ᗮᑌೊዏఀೊྲྀᗮ^2͆
͆ೊበᗮࡐᐕအೊ়੎়ᗮᎯበೊྲྀஸᗮ^͆
i͆

ݫఀ੎ᗮበᒹྲྀዏࡐᒏŸ়ೊᅻ੎हዏ੎়ᗮ়੎୪ྲྀೊዏೊအྲྀᗮೊྲྀᗮ֍ೊஸȪᗮνȩͯϕŸνȩͯϚᗮႼᅻအ়Ꭿह੎በᗮዏఀᅻ੎੎Ɖࡐ়়ᅻ੎በበᗮहအ৸੎ᗮ

૤အᅻᗮ࣒အအแ੎ࡐྲྀᗮ੎ᒏႼᅻ੎በበೊအྲྀበᗮೊྲྀᗮዏఀ੎ᗮहအྲྀዏ੎ᒏዏᗮအ଄ᗮೊ૤Ÿûᗮ್૤Ÿ੎แበ੎Ÿûᗮࡐྲ়ྀᗮᑌఀೊแ੎Ÿበዏࡐዏ੎༌੎ྲྀዏበȪᗮ

DF;VT);:u

ŏ؛ ò ^͆

͆ Ŵ؛ (ɼ

N!36T)u GV1!Ou

͆
i͆ 
90
T͆

ΦϏ
͆ ͆
͆© © ͆0
͆͆
i\͆

͆
͆ (Iɼ
͆

͆ Ď؛ ɼ͆ #͆ \͆ ɂ͆ #͆
͆
ҿ 
9ʿ
T͆

#
͆ / 2h  
i͆ / ƥ 
i͆

2 
͆ /

͆ Ď؛ ȣɼ͆ #͆\͆ 2h͆

ɼ%͆ #͆
͆
ҿ 
90
T͆

#͆
͆ / 
90
T͆

: Ǿ͆
i͆/ % ͆
i͆
ҿ ͆
i͆

 
͆ / # 
͆

È͆ 0
#
\͆ È͆ 2h  
͆

Ù Ù ͆
N͆'·Ϯ Ɠ͆
i\͆

È͆ 0
#
\͆ È͆ % F 
͆

2͆ ò ^'
ɼ͆ #͆ \͆ :͆ 0
 ͆ / 
90
T͆

#͆
͆
ҿ 
90
T͆

#͆ŏ
͆
ҿ 2͆ˋi͆

2h ͆
i͆
ҿ 0
 ͆

2 
͆
ҿ 0
0
 \͆ È͆ ɵ 
͆

È͆ 0
# 
\͆ È͆ : F 
͆

È͆ 
N͆'·Ϯ 0
 \͆

͆ Ȟᗮ ^{:͆ %͆} : ͆
i͆
ҿ 
90
˼T͆

Ɋ% Ƌ͆
i͆
ҿ 2͆
i͆

2 
͆ /

֍ೊஸᎯᅻ੎ᗮνȩͯνђᗮ ܺᒹྲྀዏࡐᒏŸ়ೊᅻ੎हዏ੎়ᗮ়੎୪ྲྀೊዏೊအྲྀᗮ૤းᅻᗮ஛အᑌŸအ૬Ɖहအྲྀዏᅻအแᗮበዏࡐዏ੎༌੎ྲྀዏበȪᗮ ߖ੎ᗮࡐበበᎯ༌੎ᗮዏఀࡐዏᗮ^
90
T͆हᅻ੎ࡐዏ੎በᗮࡐᗮྲྀ੎ᑌᗮแࡐ࣒੎แᗮ੎ࡐहఀᗮዏೊ༌੎ᗮೊዏᗮೊበᗮहࡐแแ੎়ûᗮࡐྲ়ྀᗮዏఀࡐዏᗮ

Inherited AGributes

Not relevant for control flow

Transla=on of Boolean Expressions

24

 ˙ -8˙°Ž˙  8#ZKZ˙= 8 ˙ हအྲ়ྀഇዏഇအྲྀࡐแᗮࡐྲ়ྀᗮᎯྲྀहအྲ়ྀഇዏഇအྲྀࡐแᗮෟᎯ༌Ⴜበᗮዏအᗮ အྲྀ੎ᗮအ૤ᗮዏᑌအᗮแࡐ࣒੎แበгᗮ ^(͆!
͆ഇ૤ᗮ^(͆ഇበᗮዏᅼᎯ੎ĉᗮ ࡐྲ়ྀᗮ^(͆
͆ഇ૤ᗮ^(͆ഇበᗮ૤ࡐแበ੎ȩᗮ

>F;VT*;6u N!56T)u GV1!Ou (͆ C͆ (c͆ l l ť(%͆ (c !
͆^/(4!
͆

(c 
͆^/ 
Ě0
T͆

(% 4 !
͆^/(4 !
͆

(% 
͆^/(͆
͆

(͆ Jҿ (c͆PPť(%͆ (c  !
͆^/
Ě0
T͆

(c 
͆^/(´
͆

(% ƕ!
͆^/(  !
͆

(% 4
͆
ҿ(͆
͆

( ¡ 
͆^/

(͆ C͆ ᗮ^(c͆ (c ͆!
͆
ҿ(͆
͆

(c 
͆^/(4!
͆

( 
͆/(c 4 
͆

(͆ C͆ c͆ 
Éɼ%͆ ( 
͆/

Ù Z ͆
N͆
ȩϮ c ͆͆
ÉIɼ ͆% ͆͆NK.‘.N͆ (4͆!
\͆

Z Z ͆
N͆K.‘.N͆ (͆´
\͆

(͆ C͆ #
ɼ (4 
͆^/
NK.‘.N͆ ( !
\͆

(͆ C͆ 
ɼ (͆
͆^/
N͆K.‘.«͆ (͆Þ
\͆

֏ഇஸᎯᅼ੎ᗮνȩͯϚюᗮ ֿ੎ྲྀ੎ᅼࡐዏഇྲྀஸᗮዏఀᅼ੎੎Ÿࡐ়়ᅼ੎በበᗮहအ়੎ᗮ૤အᅼᗮ࣒အအแ੎ࡐྲྀበᗮ

ݫఀ੎ᗮ૤အᎯᅼዏఀᗮႼᅼအ়Ꭿहዏഇအྲྀᗮഇྲྀᗮ֏ഇஸȪᗮ νȩͯϚĉᗮ(͆ C͆ c͆ 
Éɼ % ͆ഇበᗮዏᅼࡐྲྀበแࡐዏ੎়ᗮ়ഇᅼ੎हዏแᒹᗮ ഇྲྀዏအᗮ ࡐᗮ हအ༌Ⴜࡐᅼഇበအྲྀᗮ ዏఀᅼ੎੎Ÿࡐ়়ᅼ੎በበᗮ ഇྲྀበዏᅼᎯहዏഇအྲྀᗮ ᑌഇዏఀᗮ ෟᎯ༌Ⴜበᗮ ዏအᗮ ዏఀ੎ᗮ ࡐႼႼᅼအႼᅼഇࡐዏ੎ᗮ Ⴜแࡐह੎በȪᗮ ֏အᅼᗮഇྲྀበዏࡐྲྀह੎ĉᗮ^(͆အ૤ᗮዏఀ੎ᗮ૤အᅼ༌ᗮ^{ҿĨ͆ 0͆}ዏᅼࡐྲྀበแࡐዏ੎በᗮഇྲྀዏအѓᗮ

Ϯ &Ϯ Ϯ Ϯ K.‘.͆ (!
͆

K.‘.͆ (4
͆

ݫఀ੎ᗮᅼ੎༌ࡐഇྲྀഇྲྀஸᗮႼᅼအ়Ꭿहዏഇအྲྀበᗮ૤အᅼᗮ^(͆ࡐᅼ੎ᗮዏᅼࡐྲྀበแࡐዏ੎়ᗮࡐበᗮ૤အแแအᑌበгᗮ

؛ ܺᎯႼႼအበ੎ᗮ^(͆ഇበᗮအ૤ᗮዏఀ੎ᗮ૤အᅼ༌ᗮ^(c͆ , , Ϗ(% 4͆ ר૤ᗮ^(c͆ഇበᗮዏᅼᎯ੎ĉᗮዏఀ੎ྲྀᗮᑌ੎ᗮഇ༌༌੎়ഇࡐዏ੎แᒹᗮ คྲྀအᑌᗮዏఀࡐዏᗮ^(͆ഇዏበ੎แ૤ᗮഇበᗮዏᅼᎯ੎ĉᗮበအᗮ^{(c 4͆!
͆}ഇበᗮዏఀ੎ᗮበࡐ༌੎ᗮࡐበᗮ^(4͆!
͆ר૤ᗮ^(c͆ഇበᗮ૤ࡐแበ੎Ńᗮ ዏఀ੎ྲྀᗮ^(%͆༌Ꭿበዏᗮ࣒੎ᗮ੎ᐕࡐแᎯࡐዏ੎়ĉᗮበအᗮᑌ੎ᗮ༌ࡐค੎ᗮ^{(c 
͆}࣒੎ᗮዏఀ੎ᗮ้ࡐ࣒੎แᗮအ૤ᗮዏఀ੎ᗮ୪ᅼበዏᗮ ഇྲྀበዏᅼᎯहዏഇအྲྀᗮഇྲྀᗮዏఀ੎ᗮहအ়੎ᗮ૤အᅼᗮ^{(% ͆} ݫఀ੎ᗮዏᅼᎯ੎ᗮࡐྲ়ྀᗮ૤ࡐแበ੎ᗮ੎ᒏഇዏበᗮအ૤ᗮ(%͆ࡐᅼ੎ᗮዏఀ੎ᗮበࡐཌྷ੎ᗮ ࡐበᗮዏఀ੎ᗮዏᅼᎯ੎ᗮࡐྲ়ྀᗮ૤ࡐแበ੎ᗮ੎ᒏഇዏበᗮအ૤ᗮ(͆ᅼ੎በႼ੎हዏഇᐕ੎แᒹȪᗮ

Inherited AGributes

Example

if ( x < 100 || x > 200 && x != y ) x = 0;

is translated into:

if x < 100 goto L2 goto L3

L3: if x > 200 goto L4 goto L1

L4: if x != y goto L2 goto L1

L2: x=0 L1:

if x < 100 goto L2

ifFalse x > 200 goto L1 ifFalse x ! = y goto L1 L2: x=0

By removing several redundant jumps we can obtain the equivalent:

Transla=ng Short-Circuit Expressions Using Backpatching

E → E or M E | E and M E | not E

| ( E )

| id relop id | true

| false M → ε

M : marker nonterminal

Synthesized attributes:

E.truelist backpatch list for jumps on true E.falselist backpatch list for jumps on false

M.quad location of current three-address quad

Idea: avoid using inherited a"ributes by genera=ng par=al

code. Addresses for jumps will be inserted when known.

Backpatch Opera=ons with Lists

•  makelist(i) creates a new list containing three-address location i, returns a pointer to the list

•   merge(p

, p

) concatenates lists pointed to by p

and p

, returns a pointer to the concatenated list

•  backpatch(p, i) inserts i as the target label for each of

the statements in the list pointed to by p

28

Backpatching with Lists: Example

a < b or c < d and e < f

100: if a < b goto _ 101: goto _

102: if c < d goto _ 103: goto _

104: if e < f goto _ 105: goto _

backpatch

100: if a < b goto TRUE 101: goto 102

102: if c < d goto 104 103: goto FALSE

104: if e < f goto TRUE 105: goto FALSE

Backpatching with Lists: Transla=on Scheme

M → ε { M.quad := nextquad() } E → E₁ or M E₂

{ backpatch(E₁.falselist, M.quad);

E.truelist := merge(E₁.truelist, E₂.truelist);

E.falselist := E₂.falselist } E → E₁ and M E₂

{ backpatch(E₁.truelist, M.quad);

E.truelist := E₂.truelist;

E.falselist := merge(E₁.falselist, E₂.falselist); } E → not E₁ { E.truelist := E₁.falselist;

E.falselist := E₁.truelist } E → ( E₁ ) { E.truelist := E₁.truelist;

E.falselist := E₁.falselist }

Backpatching with Lists: Transla=on Scheme (cont’d)

E → id₁ relop id₂

{ E.truelist := makelist(nextquad());

E.falselist := makelist(nextquad() + 1);

emit(‘if’ id₁.place relop.op id₂.place ‘goto _’);

emit(‘goto _’) }

E → true { E.truelist := makelist(nextquad());

E.falselist := nil;

emit(‘goto _’) }

E → false { E.falselist := makelist(nextquad());

E.truelist := nil;

emit(‘goto _’) }

Flow-of-Control Statements and Backpatching: Grammar

S → if E then S

| if E then S else S | while E do S

| begin L end | A

L → L ; S | S

Synthesized attributes:

S.nextlist backpatch list for jumps to the next statement after S (or nil)

L.nextlist backpatch list for jumps to the next statement after L (or nil)

S₁ ; S₂ ; S₃ ; S₄ ; S₅ … backpatch(S₁.nextlist, 200) backpatch(S₂.nextlist, 300)

100: Code for S1 200: Code for S2 300: Code for S3

Jumps out of S₁

Flow-of-Control Statements and Backpatching

The grammar is modified adding suitble marking non-terminals S → A { S.nextlist := nil }

S → begin L end

{ S.nextlist := L.nextlist } S → if E then M S₁

{ backpatch(E.truelist, M.quad);

S.nextlist := merge(E.falselist, S₁.nextlist) } L → L₁ ; M S { backpatch(L₁.nextlist, M.quad);

L.nextlist := S.nextlist; } L → S { L.nextlist := S.nextlist; } M → ε { M.quad := nextquad() }

A → …

Non-compound statements, e.g. assignment, func&on call

Flow-of-Control Statements and Backpatching (cont’d)

S → if E then M₁ S₁ N else M₂ S₂

{ backpatch(E.truelist, M₁.quad);

backpatch(E.falselist, M₂.quad);

S.nextlist := merge(S₁.nextlist,

merge(N.nextlist, S₂.nextlist)) } S → while M₁ E do M₂ S₁

{ backpatch(S₁.nextlist, M₁.quad);

backpatch(E.truelist, M₂.quad);

S.nextlist := E.falselist;

emit(‘goto M₁.quad’) }

N → ε { N.nextlist := makelist(nextquad());

Summarizing…

•  Transla=on from source code to intermediate representa=on can be performed in a syntax- directed way during parsing

•  We considered transla=on of expressions and statements to three address code, with a

simplified handling of names (for example: no defini=ons)

•  More effec=ve transla=on of boolean expressions for flow control require inherited aGributes

•  They can be avoided using backpatching

34