Copyright © 2004, 2021
Robert W. Hasker

Ch. 5

Semantic Analysis: Variables & Types

• track variables
• check types

Symbol Tables

• sometimes called the "environment"
• track which identifiers are legal
• map identifiers to types and locations
  • types, locations: the "meanings" of variables
  • also known as "bindings" (especially when talking about an environment)
• issue: nested definitions

          class C
          {
             int a, b;
             ...
             public void f()
             {
                int x = a + b;
                String a = "a and b is "; // new declaration of a - hides older one
                System.out.println(a + x);
             }
          }
  

  • track which binding of a is being accessed by which statement
• implementation
  • simple method (imperative): map from variables to a stack of bindings
    • push new binding when define new variable
    • pop appropriate stacks when leave scopes
    • requires tracking what variables are defined in each scope
  • alternative method (functional): use a tree with a different root for each scope
    • This is a useful optimization, but not necessary for this term's project
    • example, if interested: fig 5.4
    • note: to insert new value at level d, may need to copy nodes from root to level d
    • can be (nearly?) as fast as imperative solution

Type Checking

• type information which must be stored:
  • variables: type
  • methods: parameters, result type
    • in MiniJava: add local variables; locals can only be declared at beginning of methods
  • classes: variable and method declarations
• MiniJava types
  • primitive types: int, boolean
  • integer array: int []
  • class names
  • can store types as strings; this allows using string equality to check types
• type-checking in MiniJava
  • algorithm
    • pass 1: build symbol table from abstract parse tree
      • check for duplicated declarations
    • pass 2: type-check statements and expressions
      • improvement over book: add isInteger and isBoolean operations to types (and introduce a type hierarcy) to simplify type-checking operations
  • example: to check e₁ + e₂, need to check that e₁ and e₂ are both integers and note that the result type is an integer
    • note: more sophisticated language would require differentiating between integer addition and floating-point addition
  • assignment: both sides must have same type
    • will need to refine when implement inheritance
  • method calls: check types of actual parameters against formal parameters
• error handling
  • if variable not declared, add entry (assume it's an int) so can continue
• ensure all errors detected by type-checking phase!

Review

• symbol tables
• type checking