Syntax Directed

Syntax-Directed
y Translation
&
Intermediate Code Generation
Dr. P K Singh TCS - 502 1

The Structure of our Compiler Revisited
Character Token Syntax-directed Java

stream Lexical analyzer
stream translator bytecode
Yacc specification
Lex specification JVM specification
with semantic rules

Syntax-Directed Translation
• Grammar symbols are associated with attributes to associate information
with the programming language constructs that they represent.
• Values
V l off these
th attributes
tt ib t are evaluated
l t db by the
th semantic
ti rules
l associated
i t d
with the production rules.
• Evaluation of these semantic rules:
– may generate intermediate codes
– may put information into the symbol table
– may perform type checking
– may issue error messages
– may perform some other activities
– in fact, they may perform almost any activities.
• An attribute mayy hold almost anyy thing.

g
– a string, a number, a memory location, a complex record.
Dr. P K Singh TCS - 502 slide3
Syntax-Directed Definitions and Translation
Schemes
• When we associate semantic rules with productions, we use two notations:
– Syntax-Directed Definitions
– Translation Schemes
• Syntax
Syntax-Directed
Directed Definitions:
– give high-level specifications for translations
– hide many implementation details such as order of evaluation of semantic actions.
– We associate a production rule with a set of semantic actions, and we do not say when they
will be evaluated.
• Translation Schemes:
– indicate the order of evaluation of semantic actions associated with a production rule.
– In other words, translation schemes give a little bit information about implementation details.

Example Attribute Grammar in Yacc
%token DIGIT
%%
L : E ‘\n’ { printf(“%d\n”, $1); }
;
E : E ‘+’ T { $$ = $1 + $3; }
| T { $$ = $1
$1; }
;
T : T ‘*’ F { $$ = $1 * $3; }
| F { $$ = $1; }
;
F : ‘(’ E ‘)’ { $$ = $2; }
| DIGIT { $$ = $1; }
;
%%

Syntax-Directed Definitions
• A syntax-directed
t di t d definition
d fi iti is
i a generalization
li ti off a context-free
t tf grammar iin
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.
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.
attribute But a semantic
rule may also have some side effects such as printing a value.

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.
• Of course
course, the order of these computations depends on the dependency
graph induced by the semantic rules.

Syntax-Directed Definition
• In a syntax-directed definition, each production A→ α is associated with a
set of semantic rules of the form:
b=f(c1,c2,…,cn) where f is a function,
and b can be one of the followings:
g
Î b is a synthesized attribute of A and c1,c2,…,cn are attributes of the
grammar symbols in the production ( A→α ).
OR
Î b is an inherited attribute one of the grammar symbols in α (on the
right side of the production), and c1,c2,…,cn are attributes of the
grammar symbols in the production ( A→ α ).

Attribute Grammar
• So, a semantic rule b=f(c1,c2,…,cn) indicates that the attribute b depends on
attributes c1,c2,…,cn.
• In a syntax-directed definition, a semantic rule may just evaluate a value
of an attribute or it may have some side effects such as printing values.
• An attribute grammar is a syntax-directed definition in which the functions

in the semantic rules cannot have side effects (they can only evaluate values
of attributes).

Syntax-Directed Definition -- Example
Production Semantic Rules
L → E return print(E.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
F → digit
g F.val = digit.lexval
g
• Symbols E, T, and F are associated with a synthesized attribute val.

• The
e to
token
e ddigit
g t has
as a sy
synthesized
t es ed att bute lexval
attribute e a ((itt iss assu
assumed
ed tthat
at itt iss
evaluated by the lexical analyzer).

Annotated Parse Tree -- Example
Input: 5+3*4 L
E.val=17 return
E.val=5 + T.val=12
T val=5
T.val=5 T.val=3
T val=3 * F val=4
F.val=4
F.val=5 F.val=3 digit.lexval=4
digit.lexval=5 digit.lexval=3

Dependency Graph
Input: 5+3*4 L
E.val=17
E.val=5 T.val=12
T val=5
T.val=5 T.val=3
T val=3 F.val=4
F val=4
F.val=5 F.val=3 digit.lexval=4
digit.lexval=5 digit.lexval=3

Intermediate Code Generation
• Facilitates retargeting: enables attaching a back end for

the new machine to an existing front end
Target
Intermediate
Front end Back end machine
code
code
• Enables
E bl machine-independent
hi i d d t code
d optimization
ti i ti

Intermediate Representations
• Graphical representations (e.g. AST)
• Postfix notation: operations
p on values stored on operand
p stack (similar
( to
JVM bytecode)
• Three-address code: (e.g. triples and quads)
x := y op
pz
• Two-address code:
x := op y
which is the same as x := x op y

Implementing Syntax Trees
• Each node can be represented by a record with several

fields
• Example: node representing an operator used in an
expression:
– One field indicates the operator and others point to records
for nodes representing operands
– The operator is referred to as the “label” of the node
• If being used for translation, records can have
additional fields
f ffor attributes

Syntax Trees for Expressions
• Functions will create nodes for the syntax tree

– mknode (op left, right) – creates an operator node
(op, left
with label op and pointers left and right which point to
operand nodes
– mkleaf(id, entry) – creates an identifier node with label
id and a pointer to the appropriate symbol table entry
Mkleaf(num val) – creates a number node with label num
– Mkleaf(num,
and value val
• Each function returns pointer to created node

Syntax-Directed Translation of Abstract
y
Syntax Trees
Production Semantic Rule

S → id := E S.nptr := mknode(‘:=’, mkleaf(id, id.entry), E.nptr)
E → E1 + E2 E.nptr := mknode(‘+’, E1.nptr, E2.nptr)
E → E1 * E2 E.nptr
p := mknode((‘*’,, E1.nptr,
p , E2.nptr)
p )
E → - E1 E.nptr := mknode(‘uminus’, E1.nptr)
E → ( E1 ) E.nptr
pt := E1.nptr
pt
E → id E.nptr := mkleaf(id, id.entry)

Example: a - 4 + c
p1 := mkleaf(id, pa);
P2 := mkleaf(num, 4); - id
p3 := mknode('-', p1, p2);
to entry for c
p4 := mkleaf(id
mkleaf(id, pc);
p5 := mknode('+', p3, p4); id num 4
to entry for a

Directed Acyclic Graphs
• Called a dag for short

• Convenient for representing expressions
• As with syntax trees:
– Everyy subexpression
p will be represented
p byy a node
– Interior nodes represent operators, children represent
operands
• U
Unlike
lik syntax
t ttrees, nodes
d may h have more than
th one
parent
• Can be created automatically (discussed in textbook)

Example: a + a * (b – c) + (b – c) * d
+ *
* d
a -
b c

Abstract Syntax Trees
E.nptr
a * (b + c) E nptr
E.nptr * E.nptr
E nptr
a ( E.nptr )
E.nptr + E.nptr
b c
*
Pro: easy restructuring of code
and/or expressions for a +
intermediate code optimization
Cons: memoryy intensive b c
Dr. P K Singh
21
TCS - 502
Abstract Syntax Trees versus DAGs
a := b * -c + b * -c
:
:= :
:=
a + a +
* * *
b uminus b uminus b uminus
c c c
Tree DAG

Postfix Notation
a := b * -c + b * -c
a b c uminus * b c uminus * + assign Bytecode (for example)

iload 2 // push b
Postfix notation represents iload 3 // push c
ineg // uminus
operations
ti on a stack
t k imul // *
iload 2 // push b
Pro: easyy to ggenerate iload 3 // push c
i
ineg // uminus
i
Cons: stack operations are more imul // *
difficult to optimize iadd // +
istore 1 // store a

Three-Address Code
a := b * -c + b * -c
t1 := - c t1 := - c
t2 := b * t1 t2 := b * t1
t3 := - c t5 := t2 + t2
t4 := b * t3 a := t5
t5 :=
: t2 + t4
a := t5
Linearized representation
p Linearized representation
p
of a syntax tree of a syntax DAG

Three-Address Statements
• Assignment statements: x := y op z, x := op y
• Indexed
I d t x := y[i],
d assignments:
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
• F
Function ll param x… call p, n
ti calls:
return y

Syntax-Directed Translation into Three-
Address Code
Productions Synthesized
y attributes:
S → id := E S.code three-address code for S
| while E do S S.begin label to start of S or nil
E→E+E S after
S.after label to end of S or nil
|E*E E.code three-address code for E
|-E E.place a name holding the value of E
|(E)
| id
| num gen(E.place ‘:=’ E1.place ‘+’ E2.place)
Code generation
t3 := t1 + t2

Address Code (cont’d)
Productions Semantic rules
S → id := E S.code := E.code || gen(id.place ‘:=’ E.place); S.begin := S.after := nil
E → E1 + E2 E.place := newtemp();
E.code := E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘+’ E2.place)
E → E1 * E2 E.place
place := newtemp();
E.code := E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘*’ E2.place)
E → - E1 E.place := newtemp();
E.code
code := E1.code
code || gen(E.place
place ‘:=’ uminus E1.place)
:= ‘uminus’ place)
E → ( E1 ) E.place := E1.place
E.code := E1.code
E → id E.place := id.name
E.code := ‘’
E → num E.place
place := newtemp();
E.code := gen(E.place ‘:=’ num.value)

Address Code (cont’d)
Production
S → while E do S1
Semantic rule
S begin: E.code
S.begin: E code
S.begin := newlabel()
if E.place = 0 goto S.after
S.after := newlabel()
S.code := gen(S.begin ‘:’) || S.code
E.code || goto S.begin
gen(‘if’ E.place ‘=‘ ‘0’ ‘goto’ S.after) || …
S.after:
S1.code ||
gen(‘goto’
(‘ t ’ S.begin)
S b i ) ||
gen(S.after ‘:’)

Example
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:

Implementation 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 optimization

Dr. P K Singh
Cons: lots of temporariesTCS - 502 30
Implementation of Three-Address Statements:
p
Triples
# Op Arg1 Arg2
(0) uminus
i c
(1) * b (0)
((2)) uminus c
(3) * b (2)
(4) + (1) (3)
(5) := a (4)
Triples
Pro: temporaries are implicit
Cons: difficult to rearrange code

Implementation of Three-Address Stmts:
p
Indirect Triples
# Stmt # Op Arg1 Arg2
(0) (14) (14) uminus c
(1) (15) (15) * b (14)
(2) (16) (16) uminus c
(3) (17) (17) * b (16)
(4) (18) (18) + (15) (17)
(5) (19) (19) := a (18)
Program Triple container
Pro: temporaries are implicit & easier to rearrange code

Names and Scopes
• The three-address code generated by the syntax-

directed definitions shown on the previous slides is
somewhat simplistic, because 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
declarations as well as local declarations in
procedures, blocks, and structs to resolve names

Symbol Tables for Scoping
struct S We need a symbol table
{ int a;
for the fields of struct S
int b;
} s;
Need symbol table
void swap(int& a, int& b) for global variables
{ int
i t t;
t and functions
t = a;
a = b;
b = t;
} Need symbol table for arguments
and locals for each function
void somefunc()
{ … Check: s is global and has fields a and b
swap(s.a, s.b);
Using symbol tables we can generate
…
} code to access s and its fields
Dr. P K Singh TCS - 502
34
Offset and Width for Runtime Allocation
struct S
{ int a; The fields a and b of struct S
int b; are located at offsets
ff 0 and 4
} s; from the start of S
void swap(int& a, int& b) a (0)
{ int
i t t;
t The width of S is 8 b (4)
t = a;
a = b; Subroutine frame holds
b = t; arguments a and b and
} Subroutine
local t at offsets 0, 4, and 8 frame
void somefunc() fp[0] a
fp[0]= (0)
{ … fp[4]= b (4)
swap(s.a, s.b);
The width of the frame is 12 fp[8]= t (8)
…
}
Example
globals
struct S prev=nil [4] Trec S
{ int a;
s (0)
int b; nil [8]
prev=nil
prev
} s; swap
a (0)
foo
void swap(int& a, int& b) b (4)
{ int
i t t;
t Tfun swap
t = a; Tref
a = b; prev [12]
b = t; Tint
a (0)
}
b (4)
void foo() t ((8))
Table nodes
{ …
swap(s.a, s.b); Tfun foo type nodes
… (offset)
} prev [0] [width]
Hierarchical Symbol Table Operations
• mktable(previous) returns a pointer to a new table that is
linked to a p
previous table in the outer scope
p
• enter(table, name, type, offset) creates a new entry in table
• addwidth(table, width) accumulates the total width of all
entries in table
• enterproc(table, name, newtable) creates a new entry in table
for procedure with local scope newtable
• lookup(table, name) returns a pointer to the entry in the table
fo name by
for b following
follo ing linked tables

Syntax-Directed Translation of Declarations in
p
Scope
Productions Productions (cont’d)
P→D;S E→E+E
D→D;D |E*E
| id : T |-E Synthesized attributes:
| proc id ; D ; S |(E) T.type pointer to type
T → integer | id T.width storage width of type (bytes)
| real |E^ E.place name of temp holding value of E
| array [ num ] of T |&E
|^T | E . id
Global data to implement scoping:
| record D end A→A,E
tblptr stack of pointers to tables
S→S;S |E
offset stack of offset values
| id ::= E
| call id ( A )

p (cont’d)
Scope
P→ { t := mktable(nil); push(t, tblptr); push(0, offset) }

D;S
D → id : T
{ enter(top(tblptr), id.name, T.type, top(offset));
top(offset)
( ff ) := top(offset)
( ff ) + T.width
T id h }
D → proc id ;
{ t := mktable(top(tblptr)); push(t, tblptr); push(0, offset) }
D1 ; S
{ t := top(tblptr); addwidth(t, top(offset));
pop(tblptr); pop(offset);
enterproc(top(tblptr),
t (t (tbl t ) id.name,
id name t) }
D → D1 ; D2

p (cont’d)
Scope
T → integer { T.type := ‘integer’; T.width := 4 }

T → real { T.type
T type := ‘real’;
real ; T.width
T width := 8 }
T → array [ num ] of T1
{ T.type := array(num.val, T1.type);
T.width := num.val * T1.width }
T → ^ T1
{ T.type
yp := ppointer(T
( 1.type);
yp ); T.width := 4 }
T → record
{ t := mktable(nil); push(t, tblptr); push(0, offset) }
D end
{ T.type := record(top(tblptr)); T.width := top(offset);
addwidth(top(tblptr), top(offset)); pop(tblptr); pop(offset) }

Example
globals
s: record prev=nil [4] Trec
a: integer; s (0)
b: integer; prev=nil [8]
swap
end; a (0)
foo
b (4)
proc swap;
Tfun swap
a: ^integer; Tptr
b: ^integer;
pprev [[12]]
t: integer; Tint
t := a^; a (0)
a^ := b^; b (4)
b^ :
b := t; t (8)
Table nodes
proc foo; Tfun foo type nodes
p
call swap(&s.a, &s.b); (offset)
prev [0] [width]
Syntax-Directed Translation of Statements in
p
Scope
Globals
S→S;S s (0)
S → id := E x (8)
{ p := lookup(top(tblptr), id.name); y (12)
if p = nil then
error()
Subroutine
else if p.level = 0 then // global variable frame
emit(id.place ‘:=’ E.place) fp[0]= a (0)
else // local variable in subroutine frame fp[4]= b (4)
emit(fp[p.offset]
( p[p ] ‘:=’ E.place)
p )} f [8] t
fp[8]= (8)
…

Syntax-Directed Translation of Expressions in Scope
E → E1 + E2 { E.place
place := newtemp();
emit(E.place ‘:=’ E1.place ‘+’ E2.place) }
E → E1 * E2 { E.place
place := newtemp();
emit(E.place ‘:=’ E1.place ‘*’ E2.place) }
E → - E1 { E.place
place := newtemp();
emit(E.place ‘:=’ ‘uminus’ E1.place) }
E → ( E1 ) { E.place
place := E1.place
place }
E → id { p := lookup(top(tblptr), id.name);
if p = nil then error()
else if p.level = 0 then // global variable
E.place := id.place
else // local variable in frame
E.place := fp[p.offset] }
Syntax-Directed Translation of Expressions in Scope (cont’d)
E → E1 ^ { E.place := newtemp();
emit(E.place ‘:=’ ‘*’ E1.place) }
E → & E1 { E.place := newtemp();

emit(E.place ‘:=’ ‘&’ E1.place) }
E → id1 . id2 { p := lookup

l k (top(tblptr
bl ),
) id1.name); )
if p = nil or p.type != Trec then error()
else
q := lookup(p.type.table,
type table id2.name);
name);
if q = nil then error()
else if p.level = 0 then // global variable
E.place place[q.offset]
place := id1.place[ offset]
else // local variable in frame
E.place := fp[p.offset+q.offset] }

Advanced Intermediate Code Generation
Techniques
• Reusing temporary names
• Addressingg arrayy elements
• Translating logical and relational expressions
• Translating short-circuit Boolean expressions and flow-of-control
statements with backpatching lists
• Translating procedure calls
45
Reusing Temporary Names
generate
E1 + E2 Evaluate E1 into t1
Evaluate E2 into t2
t3 := t1 + t2
If t1 no longer used, can reuse t1

instead of using new temp t3
Modify newtemp() to use a “stack”:

Keep a counter c, initialized to 0
newtemp() increments c and returns temporary $c
Decrement counter on each use of a $i in a three-address statement
46
Reusing Temporary Names (cont’d)
x := a * b + c * d - e * f
Statement c
0
$0 := a * b 1
$1 := c * d 2
$0 := $0 + $1 1
$1 := e * f 2
$0 := $0 - $1 1
x := $0 0
47
Addressing Array Elements: One-Dimensional
y
Arrays
A : array [10..20] of integer;
… := A[i] = baseA + (i - low) * w

=i*w+c
where c = baseA - low * w
with low = 10; w = 4
t1 := c // c = baseA - 10 * 4
t2 := i * 4
t3 := t1[t2]
… := t3
48
Addressing Array Elements: Multi-Dimensional Arrays
A : array [1..2,1..3] of integer;
low1 = 1, low2 = 1, n1 = 2, n2 = 3, w = 4
baseA A[1,1]
baseA A[1,1]
A[1,2] A[2,1]
A[1,3] A[1,2]
A[2,1] A[2,2]
A[2,2] A[1,3]
A[2 3]
A[2,3] A[2 3]
A[2,3]
Row-major Column-major
49
Addressing Array Elements: Multi-Dimensional
y
Arrays
A : array [1..2,1..3] of integer; (Row-major)
… := A[i,j] = baseA + ((i1 - low1) * n2 + i2 - low2) * w

= ((i1 * n2) + i2) * w + c
where c = baseA - ((low1 * n2) + low2) * w
t1
1 := i * 3 with low1 = 1; low2 = 1; n2 = 3; w = 4
t1 := t1 + j
t2 := c // c = baseA - (1 * 3 + 1) * 4
t33 := t11 * 4
t4 := t2[t3]
… := t4
50
Addressing Array Elements: Grammar
S → L := E
Synthesized attributes:
E→E+E E.place name of temp holding value of E
|(E) Elist.array array name
|L Elist.place name of temp holding index value
L → Elist ] Elist.ndim number of array dimensions
| id L.place lvalue (=name of temp)
L.offset index into array (=name of temp)
Elist → Elist , E null indicates non-array simple id
| id [ E
51
Addressing Array Elements
S → L := E { if L.offset = null then
emit(L.place ‘:=’ E.place)
else
emit(L.place[L.offset] ‘:=’ E.place) }
E → E1 + E2 { E.place := newtemp();
emit(E.place
it(E l ‘:=’
‘ ’ E1.place
l ‘+’ E2.place)
l )}
E → ( E1 ) { E.place := E1.place }
E→L { if L.offset = null then
E.place := L.place
else
E.place ::= newtemp();
emit(E.place ‘:=’ L.place[L.offset] }
52
Addressing Array Elements
L → Elist ] { L.place
L place := newtemp();
L.offset := newtemp();
emit(L.place ‘:=’ c(Elist.array);
emit(L.offset ‘:=’ Elist.place ‘*’ width(Elist.array)) }
L → id { L.place := id.place;
L.offset := null }
Elist → Elist1 , E
{ t := newtemp(); m := Elist1.ndim + 1;
emit(t ‘:=’
:= Elist1.place
place ‘*’
* limit(Elist1.array,
array m));
emit(t ‘:=’ t ‘+’ E.place);
Elist.array := Elist1.array; Elist.place := t;
Elist.ndim := m }
Elist → id [ E { Elist.array := id.place; Elist.place := E.place;
Elist.ndim := 1 }
53
Translating Assignments
p := lookup(id.name);
if p != NULL then
S Æ id := E emit(p ':=' E.place)
else
error
E.place := newtemp;
E Æ E1 + E2
emit(E.place ':=' E1.place '+' E2.place)
E.place := newtemp;
E Æ E1 * E2
emit(E.place ':=' E1.place '*' E2.place)
E.place
E place :=
: newtemp;
E Æ -E1
emit(E.place ':=' 'uminus' E1.place)
E Æ (E1) E.place := E1.place

p := lookup(id.name);
if p != NULL then
E Æ id E.place := p
else
error
P K Singh M M M Engg. College, Gorakhpur ICG - 54

Type Conversions
• There are multiple types (e.g. integer, real) for variables and constants
– Compiler may need to reject certain mixed-type operations
– At times, a compiler needs to general type conversion
instructions
• An attribute E.type holds the type of an expression
Semantic Action: E Æ E1 + E2
E.place := newtemp;
if E1.type = integer and E2.type = integer then
begin
emit(E.place ':=' E1.place 'int+' E2.place);
E type := integer
E.type
end
else if E1.type = real and E2.type = real then
…
else if E1.type = integer and E2.type = real then
begin
g
u := newtemp;
emit(u ':=' 'inttoreal' E1.place);
emit(E.place ':=' u 'real+' E2.place);
E.type := real
end
else if E1.type = real and E2.type = integer then
…
else E.type := type_error;
Example: x := y + i * j
• Without Type conversion
t1 := i * j
t2 := y + t1
x := t2
• With Type conversion

o In this example, x and y have type real
o i and j have type integer
o The
Th intermediate
i t di t code
d is
i shown
h below:
b l
t1 := i int* j
t3 := inttoreal t1
t2
2 := y real+
l t33
x := t2

Boolean Expressions
• Boolean expressions compute logical values
• Often used with flow-of-control statements
• Methods of translating boolean expression:
– Numerical methods:
• True is represented as 1 and false is represented as 0
• Nonzero values are considered true and zero values are considered false
– Flow-of-control methods:
• R
Representt the
th value
l off a boolean
b l by
b the
th position
iti reached
h d in
i a program
• Often not necessary to evaluate entire expression

Numerical Representation
• Expressions evaluated left to right using 1 to denote true and 0 to donate false
• Example: a or b and not c
t1 := not c
t2 := b and t1
t3 := a or t2
• Another example: a < b
100: if a < b goto 103
101: t : = 0
102: goto 104
103: t : = 1
104: …

Numerical Representation
E.place
E place :=
: newtemp;
E Æ E1 or E2 emit(E.place ':=' E1.place 'or'
E2.place)
.p ace :
E.place := newtemp;
e te p;
E Æ E1 and E2 emit(E.place ':=' E1.place 'and'
E2.place)
E.place := newtemp;
E Æ not E1
emit(E.place ':=' 'not' E1.place)
E Æ (E1) E.place := E1.place;
E.place := newtemp;
emit('if' id1.place relop.op
id2.place 'goto' nextstat+3);
E Æ id1 relop id2
emit(E.place ':=' '0');
emit('goto' nextstat+2);
emit(E.place ':=' '1');
E.place := newtemp;
E Æ true
emit(E.place
( p ':=' '1')
)
E.place := newtemp;
E Æ false
emit(E.place ':=' '0')
Example: a<b or c<d and e<f
100: if a < b goto 103
101: t1 := 0
102: goto 104
103: t1 := 1
104: if c < d goto 107
105: t2 := 0
106: goto 108
107: t2 := 1
108: if e < f goto 111
109: t3 := 0
110
110: goto
t 112
111: t3:= 1
112: t4 := t2 and t3
113: t5 := t1 or t4

Flow-of-Control
Fl Control
Flow C t l Statements
St t t
• S Æ if E then S1
• S Æ if E then S1 else S2
• S Æ while E do S1
• The function newlabel will return a new symbolic label each time it
is called
• Each boolean expression will have two new attributes:
– E.true is the label to which control flows if E is true
– E.false is the label to which control flows if E is false
• Attribute S.next of a statement S:
– IInherited
h i d attribute
ib whose h value
l isi the
h label
l b l attached
h d to the
h first
fi instruction
i i to
be executed after the code for S
– Used to avoid jumps to jumps

S Æ if E then S1
E.true := newlabel;
E.false := S.next;
S1.next := S.next;
S code :=
S.code : E.code
E code || gen(E
gen(E.true
true ':')
: ) || S1
S1.code
code

S Æ if E then S1 else S2
E.true
E t := newlabel;
l b l
E.false := newlabel;
S1.next := S.next;
S2.next := S.next;
S.code := E.code || gen(E.true ':') || S1.code ||
gen('goto'
g g S.next) || g
gen(E.false ':') ||
S2.code
S Æ while E do S1
S.begin := newlabel;
E.true := newlabel;
E.false := S.next;
S1.next := S.begin;
S.code := gen(S.begin ':') || E.code || gen(E.true
':') || S1.code || gen('goto' S.begin)

Boolean Expressions
E1.true := E.true;
E1.false := newlabel;
E Æ E1 or E2 E2.true
true := E
E.true;
true;
E2.false := E.false;
E.code := E1.code || gen(E1.false ':') || E2.code
E1.true := newlabel;
E Æ E1 and E2 E2.true := E.true;
E.code := E1.code || gen(E1.true ':') || E2.code

Boolean Expressions
E Æ not E1 E1.true := E.false;
E1.false := E.true;
E code := E1
E.code E1.code
code
E Æ (E1) E1.true := E.true;
E.code := E1.code
E Æ id1 relop id2 E.code := gen('if‘ id.place relop.op id2.place
'goto‘ E.true) || gen('goto' E.false)
E Æ true E.code := gen('goto' E.true)
E Æ false E.code :=
: gen(
gen('goto'
goto E.false)

Examples:
a<b or c<d and e<f
if a < b goto Ltrue
goto L1
L1: if c < d goto L2
goto
g Lfalse
L2: if e < f goto Ltrue
goto Lfalse
while a < b do 1
L1: if a < b goto L2
2
if c < d then goto Lnext
x := y + z L2: if c < d goto L3
else goto L4
x := y - z L3: t1 := y + z
x:= t1
goto L1
L4: t2 := y – z
X := t2
goto L1
g
Lnext:
Mixed-Mode Expressions
• Boolean expressions often have arithmetic subexpressions, e.g. (a + b) < c
• If false has the value 0 and true has the value 1
– arithmetic expressions
p can have boolean subexpressions
p
– Example: (a < b) + (b < a) has value 0 if a and b are equal
and 1 otherwise
• Some operators may require both operands to be boolean
• Other operators may take both types of arguments, including mixed arguments

Revisit: E Æ E1 + E2
E.type := arith;
if E1.type = arith and E2.type = arith then
begin
/* normal arithmetic add */
E.place := newtemp;
E.code := E1.code || E2.code ||
gen(E.place ':=' E1.place '+' E2.place)
end
else if E1.type := arith and E2.type = bool then
begin
E2 place :
E2.place := newtemp;
E2.true := newlabel;
E2.flase := newlabel;
E.code := E1.code || E2.code ||
gen(E2.true ':' E.place ':=' E1.place + 1) ||
gen('goto' nextstat+1) ||
gen(E2.false ':' E.place ':=' E1.place)
else if …

Translating Logical and Relational Expressions
t1 := not c
a or b and not c t2 := b and t1
t3 := a or t2
if a < b goto L1
a<b t1 := 0
goto L2
L1: t1 := 1
L2:
70
Backpatching
E → E or M E
Synthesized attributes:
| E and M E E d
E.code three-address
h dd code
d
| not E E.truelist backpatch list for jumps on true
|(E) E.falselist backpatch list for jumps on false
| id relop
l id M quad
M.quad location of current three-address
three address quad
| true
| false
M→ε
71
Backpatch Operations with Lists
• makelist(i) creates a new list containing three-address

location i, returns a pointer to the list
• merge(p1, p2) concatenates lists pointed to by p1 and
p2, returns a pointer to the concatenates list
• backpatch(p, i) inserts i as the target label for each of
the statements in the list pointed to by p
72
Backpatching with Lists: Example
100: if a < b goto _
101: goto _
102: if c < d goto
g _
a < b or c < d and e < f
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
73
Backpatching with Lists: Translation Scheme
M→ε { M.quad := nextquad() }
E → E1 or M E2
{ backpatch(E1.falselist,
falselist M.quad);
M quad);
E.truelist := merge(E1.truelist, E2.truelist);
E.falselist := E2.falselist }
E → E1 and M E2
{ backpatch(E1.truelist, M.quad);
E.truelist := E2.truelist;;
E.falselist := merge(E1.falselist, E2.falselist); }
E → not E1 { E.truelist := E1.falselist;
E falselist := E1.truelist
E.falselist truelist }
E → ( E1 ) { E.truelist := E1.truelist;
E.falselist := E1.falselist }
74
Backpatching with Lists: Translation Scheme
(cont’d)
E → id1 relop id2
{ E.truelist := makelist(nextquad());
E f l li t := makelist(nextquad()
E.falselist k li ( d() + 1);
1)
emit(‘if’ id1.place relop.op id2.place ‘goto _’);
emit(‘goto _ _’) }
E → true { E.truelist := makelist(nextquad());
E.falselist := nil;
emit(‘goto
emit( goto _’)) }
E → false { E.falselist := makelist(nextquad());
E.truelist := nil;
emit(‘goto
it(‘ t _’) ’) }
75
Flow-of-Control Statements and Backpatching:
Grammar
S → if E then S
| if E then
th S else
l S Synthesized attributes:
| while E do S S.nextlist backpatch list for jumps to the
| begin
g L end next statement after S (or nil)
|A L.nextlist backpatch list for jumps to the
next statement after L (or nil)
L→L;S
|S
Jumps
S1 ; S2 ; S3 ; S4 ; S4 … 100: Code for S1 out of S1 backpatch(S1.nextlist, 200)

200: Code for S2
300: Code for S3
b k
backpatch(S
h(S2.nextlist,
li 300)
400: Code for S4 backpatch(S3.nextlist, 400)
500: Code for S5 backpatch(S4.nextlist, 500)
76
Flow-of-Control Statements and Backpatching
S→A { S.nextlist := nil }

S → begin L end
{ S.nextlist := L.nextlist }
S → if E then M S1
{ backpatch(E.truelist, M.quad);
S.nextlist := merge(E.falselist, S1.nextlist) }
L → L1 ; M S { backpatch(L1.nextlist, M.quad);
L nextlist := S.nextlist;
L.nextlist S nextlist; }
L→S { L.nextlist := S.nextlist; }
M→ε { M.quad := nextquad() }
77
Flow-of-Control Statements and Backpatching
(cont’d)
S → if E then M1 S1 N else M2 S2
{ backpatch(E.truelist, M1.quad);
backpatch(E.falselist, M2.quad);
S.nextlist := merge(S1.nextlist,
merge(N.nextlist, S2.nextlist)) }
S → while M1 E do M2 S1
{ backpatch(S1,nextlist, M1.quad);
backpatch(E truelist M2.quad);
backpatch(E.truelist, quad);
S.nextlist := E.falselist;
emit(‘goto _’) }
N→ε { N.nextlist := makelist(nextquad());
emit(‘goto _’) }
78
Translating Procedure Calls
S → call id ( Elist )
Elist → Elist , E
|E
foo(a+1, b, 7) t1 := a + 1
t2 := 7
param t1
param b
param t2
call foo 3
79
Translating Procedure Calls
S → call id ( Elist ) { for each item p on queue do

emit(‘param’ p);
emit(‘call’ id.place |queue|) }
Elist → Elist , E { append E.place to the end of queue }
Elist → E { initialize queue to contain only E.place }
80

Syntax Directed

Uploaded by

Copyright:

Available Formats

Syntax Directed

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Syntax Directed

Uploaded by

Copyright:

Available Formats

Syntax-Directed

Dr. P K Singh TCS - 502 1

Character Token Syntax-directed Java

Dr. P K Singh TCS - 502 2

• An attribute mayy hold almost anyy thing.

Dr. P K Singh TCS - 502 slide4

Dr. P K Singh TCS - 502 5

Dr. P K Singh TCS - 502 slide6

Dr. P K Singh TCS - 502 slide7

Dr. P K Singh TCS - 502 slide8

• An attribute grammar is a syntax-directed definition in which the functions

Dr. P K Singh TCS - 502 slide9

• Symbols E, T, and F are associated with a synthesized attribute val.

Dr. P K Singh TCS - 502 slide10

F.val=5 F.val=3 digit.lexval=4

Dr. P K Singh TCS - 502 11

F.val=5 F.val=3 digit.lexval=4

Dr. P K Singh TCS - 502 12

• Facilitates retargeting: enables attaching a back end for

Dr. P K Singh TCS - 502 slide13

Dr. P K Singh TCS - 502 slide14

• Each node can be represented by a record with several

Dr. P K Singh TCS - 502 slide15

• Functions will create nodes for the syntax tree

Dr. P K Singh TCS - 502 slide16

Production Semantic Rule

Dr. P K Singh TCS - 502 17

Dr. P K Singh TCS - 502 18

• Called a dag for short

Dr. P K Singh TCS - 502 slide19

Dr. P K Singh TCS - 502 slide20

b uminus b uminus b uminus

Dr. P K Singh TCS - 502 22

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

Dr. P K Singh TCS - 502 23

Dr. P K Singh TCS - 502 24

Dr. P K Singh TCS - 502 slide25

Dr. P K Singh TCS - 502 26

Dr. P K Singh TCS - 502 27

Dr. P K Singh TCS - 502 28

Dr. P K Singh TCS - 502 29

# Op Arg1 Arg2 Res

Pro: easy to rearrange code for global optimization

Dr. P K Singh TCS - 502 31

Program Triple container

Pro: temporaries are implicit & easier to rearrange code

Dr. P K Singh TCS - 502 32

• The three-address code generated by the syntax-

Dr. P K Singh TCS - 502 slide33

Dr. P K Singh TCS - 502 slide37

Dr. P K Singh TCS - 502 38

P→ { t := mktable(nil); push(t, tblptr); push(0, offset) }

Dr. P K Singh TCS - 502 39

T → integer { T.type := ‘integer’; T.width := 4 }

Dr. P K Singh TCS - 502 40

Dr. P K Singh TCS - 502 42

E → & E1 { E.place := newtemp();

E → id1 . id2 { p := lookup

Dr. P K Singh TCS - 502 44

If t1 no longer used, can reuse t1