Lecture Notes

Chapter 6 Name Resolution and Scoping:

Reading

Chapter 6: Name Resolution and Scoping

List of what can be named in a program:

  1. Variables (local/global) and parameters
  2. Procedures/Functions/Methods/Sub-routines
  3. Modules/Packages
  4. Classes
  5. Fields
  6. Program locations (labels)
  7. Types and Structures
Activation Records

All code runs in a data context (a state)–the context is the data associated w/ the running code. The data associated is typically the state of parameters and the local variables; the state associated w/ an object is kept in dynamically allocated blocks of memory on the heap.

IMPORTANT: Parameters and local variables are typically stored in an activation record

What is an activation record? An activation record (sometimes called an activation or frame) contains other information aside from the parameters and local variables. They contain:

  1. return address
  2. saved registers
  3. pointers (links) to other activation records
  4. other language-dependent / architecture-dependent information

When a procedure is called, an activation record is called. The size of the activation record depends on the number of local variables and parameters. The order in which they need to be arranged in should be:

  1. Place parameters first in the order they appear in the program
  2. Place locals second in the order they appear in the program

For each local, allocate a separate location; however, there are some compilers that would determine if two locals can share a location in the activation record bc their use in the code does not overlap.

The pointer that points to the activation record is called a stack pointer–all locals and parameters are addressed relative to it.

If the execution architecture uses registers, an activation record might contain space for storing registers' values before a call to a new procedure and for restoring the values of registers upon returning from a procedure call. ALso, return values from procedures returning a value might be stored in the activation record.

If the execution architecture are non-register-based using stack evaluation, the evaluation stack also might be stored in the activation record. Non-variable/parameter content of an activation record will depend on the execution architecture.

  • Dynamic Link - stored in an activation record for a method/function $f$ points to the activation record for the method/function that called $f$ ($f$ is the callee; the one calling $f$ is the caller)

The Dynamic Link serves two purposes:

  1. Points to the activation record of the caller (when the callee terminates, activation record is restored as the current activation record); therefore, the dynamic link will point to the activation record of its caller, etc.
  2. If the language is dynamically scoped, the dynamic link will access the activation record of the caller and its caller, and etc. to search for variables/parameters not found in the activation record of the function that is currently running.

NOTE: if a language is dynamically scoped, the callee can legally refer to the caller’s variables (or at least the variables currently in its activation record).

Call chain - the collection of dynamic links, starting at the current method

Closests enclosing scope - Following the static link to the activation record that lexically is closest tot he code associated w/ the activation record in which we did not find the variable.

Every time a procedure is called, or a method is invoked, a corresponding activation record is created. The activation record is then placed on top of a stack called the activation stack and made the current activation. Once the procedure is finished executing, the corresponding activation record (found at the top of the activation stack) will be removed. The current activation at the top of the activation stack will be made as the current activation, and the progam execution will continue in the code associated w/ this activation.

If a language supports multi-threading, each thread must have its own activation stack.

Name Binding and Scoping

Scope has two different uses:

  1. Part of the code in which a referene to a name binding is valid.
  2. Part of the code in which names are validly bound.

Name Binding - is an association of an identifier (name) with an entity. For example: declaring a variable where you associate the name of the variable with the location of the declaration in the parse tree. Declaring a method or a function would associate a name w/ the source code for the method/function.

Name of a class, name of a variable, name of a function, and the name of a parameter are examples of name bindings.

Scope of name binding - part of the code in which a reference to that name results in that specific name and not a different one.

Forward Referencable

Forward referencable - can be used before its declaration point. Requires a multi-pass compiler to capture the declaration in a prior pass tot he resolution pass, unless we use forward declarations or prototypes for functions.

Forward declarations - prototypes in C/C++. It is a incomplete declaration that appears before the first use of a name. Are necessary to implement on a one-pass compiler.

Symbol Table

A symbol table is used to associate names w/ declarations/definitions. Each scope within the program has associated a symbol table associated w/ it. A symbol table also has a reference to a parent symbol table associated w/ the enclosing scope of the code w/ which the table is associated.

Summary