lec10_bak
CS 314 Principles of Programming Languages
Prof. Zheng Zhang
Rutgers University
Lecture 10: Syntax Directed Translation
October 5, 2018
Class Information
2
• Homework 3 is being graded.
• Homework 4 will be released by the end of today.
• Project 1 will be released after hw4 is due (Tuesday 10/9/2018).
Review: Recursive Descent Parsing
3
• Each non-terminal has an associated parsing procedure that can
recognize any sequence of tokens generated by that non-terminal
• There is a main routine to initialize all globals (e.g:the token variable
in previous code example) and call the start symbol. On return, check
whether token == EOF, and whether errors occurred.
• Within a parsing procedure, both non-terminals and terminals are
matched:
➡ Non-terminal A: call procedure for A
➡ Token t: compare t with current the first of the remaining tokens;
If matched, consume input, otherwise, ERROR
• Parsing procedure may contain code that performs some useful
“computations” (syntax directed translation)
Recursive descent parser for LL(1)
Rule 3
< digit > ::= 0 | 1 | 2 | 3 | … | 9
Rule 2:
< expr > ::=
Rule 1:
< expr > ::= + < expr > < expr >
Example
4
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
void expr( ) {
switch token {
case +: token := next_token( );
expr( ) ;
expr( );
break;
case 0..9:
digit( ); break;
…
} // End switch case
} //End expr()
void digit( ): // return value of constant
switch token {
case 1: token := next_token( ); break;
case 2: token := next_token( ); break;
…
} // End switch case
}// End digit( )
Example: the Original Parser
5
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error
What happens when you parse expression
“ + 2 + 1 2”
call
call
call
2
call
call
+
call
1
call
call
2
Example: the Original Parser
6
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error
What happens when you parse expression
“ + 2 + 1 2”
call
call
call
2
call
call
+
call
1
call
call
2
Example: the Original Parser
7
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error
What happens when you parse expression
“ + 2 + 1 2”
call
call
call
2
call
call
+
call
1
call
call
2
Example: the Original Parser
8
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error
What happens when you parse expression
“ + 2 + 1 2”
call
call
call
2
call
call
+
call
1
call
call
call
call
2
Example: the Original Parser
9
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > rule 1 rule 2 error
< digit > error rule 3 error
What happens when you parse expression
“ + 2 + 1 2”
call
call
call
2
call
call
+
call
1
call
call
call
call
2
Review: Recursive Descent Parsing
10
• Each non-terminal has an associated parsing procedure that can
recognize any sequence of tokens generated by that non-terminal
• There is a main routine to initialize all globals (e.g:the token variable
in previous code example) and call the start symbol. On return, check
whether token == EOF, and whether errors occurred.
• Within a parsing procedure, both non-terminals and terminals are
matched:
➡ Non-terminal A: call procedure for A
➡ Token t: compare t with current the first of the remaining tokens;
If matched, consume input, otherwise, ERROR
• Parsing procedure may contain code that performs some useful
“computations” (syntax directed translation)
Recursive descent parser for LL(1)
11
– Interpreter
– Code generator
– Type checker
– Performance estimator
Syntax Directed Translation
Examples:
Use hand-written recursive descent LL(1) parser
Example: Interpreter
12
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Originalvoid expr( ) {
switch token {
case +: token := next_token( );
expr( ) ;
expr( );
break;
case 0..9:
digit( ); break;
…
} // End switch case
} //End expr()
void digit( ): // return value of constant
switch token {
case 1: token := next_token( ); break;
case 2: token := next_token( ); break;
…
} // End switch case
}// End digit( )
Example: Interpreter
13
int expr( ) {
int val1, val2; // two values
switch token {
case +: token := next_token( );
val1 = expr( ) ;
val2 = expr( );
return val1 + val2;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
int digit( ): // return value of constant
switch token {
case 1: token := next_token( ); return 1;
case 2: token := next_token( ); return 2;
…
} // End switch case
}// End digit( )
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
void expr( ) {
switch token {
case +: token := next_token( );
expr( ) ;
expr( );
break;
case 0..9:
digit( ); break;
…
} // End switch case
} //End expr()
void digit( ): // return value of constant
switch token {
case 1: token := next_token( ); break;
case 2: token := next_token( ); break;
…
} // End switch case
}// End digit( )
OriginalInterpreter
Each
Each
returns the
Each
returns the sum of its
Example: Interpreter
14
int expr( ) {
int val1, val2; // two values
switch token {
case +: token := next_token( );
val1 = expr( ) ;
val2 = expr( );
return val1 + val2;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
int digit( ): // return value of constant
switch token {
case 1: token := next_token( ); return 1;
case 2: token := next_token( ); return 2;
…
} // End switch case
}// End digit( )
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Interpreter
Example: Interpreter
15
int expr( ) {
int val1, val2; // two values
switch token {
case +: token := next_token( );
val1 = expr( ) ;
val2 = expr( );
return val1 + val2;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
int digit( ): // return value of constant
switch token {
case 1: token := next_token( ); return 1;
case 2: token := next_token( ); return 2;
…
} // End switch case
}// End digit( )
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Interpreter
What happens when parsing expression
“ + 2 + 1 2”
The parsing produces
?
16
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
Example: Interpreter (parse tree)
17
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
+
Example: Interpreter (parse tree)
18
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
+
Example: Interpreter (parse tree)
2
19
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
+
Example: Interpreter (parse tree)
2
2
The
return
value of
digit( )
20
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
The
returns the
21
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
22
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
23
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1
24
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1
1
25
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1+
1
1
26
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1+
1
1
27
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1+
1
1
2
28
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1+
1
1
2
2
The
29
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
1+
1
1
2
2
2
The
returns the
30
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
2+
Example: Interpreter (parse tree)
2
2
3
1+
1
1
2
2
2
The
returns the sum of its
31
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
5
2+
Example: Interpreter (parse tree)
2
2
3
1+
1
1
2
2
2
The
returns the sum of its
Example: Interpreter (parse tree)
32
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse expression
“ + 2 + 1 2”
Each
returns the sum of its
5
2
3+
1
2+
2
1
2
The parsing returns:
5
Each
returns the
Each
2
21
Example: Type Checker
33
string expr( ) { // returns type expression
string type1, type2; // other type expressions
switch token {
case +:
token := next_token( );
type1 = expr( );
type2 = expr( );
if (type1 == “int” && type2 == “int”){
return “int”;
} else{
return “error”;
}
case 0..9:
return digit ( );
…
}
}
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
string digit( ) { // returns type expression
switch token {
case 1: token := next_token( );
return “int”;
case 2: token := next_token( );
return “int”;
…
}
}
34
Example: Type Checker (cont.)
What happens when you parse subprogram
“ + 2 + 1 2” ?
The parsing produces:
“int”
35
Example: Code Generator (cont.)
What happens when you parse subprogram
“ + 2 + 1 2” ?
The parsing produces:
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
Example: Simple Code Generator
36
int expr( ) {
int target_reg; // target register
int reg1, reg2; // source registers
switch token {
case +:
token := next_token( );
target_reg = next_register( );
reg1 = expr( ) ;
reg2 = expr( );
print_inst(ADD, reg1, reg2, target_reg);
return target_reg;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Code Generator
int digit( ): // return value of constant
int target_reg; // target register
switch token {
case 1:
token := next_token( );
target_reg = next_register( );
print_inst(LOADI, 1, target_reg);
return target_reg;
case 2:
….
} // End switch case
}// End digit( )
First call to next_register() will return 1
Example: Simple Code Generator
37
int expr( ) {
int target_reg; // target register
int reg1, reg2; // source registers
switch token {
case +:
token := next_token( );
target_reg = next_register( );
reg1 = expr( ) ;
reg2 = expr( );
print_inst(ADD, reg1, reg2, target_reg);
return target_reg;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Code Generator
int digit( ): // return value of constant
int target_reg; // target register
switch token {
case 1:
token := next_token( );
target_reg = next_register( );
print_inst(LOADI, 1, target_reg);
return target_reg;
case 2:
….
} // End switch case
}// End digit( )
“ADD r
Example: Simple Code Generator
38
int expr( ) {
int target_reg; // target register
int reg1, reg2; // source registers
switch token {
case +:
token := next_token( );
target_reg = next_register( );
reg1 = expr( ) ;
reg2 = expr( );
print_inst(ADD, reg1, reg2, target_reg);
return target_reg;
case 0..9:
return digit( );
…
} // End switch case
} //End expr()
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
Code Generator
int digit( ): // return value of constant
int target_reg; // target register
switch token {
case 1:
token := next_token( );
target_reg = next_register( );
print_inst(LOADI, 1, target_reg);
return target_reg;
case 2:
….
} // End switch case
}// End digit( )
“ LOADI 1 => r
39
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
Register r1 is selected as target register.
We recurse into child
r1
Example: Code Generator (parse tree)
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
40
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
Example: Code Generator (parse tree)
We call the
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
41
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
Example: Code Generator (parse tree)
Register r2 is selected as target register.
We generate code to load digit into r2.
We return r2.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
42
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
Register r2 is selected as target register.
We generate code to load digit into r2.
We return r2.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
43
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2+
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
We return register r2 from child
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
44
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
We recurse into next
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
45
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
We select r3 as target register.
We recurse into
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
46
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
We call the
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
47
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r2
LOADI 2 => r2
Example: Code Generator (parse tree)
We select r4 as target register.
We generate code to load digit into r4.
We return r4.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
48
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
Example: Code Generator (parse tree)
We select r4 as target register.
We generate code to load digit into r4.
We return r4.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
49
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r4+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
Example: Code Generator (parse tree)
We return r4.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
50
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r4
r2
LOADI 2 => r2
r4
LOADI 1 => r4
Example: Code Generator (parse tree)
We recurse into next
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
51
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r4
r2
LOADI 2 => r2
r4
LOADI 1 => r4
Example: Code Generator (parse tree)
We call
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
52
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r4
r2
LOADI 2 => r2
r4
LOADI 1 => r4
r5
LOADI 2 => r5
Example: Code Generator (parse tree)
We select r5 as target register.
We generate code to load digit into r5.
We return r5.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
53
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3+
r4
r5+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
r5
LOADI 2 => r5
Example: Code Generator (parse tree)
We return r5.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
54
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
r2
r3
ADD r4, r5 => r3
+
r4
r5+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
r5
LOADI 2 => r5
Example: Code Generator (parse tree)
We generate addition code,
then we return target register r3.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
55
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
r1
ADD r2, r3 => r1
r2
r3
ADD r4, r5 => r3
+
r4
r5+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
r5
LOADI 2 => r5
Example: Code Generator (parse tree)
We generate addition code,
then we return target register r1.
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
generated code
(in progress)
56
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
+ 0…9 other
< expr > r1 r2 error
< digit > error r3 error
What happens when you parse subprogram
“ + 2 + 1 2”
r1
ADD r2, r3 => r1
r2
r3
ADD r4, r5 => r3
+
r4
r5+
r2
LOADI 2 => r2
r4
LOADI 1 => r4
r5
LOADI 2 => r5
Example: Code Generator (parse tree)
A postorder traversal
LOADI 2 => r2
LOADI 1 => r4
LOADI 2 => r5
ADD r4, r5 => r3
ADD r2, r3 => r1
Example: Basic Performance Predictor
57
int expr( ) { // returns cycles
int cyc1, cyc2; // subexpression cycles
switch token {
case +:
token := next_token ( )
cyc1 = expr( );
cyc2 = expr( );
// ADD takes 2 cycles
return cyc1 + cyc2 + 2;
case 0..9:
return digit ( );
…
}
}
1: < expr > ::= + < expr > < expr > |
2: < digit >
3: < digit > ::= 0 | 1 | 2 | 3 | … | 9
int digit( ) { // returns cycles
switch token {
case 1:
token := next_token ( );
return 1; // LOADI takes 1 cycle
case 2:
token := next_token ( );
return 1; // LOADI takes 1 cycle
…
}
}
+ 0…9 other
< expr > Rule 1 Rule 2
< digit > Rule 3
58
Example: Basic Performance Predictor (cont.)
What happens when you parse subprogram
“ + 2 + 1 2” ?
The parsing produces:
7
ADD takes 2 cycles
LOADI takes 1 cycle
Imperative Programming Language
59
• Manipulate an abstract machine with:
1. Variables naming memory locations
2. Arithmetic/logical operations
3. Reference, evaluate, assign operations
4. Explicit control flow statements
• Key operations: Assignment and control flow
• Fits the Von Neumann architecture
Imperative:
Sequence of state-changing actions.
Run-time Storage Organization
60
Typical memory layout
S
t
a
c
k
H
e
a
p
C
o
d
e
S
t
a
t
i
c
G
l
o
b
a
l
&
Most Language runtime layout the address space in a similar way
• Pieces (stack, heap, code & globals) may move, but all will be there
• Stack and heap grow toward each other
• Arrays live on one of the stacks, in the global area, or in the heap
Stack vs Heap
61
• Procedure activations, statically allocated local variables, parameter
values
• Lifetime same as subroutine in which variables are declared
• Stack frame is pushed with each invocation of a subroutine, and
popped after subroutine exit
Stack:
• Dynamically allocated data structure, whose size may not be known
in advance
• Lifetime extends beyond subroutine in which they are created
• Must be explicitly freed or garbage collected
Heap:
How Does Address Space Mapping Work?
62
The big picture
Compiler’s view
S
t
a
c
k
H
e
a
p
C
o
d
e
S
t
a
t
i
c
G
l
o
b
a
l
S
t
a
c
k
H
e
a
p
G
l
o
b
a
l
G
l
o
b
a
l
G
l
o
b
a
l
S
t
a
c
k
S
t
a
c
k
C
o
d
e
C
o
d
e
H
e
a
p
H
e
a
p
C
o
d
e
S
t
a
t
i
c
S
t
a
t
i
c
S
t
a
t
i
c
& & & &
virtual address spaces
…
…
OS’s view
TLB 0 high
physical address space
TLB is an address cache used by the
OS to speed virtual-to-physical address
translation. A process may have >1 level TLB
C: An Imperative Programming Language
63
• if statements, with or without else clauses
• loops, with break and continue exits
while ( < expr > ) < stmt >
do < stmt > while ( < expr > )
for ( < expr >; < expr >; < expr > ) < stmt >
• switch statements
• goto with labelled branch targets
Expressions: include procedure and function calls and assignments,
and thus can have side-effects
Control Structures:
Basic Comparisons (Incomplete)
64
C JAVA
Basic types:
int, double, char, boolean
Primitive types:
int, double, char, boolean
Pointer (to a value) Reference (to an object)
Aggregates:
array, struct
Aggregates:
array, object (class)
Control Flow:if-else, switch, while,
break, continue, for, return, goto
Control Flow:if-else, switch, while,
break, continue, for, return
Logic Operators:
||, &&, !
Logic Operators:
||, &&, !
Logical Comparisons:
==, !=
Logical Comparisons:
==, !=
Numeric Comparisons:
<, >, <=, >=
Numeric Comparisons:
<, >, <=, >=
string as char* array String as an object
Pointers in C
65
• “address-of” operator &
• dereference (“content-of”) operator *
Pointer: Variable whose R-value (content) is the L-value (address) of a
variable
int *p, x;
p = &x;
*p = 5;
p
5
x
x = 12; 12
xp
p x
Example: Maintaining Free Lists
66
• Allocate: continuous block of memory; remove space from free list
(here: singly-linked list).
• Free: return to free list after coalescing with adjacent free storage (if
possible); may initiate compaction.
Example: Maintaining Free Lists
free space pointer
NEWLY ALLOCATED
free space pointer
Before Allocation:
After Allocation:
ALLOCATED
Example: Maintaining Free Lists
68
FREE
free space pointer
Before De-allocation:
After De-allocation:
free space pointer
Potential Issues with Explicit Control of Heaps
69
• Dangling references
– Storage pointed to is freed, but pointer is not set to NULL
– Able to access storage whose values are not meaningful
• Garbage
– Objects in heap that cannot be accessed by the program any more
– Example
int *x, *y;
x = (int*) malloc (sizeof (int));
y = (int*) malloc (sizeof (int));
x = y;
• Memory leaks
– Failure to release (reclaim) memory storage build up overtime
Potential Issues with Explicit Control of Heaps
70
• Dangling references
– Storage pointed to is freed, but pointer is not set to NULL
– Able to access storage whose values are not meaningful
• Garbage
– Objects in heap that cannot be accessed by the program any more
– Example
int *x, *y;
x = (int*) malloc (sizeof (int));
y = (int*) malloc (sizeof (int));
x = y;
• Memory leaks
– Failure to release (reclaim) memory storage build up overtime
Potential Issues with Explicit Control of Heaps
71
• Dangling references
– Storage pointed to is freed, but pointer is not set to NULL
– Able to access storage whose values are not meaningful
• Garbage
– Objects in heap that cannot be accessed by the program any more
– Example
int *x, *y;
x = (int*) malloc (sizeof (int));
y = (int*) malloc (sizeof (int));
x = y;
• Memory leaks
– Failure to release (reclaim) memory storage build up overtime
Example: Singly-Linked List
72
#include
#include
/* TYPE DEFINITION */
typedef struct cell listcell;
struct cell
{ int num;
listcell *next;
};
/* GLOBAL VARIABLES */
listcell *head, *new_cell, *current_cell;
Example: Singly-Linked List
73
#include
listcell *head, *new_cell, *current_cell;
int main(void){
/* CREATE FIRST LIST ELEMENT */
…
/* CREATE NINE MORE ELEMENTS */
…
/* DEALLOCATE LIST */
for(current_cell = head;
current_cell != null;
current_cell = current_cell -> next){
free(current_cell);
}
…
}
Let’s deallocate,i.e., free all list elements
Does this work?
Example: Singly-Linked List
74
#include
listcell *head, *new_cell, *current_cell;
int main(void){
/* CREATE FIRST LIST ELEMENT */
…
/* CREATE NINE MORE ELEMENTS */
…
/* DEALLOCATE LIST */
for(current_cell = head;
current_cell != null;
current_cell = current_cell -> next){
free(current_cell);
}
…
}
Let’s deallocate,i.e., free all list elements
What went wrong?
75
#include
#include
int main(void){
int *a;
*a = 12;
printf(“%x,%x: %d\n”, &a, a, *a);
a = (int *)12;
printf(“%d \n”, *a);
}
Uninitialized variables and “dangerous” casting
> a.out
effff60c effff68c: 12
segmentation fault (core dumped)
Note: Segmentation faults result in the generation of a core file which can
be rather large. Don’t forget to delete it.
What went wrong?
76
That’s better!
#include
#include
int main(void){
int *a = NULL; /* good practice */
a = (int *)malloc(sizeof(int));
*a = 12;
printf(“%x,%x: %d\n”, &a, a, *a);
}
> a.out
effff60c 20900: 12
What went wrong?
77
#include
#include
int main(void){
int i;
char* string = “Hello, how are you today.”;
printf(“\n%s\n”, string);
for(i = 0; string[i] != ‘.’; i++){
if(string[i] = ‘ ‘)
for(; string[i] = ‘ ‘; i++);
printf(“%c”, string[i]);
}
printf(“.\n”);
}
> a.out
Hello, how are you today.
Segmentation fault (core dumped)
What went wrong?
78
“ = ” is not the same as “ == ”
#include
#include
int main(void){
int i;
char* string = “Hello, how are you today.”;
printf(“\n%s\n”, string);
for(i = 0; string[i] != ‘.’; i++){
if(string[i] == ‘ ‘)
for(; string[i] == ‘ ‘; i++);
printf(“%c”, string[i]);
}
printf(“.\n”);
}
> a.out
Hello, how are you today.
Hello,howareyoutoday.
What went wrong?
79
“ Aliasing ” and freeing memory
#include
#include
int main(void){
int *a = NULL;
int *b = NULL;
int *c = NULL;
a = (int *)malloc(sizeof(int));
b = a;
*a = 12;
printf(“%x %x: %d\n”, &a, a, *a);
printf(“%x %x: %d\n”, &b, b, *b);
free(a);
printf(“%x %x: %d\n”, &b, b, *b);
c = (int *)malloc(sizeof(int));
*c = 10;
printf(“%x %x: %d\n”, &c, c, *c);
printf(“%x %x: %d\n”, &b, b, *b);
}
> a.out
effff60c 209d0: 12
effff608 209d0: 12
effff608 209d0: 12
effff604 209d0: 10
effff604 209d0: 10
What went wrong?
80
Use a subroutine to create an object
#include
#include
/* TYPE DEFINITION */
typedef struct cell listcell;
struct cell
{
int num;
listcell *next;
};
listcell *head = NULL;
listcell *create_listcell(){
listcell new;
new.num = -1;
new.next = NULL;
return &new;
}
int main(void){
head = create_listcell();
printf(“head -> num = %d\n”, head -> num);
}
What went wrong?
81
> gcc stack.c
stack.c: In function “create_listcell”:
stack.c:17: warning: function returns address of local variable
> ./a.out
head —> num = -1
Use a subroutine to create an object (cont.)
What went wrong?
82
#include
#include
/* TYPE DEFINITION */
typedef struct cell listcell;
struct cell
{
int num;
listcell *next;
};
listcell *head = NULL;
listcell *create_listcell(){
listcell *new;
new = (listcell *)malloc(sizeof(listcell));
new -> num = -1;
new -> next = NULL;
return new;
}
int main(void){
head = create_listcell();
printf(“head -> num = %d\n”, head -> num);
}
Use a subroutine to create an object: malloc
What went wrong?
83
> gcc heap.c
> ./a.out
head —> num = -1
Use a subroutine to create an object: malloc (cont.)
Pointers and Arrays in C
84
• Array name is a pointer to a[0]:
• Pointer arithmetic is array indexing
• Exception: an array name is a constant pointer
Pointers and arrays are similar in C:
int a[10];
int *pa;
pa = &a[0];
pa and a have the same semantics
pa + 1 and a + 1 point to a[1]
a++ is ILLEGAL
a = pa is ILLEGAL (pa = a is LEGAL!)
Next Lecture
85
• Start programming in C.
• Read Scott, Chapter 8.1 – 8.2; ALSU 7.1 – 7.3.
• Next time:
– Procedure abstractions; Runtime stack; Scoping
Things to do: