Content

1. Overview
2. Abstract Syntax Tree (AST)
3. Type Checking
    1. Type Checker
    2. Compound Type Equivalence
    3. Type Compatibility
    4. Scoping
4. Runtime Environment
    1. Data Representation
    2. Storage Classes
    3. Runtime Stack
    4. Memory Management

Overview

Parsing → Abstract syntax tree (AST) ← semantic analysis

Abstract Syntax Tree (AST)

  • Parse tree: structure of derivation of input sentence
    • Interior nodes: non-terminals
    • Leaf nodes: terminals
  • Abstract syntax tree: structure of input sentence; does not include keywords and punctuations
    • Interior nodes: operators
    • Leaf nodes: operands

Type Checking

  • Declaration
  • Types & operations
  • Assignment
  • Function parameters
  • Singly or multiply typed
  • Static (compile time) or dynamic type checking (runtime)
  • Type conversion
  • ...

Type Checker

Type + language constructs → type + semantic rules

  • Interpreter: variables first encountered have type info stored in symbol table
  • Compiler: symbol table discarded after compilation

Compound Type Equivalence

type
    little = array[1..5] of integer;
    small = array[1..5] of integer;
    big = array[1..10] of integer;
var
    a, b: array[1..5] of integer;
    c: array[1..5] of integer;
    d, e: little;
    f, g: small;
    h, i: big;

* d..i: named types
* a..c: anonymous types
* c structurally equivalent to a, b, d..g

Complex types (list, tables, queues, ...) harder to check!

Type Compatibility

  • Type coercion: int coerced to double
  • Subtypes: e.g. subclassing in OO; C's enum subtype of int

Scoping

Lexical area in which a variable is visible.

  • One symbol table per scope
  • One global symbol table, each scope has a number; variables assigned scope numbers
  • Static & dynamic scoping of function call
    • Static: where function is defined
    • Dynamic: where function is called
  • Keep track of:
    • Location of global variables
    • Location of local variables
    • Location of functions

Runtime Environment

Statically linked libraries, dynamically linked libraries, OS, I/O, memory allocation/deallocation... may be written in other languages; need an interface between target program & runtime external functions.

Data Representation

Many machines support the same primitive types, but not pointers, arrays, structs, objects, ...

Storage Classes

Lifetime of a variable.

  • Global: lifetime = program
  • Local: lifetime = call/block
  • Static: lifetime = program, used within functions only
  • Dynamic: lifetime = that of the pointer pointing to it

Runtime Stack

  • Parameters passing
    • By value
    • By value-result
    • By reference
    • By name
    • ...
  • Flow
    • Before function call, calling routine:
      • Save registers
      • Push args onto stack
      • Setup static links if appropriate
      • Push return address onto stack
      • Jump to target
    • During function call, target routine:
      • Setup frame pointer
      • Make space for local variables
      • Do job...
      • Tear down frame pointer & static links
      • Restore saved registers
      • Jump back
    • After function call, calling routing:
      • Remove return address & params from stack
      • Restore saved registers
      • Continue...

Memory Management

new/delete in C++, malloc in C, garbage collection in Java, ...

results matching ""

    No results matching ""