程序代写代做代考 scheme python compiler Java flex chain javascript lec11

lec11

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 11: Names, Scopes, and Binding

October 10, 2018

Class Information

2

• Project 1 posted (open at noon), due Tuesday 10/23 11:55 pm EDT.
• Midterm exam will be on 11/7 Wednesday, in class, closed-book.
• Project 2 will be released immediately after midterm exam.
• My office hour this week is changed to Thursday 4:00pm-5:00pm.

Project 1: overview

3

RISC
Machine Code

optimizer

Example: tinyL.out

RISC
machine code

Example:
optimize < tinyL.out Output to stdout … > opt.out

Optimizer

compiler

tinyL.program

tinyL.program

Example:
test1

Example:
compile test1

Output always
“tinyL.out”

Compiler

RISC
machine code run

Output
of execution

Example: run opt.out

Project 1: overview

4

RISC
Machine Code

optimizer

Example: tinyL.out

RISC
machine code

Example:
optimize < tinyL.out Output to stdout … > opt.out

Optimizer

compiler

tinyL.program

tinyL.program

Example:
test1

Example:
compile test1

Output always
“tinyL.out”

Compiler

RISC
machine code run

Output
of execution

Example: run opt.out

Project 1: overview

5

RISC
Machine Code

optimizer

Example: tinyL.out

RISC
machine code

Example:
optimize < tinyL.out Output to stdout … > opt.out

Optimizer

compiler

tinyL.program

tinyL.program

Example:
test1

Example:
compile test1

Output always
“tinyL.out”

Compiler

RISC
machine code run

Output
of execution

Example: run opt.out

Project 1 Part II: Constant Propagation

6

Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.

Example:
Original Code

LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc

After One Pass

LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf

See project description for more details.

Project 1 Part II: Constant Propagation

7

Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.

Example:
Original Code

LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc

After One Pass

LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf

See project description for more details.

Project 1 Part II: Constant Propagation

8

Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.

Example:
Original Code

LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc

After One Pass

LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf

See project description for more details.

Is this good enough?

Project 1 Part II: Constant Propagation

9

Constant Propagation: Substitute the values of known constants in
expressions at compile time. Fold multiple instructions into one if
necessary. The constant values might “propagate” and require
multiple passes of analysis.

Example:
Original Code

LOADI Ra #1
LOADI Rb #1
ADD Rc Ra Rb
LOADI Rd #2
LOADI Re #2
ADD Rf Re Rd
ADD Rg Rf Rc

After One Pass

LOADI Rc #2
LOADI Rf #4
ADD Rg Rc Rf

See project description for more details.

After Another Pass

LOADI Rg #6

Names, Bindings, and Scope

10

What’s a name?

A name is a mnemonic character string used to represent something else.

Names, Bindings, and Scope

11

• Has associated “attributes” 

Examples: type, memory location, read/write permission, storage
class, access restrictions.

• Has a meaning 

Examples: represents a semantic object, a type description, an
integer value, a function implementation, a memory address.

What’s in a name?

12

• Compile time: during compilation process – static (e.g.: macro
expansion, type definition)

• Link time: separately compiled modules/files are joined together by
the linker (e.g: adding the standard library routines for I/O (stdio.h),
external variables)

• Run time: when program executes – dynamic

Names, Bindings, and Scope

Bindings – association of a name with the thing it “names”

Binding Time – Choices

13

• Early binding times — more efficient (faster) at run time
• Late binding times — more flexible (postpone binding decision

until more “information” is available)
• Examples of static binding (early):

– functions in C
– types in C

• Examples of dynamic binding (late):
– virtual methods in Java
– dynamic typing in Javascript, Scheme

Note: dynamic linking is somewhat in between static and dynamic
binding; the function signature has to be known (static), but the
implementation is linked and loaded at run time (dynamic).

How to Maintain Bindings

14

• Symbol table: maintained by compiler during compilation
names ⇒ attributes

• Referencing Environment: 

maintained by compiler-generated-code during 

program execution
names ⇒ memory locations

Scope Example

15

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

local variable,
procedure def.

implementation

Scope Example

16

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Scope Example

17

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

Scope Example

18

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Scope Example

19

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

Scope Example

20

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

Scope Example

21

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Nested Subroutines (Algol 60, Ada, Common Lisp, Python, ….)

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Lexical Scope

22

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

Lexical Scope

23

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
program L;

var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

Lexical Scope

24

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
program L;

var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

Lexical Scope

25

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
program L;

var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?
Which “n”?

Lexical Scope

26

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable
program L;

var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?
Which “n”?

L

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Lexical Scope

27

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

L

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Lexical Scope

28

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

L

Caller

Lexical Scope

29

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

L
Which “n”?

L

Caller

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Dynamic Scope

30

• Non-local variables are associated with declarations at run time
• Find the most recent, currently active run-time stack frame

containing a declaration of the variable

L ⇒ W
L ⇒ D ⇒ W

Calling Chain:

The output is ?

Caller

L
D

Which “n”?

program L;
var n: char; {n declared in L}
procedure W;
begin

write (n); {n referenced in W}
end;
procedure D;

var n: char; {n declared in D}
begin

n := ‘D’; {n referenced in D}
W

end;
begin

n := ‘L’; {n referenced in L}
W;
D

end

Lexical Scope v.s. Dynamic Scope

31

• Non-local variables are associated with declarations at compile time
• Find the smallest block syntactically enclosing the reference and

containing a declaration of the variable

Lexical Scope

• Non-local variables are associated with declarations at run time
• Find the most recent, currently active run-time stack frame

containing a declaration of the variable

Dynamic Scope

Review: Program Memory Layout

32

• Static objects are given an absolute address
that is retained throughout the execution of
the program

• Stack objects are allocated and deallocated in
last-in, first-out order, usually in conjunction
with subroutine calls and returns

• Heap objects are allocated and deallocated at
any arbitrary time

stack

heap

static &
global

code

Procedure Activations

33

• Begins when control enters activation (call)
• Ends when control returns from call

Example:

Subroutine C

Subroutine B

Subroutine B

Subroutine A

procedure C:
D
procedure B:
if…then B else C
procedure A:
B
main program:
A

sp

Direction of
stack growth

(usually lower
addresses)

Calling chain: A ⇒ B ⇒ B ⇒ C ⇒ D

parameter
return value

return address

access link

caller FP

local variables

Subroutine D

Procedure Activations

34

• Run-time stack contains frames from main program & active procedure
• Each stack frame includes:

1. Pointer to stack frame of caller 

(control link for stack maintenance and dynamic scoping)

2. Return address (within calling procedure)
3. Mechanism to find non-local variables (access link for lexical scoping)
4. Storage for parameters, local variables and final values
5. Other temporaries including intermediate values & saved register

parameter
return value

return address

access link

caller FP

local variables

Stack Frame
or

Activation Record Frame Pointer (FP)
or Activation Record

Pointer (ARP)

Usually stored in a register

Lexical Scoping and Dynamic Scoping Implementation

35

How do we look for non-local variables?
Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Lexical Scoping and Dynamic Scoping Implementation

36

How do we look for non-local variables?
Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Lexical Scoping and Dynamic Scoping Implementation

37

How do we look for non-local variables?

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Lexical Scoping and Dynamic Scoping Implementation

38

How do we look for non-local variables?

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Lexical Scoping and Dynamic Scoping Implementation

39

How do we look for non-local variables?

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end

Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin


call C // occurrence of C
call B // occurrence of B

end

Lexical Scoping and Dynamic Scoping Example

40

Calling chain: MAIN⇒ C ⇒ B ⇒ B Control linksAccess links

fp
main

o
o

x
y

C
o

o
x

B
o

o
y
z

B
o

o
y
z

Look up Non – local Variable Reference

41

Access links and control links are used to look for non-local
variable references.

Static Scope:
Access link points to the stack frame of the most recently activated
lexically enclosing procedure

⇒ Non-local name binding is determined at compile time, and 

implemented at run-time

Dynamic Scope:
Control link points to the stack frame of caller

⇒ Non-local name binding is determined and implemented at 

run-time

Access to Non-Local Data

42

• visible everywhere
• translated into a logical address at compile time

How does the code find non-local data at run-time?

Real globals:

Lexical scoping:
• view variables as (level, offset) pairs, (compile-time symbol table)
• use (level, offset) pair to get address by using chains of access link

(at run-time)

Dynamic scoping:

• variable names are preserved
• look-up of variable name uses chains of control links (at run-time)

Lexical Scoping

43

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

44

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

45

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

46

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

47

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

48

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

49

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

50

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

51

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

52

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Lexical Scoping

53

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

54

• Assume the nesting level of the statement is level 2
• Register r0 contains the current FP (frame pointer)
• (2, 1) and (2, 2) are local variables, so they are allocated in the

activation record that current FP points to. 

(1, 1) is an non-local variable.

• Two new instructions:
LOAD Rx, Ry means Rx ← MEM(Ry)
STORE Rx, Ry means MEM(Rx) ← Ry

Access to Non-Local Data(Lexical Scoping)

What code do we need to generate for this statement:

(2,1) = (1,1) + (2,2)

What do we know?

Lexical Scoping

55

Symbol table generated at compile time matches declarations and occurrences.
⇒ Each name can be represented as a pair (nesting_level, local_index).

Program
x, y: integer // declarations of x and y
Procedure B // declaration of B
y, z: real // declaration of y and z
begin

y = x + z // occurrences of y, x, and z
if (…) call B // occurrence of B
end
Procedure C // declaration of C
x: real
begin

call B // occurrence of B
end
begin

call C // occurrence of C
call B // occurrence of B
end

Program
(1,1), (1,2): integer // declarations of x and y
Procedure (1,3) // declaration of B
(2,1), (2,2): real // declaration of y and z
begin

(2,1) = (1,1) + (2,2) // occurrences of y, x, and z
if (…) call (1,3) // occurrence of B
end
Procedure (1,4) // declaration of C
(2,1): real
begin

call (1,3) // occurrence of B
end
begin

call (1,4) // occurrence of C
call (1,3) // occurrence of B
end

Review: Access to Non-Local Data(Lexical Scoping)

56

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

parameter
return value

return address

access link

caller FP

local variables

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Current

Frame Pointer
FP

Lexical Parent

Saved in r0
Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

57

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

58

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local
variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

59

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP
local

variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

60

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

61

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

Saved in r4

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

62

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP

local variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

Saved in r4

// offset of local variable (1,1) in frame
// offset of access link in frame (bytes)
// address of access link
// get access link, fp for frame at level 1
// address of local variable (1,1) in frame
// get content of variable (1,1)
// offset of local variable (2,2) in frame
// address of local variable (2,2)
// get content of variable (2, 2)
// (1,1) + (2,2)
// offset of local variable (2,1) in frame
// address of local variable (2,1)
// (2,1) = (1,1) + (2,2)

Access to Non-Local Data(Lexical Scoping)

63

What code do we need to generate for statement (*)?

(2,1) = (1,1) + (2,2)

(1,1) LOADI r1, #4
LOADI r2, #-4
ADD r3 r0 r2
LOAD r4 r3
ADD r5 r4 r1
LOAD r6 r5
(2,2) LOADI r7 #8
ADD r8 r0 r7
LOAD r9 r8
+ ADD r10 r6 r9
(2,1) LOADI r11 #4
ADD r12 r0 r11
= STORE r12 r10

parameter
return value

return address

access link

caller FP

local variables

Frame Pointer
FP

Low

High

parameter
return value

return address

access link

caller FP
local

variables

Level 1

Level 2 —> Current Level

Frame Pointer
FP

Saved in r0

Current

Assume “access link” field is 4 bytes.
Each unit offset corresponds to 4 bytes.

Saved in r4

Next Lecture

64

• Read Scott, Chapter 3.1 – 3.4, Chapter 9.1 – 9.3 (4th Edition) or
Chapter 8.1 – 8.3 (3rd Edition)

• Read ALSU, Chapter 7.1 – 7.3 (2nd Edition).

Things to do: