Shared Flashcard Set


Comp2010 - Flashcard Set 6 - Contextual Analysis
Comp2010 - Flashcard Set 6 - Contextual Analysis
Computer Science
Undergraduate 2

Additional Computer Science Flashcards




What is contextual analyisis?
  • "Semantic" analysis - context-sensitive syntax
  • Determine whether program is well-formed
    • Scope rules (i.e. visibility)
    • Type rules (i.e. compatibility)
  • Two phases
    • Identification - What does identifier refer to?
    • Type checking - Can you do that with it?
What is the difference between identifiers and symbols?
  • Operations on strings are expensive (Comparison, hashing, etc)
  • Instead:
    • Enter all identifiers into common area (Lexeme pool)
    • Can be done by lexer
    • Work with symbols
Show a java implementation which can be used to represent symbols
  • package Symbol;
  • public class Symbol {
    • private String name;
    • private Symbol(String n){name = n;}
    • priavte static Dictionary pool = new Hashtable();
    • public String toString() {return name;}
    • public static Symbol toSymbol(String n) {
      • String u = n.intern();
      • Symbol s= (Symbol) pool.get(u);
      • if (s==null) {s=new Symbol(u); pool.put(u,s);}
      • return s;
    • }
  • }


What are symbol tables?
  • Map symbols(identifiers) to attributes
    • Constant: Type, value,...
    • Variable: type, pointer to declaration, ..
    • Method: return and argument types, modifiers...
    • Class: pointer to (public) symbol table, ...
  • Also called environments = set of bindings
  • Must cope with 
    • Nested scopes: Block structure
    • Parallel scopes: Multiple name spaces
  • Efficiency is important (But not paramount)
    • Lookup is most common operation
What are the keys of a symbol table implementation?
  • Use hash table for efficiency
    • Allow multiple entries with the same key(External chaining)
  • New binding for identifier x added to head of list for hash table bucket
    • "Hides" earlier occurrences
  • Uses auxiliary stack to implement "undo":
    • beginScope() pushes marker into stack
      • Subsequent entries recorded on stack
    • endScope() pops symbols from stack, removes binding form table
What is a hyperscope?
  • Standard environment
    • Standard collection of types, functions, etc
    • Can be used without declaration / import
    • e.g. built-in pascal-functions, java.lang
  • Initialize symbol table with these
    • At outermost scope level
    • Watch for re-definitions (if required by language)
How can multiple name-spaces be implemented?
  • In many languages, a single symbol table is not sufficient; type and variable declaration must be visible at the same time. Solutions:
    • Change symbol table type: Tag*Symbol
    • Separate tables for types and variables
  • Module/classes must have separate name-spaces
    • accessible by qualification/import
    • Separate tables for each compilation unit
      • Separate compilation requires persistent symbol tables
        • Modula-2: .sym-files
        • C: delayed to linker, no real error check
What are the principles of type checking?
  • Checking that identifiers are used correctly (i.e. in accordance with their [declared] type)
  • Statically typed languages
    • (Fortran, C), Ada, C++ Java, ML, Haskel...
  • Dynamically typed languages
    • Lisp, scheme - types determined at runtime
How can type checking be achieved?
  • Recursive walk over tree
  • Uses current environment -> assignmentstatement -> Variable/Expression
    • Look up type of Variable
    • Check and determine type of Expression
    • Check for compatiblity
  • Compatibility rules
    • Subtyping
    • Coercion: insert operations to enforce compatibility
How can type checking function calls be achieved?
  • If you have a function:
    • boolean greater(int x, int y){ return x>y;}
    • ...
    • if (greater(a,b){...}
  • Type greater is int x int -> boolean
  • To check applied occurrence:
    • Look up greater in symbol table
    • Check types of actual parameters match
    • Result type of function (boolean) becomes result type of function call)


What can we do with results of type checking?
  • Environment/type information is transient:
    • Interleave contextual analysis and translation
      • Augment tree traversal with code to build intermediate representation
  • Decorate AST with contextual information
    • Add link from each use of an identifier to corresponding declaration node in AST
    • Add link to symbol table entry for each declaration node in AST
    • Store inferred type of expression E at root node of E in AST
Supporting users have an ad free experience!