Term
| What is contextual analyisis? |
|
Definition
- "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?
|
|
|
Term
| What is the difference between identifiers and symbols? |
|
Definition
- 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
|
|
|
Term
| Show a java implementation which can be used to represent symbols |
|
Definition
- 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;
- }
- }
|
|
|
Term
|
Definition
- 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
|
|
|
Term
| What are the keys of a symbol table implementation? |
|
Definition
- 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
|
|
|
Term
|
Definition
- 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)
|
|
|
Term
| How can multiple name-spaces be implemented? |
|
Definition
- 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
|
|
|
Term
| What are the principles of type checking? |
|
Definition
- 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
|
|
|
Term
| How can type checking be achieved? |
|
Definition
- 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
|
|
|
Term
| How can type checking function calls be achieved? |
|
Definition
- 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)
|
|
|
Term
| What can we do with results of type checking? |
|
Definition
- 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
|
|
|
