Chapter 7: Basic Semantics

  • Syntax of a programming language tells us what the language constructs looks like.
  • Semantic of a programming language tells us what the language constructs actually do.

7.1 Attributes, Binding, and Semantic Functions

  • Values are any storable quantities.
  • Locations are like addresses in the memory
  • Meaning of name is determined by the properties, or attributes, associated with the name.
  • The process of associating an attribute with a name is called binding.
  • Binding time of the attribute classified according to the time during the translation/execution process when it is computed and bound to a name.
    • Static binding occurs prior to execution.
      • A static attribute can be bound during parsing or semantic analysis (translation time),
      • during the linking of the program with libraries (link time),
      • during the loading of the program for execution (load time).
      • language definition time, predefine identifiers or the language.
    • Dynamic binding occurs during execution
      • A dynamic attribute can be bound on entry or exit from a procedure, or
      • on entry or exit from the entire program
  • symbol table is a data structure that maintain the appropriate meanings given to names (names → attributes).
  • parsing phase of translation
    • lexical analysis determines whether a string of characters represents a token in the vocabulary of the language
    • syntax analysis determines whether a sequence of tokens represents a phrase in the CFG of the language.
    • static semantic analysis is concerned with establishing the attributes of names in declarations and ensuring that the use of these name in references conforms to their declared attributes.
  • Environment is to maintain the binding of names to storage location (names → location).
  • Memory is to maintain the binding of storage location to values. (locations → values).

7.2 Declarations, Blocks, and Scope

  • explicit binding (int x; bind x to integer) vs implicit binding (int x; location of x)
  • definition bind all potential attributes.
  • declaration partially specify attributes (e.g. function prototype)
  • declarations associate with a specific block are called local
  • declarations in surrounding blocks (or global) are nonlocal
  • block structure associate each declared name a level number and offset to call lexical address
    • The level number increase as we move into each nested block
    • The offset of the names declared within each nested block
  • The scope of a binding is the region of the program over which the binding is maintained.
int x;

void p() {
  char x;

void q() {
  char x;
  ::x = 42;
  • x in p() takes precedence over the global declaration of x
  • scope resolution operator :: (in C++) is to access hidden declaration (::x in q()).
  • extern is use to access global variable declaration across files in C.

7.3 The Symbol Table

  • scope analysis
    • the maintenance of scope information in a lexically scoped language with block structure requires that declarations be processed like a stack
      • on entry into a block, all declaration of that block are processed and the corresponding bindings added to the symbol table
      • on exit from the block, the bindings provided by the declaration are removed and restoring any previous bindings that may have existed.
  • dynamic vs static scoping.
  • problem with dynamic scoping
    • when a nonlocal name is used in an expression or statement, the appropriate declaration that applies to that name must obtain from executions. The semantics of the program changes during execution.
    • nonlocal variable references cannot predicted prior to execution, neither can the data types of the variable.

7.4 Name Resolution and Overloading

  • A translator disambiguate two uses of the same symbol by looking at the data types of the operands.
  • Overload resolution
    • The basic method for allowing overloaded functions is to expand the operation of the lookup operation in the symbol table to perform lookups based not only on the name of a function but also on the number of its parameters and their data types.
  • There is no semantic difference between operator and functions, only syntactic difference that operators are written in infix form while function calls are always written in prefix form.

7.5 Allocation, Lifetimes, and the Environment

  • The lifetime of an object is the duration of its allocation in the environment
  • heap allow arbitrary allocation and deallocation (dynamic allocation)
  • stack-based/automatic allocation refer to allocation of local variable.
  • static allocation refer to allocation of global variable.
int f() {
  static int x;
  • x is allocated only once and it has the same meaning (and value) across all calls to f. This combination of local scope with global lifetime can be used to preserve local state across calls to f, while at the same time preventing code outside the function from changing this state.

7.6 Variables and Constants

  • Variables is an object whose stored value can change during execution
    • principle attributes are name, location and value.
    • r-value is value stored in the location of a variable
    • l-value is the location of a variable
    • assignment by sharing result in binding the location instead of its value (pointer or reference semantics).
    • assignment by cloning result in binding to a new allocation location with the copy of the value (storage or value semantics).
  • Constants is a language entity that has a fixed value for the duration of its existence in a program.
    • no location attribute, only value.
    • constant has value semantics.
    • symbolic constant is essentially a name for a value
    • compile time vs load time constant

7.7 Aliases, Dangling References, and Garbage

  • Alias occurs when the same object is bound to two different names at the same time.
    • occur during procedure call, through the use of pointer variable and through assignment by sharing.
    • side effect of a statement is any change in the value of a variable that persists beyond the execution of the statement.
    • potential harmful side effect is changes to variables whose names do not directly appear in the statement because the effect cannot determined from the written code.
  • Dangling references is a location that has been deallocated from the environment but that can still be accessed by a program.
    • occur when global pointer reference local object, return a pointer to a local object in a function, and two pointers reference to the same object while one of the pointer free that object.
  • Garbage is memory that has been allocated in the environment but inaccessible to the program.
    • occur when pointer to a memory when reassign to another object before call free.

7.8 Case Study: Initial Static Semantic Analysis of TinyAda

Additional Notes


Other Resources