1 of 40

COMP 520: Compilers!

Lecture 9: Identification

2 of 40

Announcements + Logistics

Keep chugging on PA2!
PA3 - Contextual Analysis

Identification - Today!
Type Checking - Tomorrow!

3 of 40

Identification

4 of 40

What is identification?

Resolution of….

Identifiers and what they denote
scopes!

5 of 40

Three scopes in miniJava

Class Names
Member Names (fields and methods)
Parameters / Local variables

6 of 40

Defining context in miniJava

Give each a “level” and create some rules
Level 0: Class Names
Level 1: Member Names
Level 2+: Method Parameters & Local Variables

How does this work in Java?

7 of 40

A perfectly legal Java program

8 of 40

Defining context in miniJava

Give each a “level” and create some rules
Level 0: Class Names
Level 1: Member Names
Level 2+: Method Parameters & Local Variables

Anything in the 2+ category cannot override anything else in 2+. Other than that, higher scope levels can override lower scope levels.

9 of 40

Identifiers

An identifier has a name (string) and a context �
An identifier can be…

10 of 40

Identifiers

11 of 40

Contextual analysis: Identification

Identifiers are

defined (introduced) typically through declarations, sometimes “pre-defined”
referenced (used) through occurrences other than in a declaration. We generally call these “references”

Identification

record definitions of identifiers and their attributes when declared
attributes describe the category and specific details of a declaration

relate each reference to the appropriate attributes

12 of 40

Identifiers make sense in context

Identifier x Context → Declaration
When no given context, context is the current class

13 of 40

Forward declarations?

Note: B is defined after A
Java is doing something special that is not “in-order.”

You will have to tackle this problem too!

14 of 40

Where is a.b.c.x’s declaration?

Which contexts are the different components bound to?

15 of 40

Where is a.b.c.x’s declaration?

x is in the context of c
c is in the context of b
b is in the context of a
a was declared as an “A” object

16 of 40

What about types…

x is in the context of c
c is in the context of b
b is in the context of a
a was declared as an “A” object

a: a is of type “A”

a.b: b in context of “A”, type is “B”

a.b.c: c in context of “B”, type is “C”

a.b.c.x: x in context of “C”

17 of 40

Identification Theory

As identifiers are declared (ClassDecl, VarDecl, etc.)… keep a table of their context. �
IDTable: (id × ctx) → Declaration
Input is (id,ctx), output is Declaration �(Note: if (a,b) ∉ IDTableInputs, then id error)
But what exactly is a context?

18 of 40

Context Visibility

The context of an identifier is the class it is defined in.
Not all entries are available at all times.
When resolving a.b.c, the entry:

{“ID c”} x {“CTX B”} → FieldDecl

is unavailable when inside C.fun

19 of 40

Context Invisibility

Some languages let you manually specify context.
Shown on the right is C++. �
Can use language’s syntax to bypass hidden contexts (in this case, local variable hides field variable)

20 of 40

Scoped Identification

Your ID Table can be seen as a stack. �
When a new scope occurs (with a block statement{…}) then you get a new ID table pushed on the stack.
Other than for QualRef, check the top-most ID table, and work your way down to find the Declaration

21 of 40

How to determine the definition that applies to a reference?

Context

Java class names can only appear in some places (where?)
variable, function and procedure names can appear in other places

Qualified access

prefix determines applicable definitions
e.g. System.out.println(…)

visibility rules

a subset of definitions is visible at a given program point

scope rules: local variables, parameters, members, classnames
inheritance of class or interface(s)
qualified references
accessibility: public / private / protected

type rules

overloading: foo(5), foo(“string”)

22 of 40

Implementation: Identification

Identification table (a.k.a. symbol table)

maps identifier names to attributes
attributes vary greatly depending on the category of identifier

strategy: the attributes of an identifier are in the AST node where it is declared

all declaration nodes in miniJava AST are subtype of Declaration (Decl)

23 of 40

Identification Table Implementation Details

(auto-expanding) hashtable

O(n) amortized access cost for O(n) insertions and lookups

Java: class HashMap<String, Decl>

clear()
boolean containsKey( String id )
Decl put( String id , Decl decl ) // associate id with decl
Decl get( String id ) // decl or null, if id not in hashmap
void remove( String id ) // remove current association of id, if any

24 of 40

Scoped Identification Table

Extends hashtable with two operations

openScope()
closeScope()
Get(id.spelling()) returns innermost declaration �

Implementation challenges

remove mappings when leaving scope
handling multiple declarations

Question: When should you open/close a scope?

25 of 40

Parameters to the identification process

Class declarations

to identify uses of class names�e.g. Foo x = … new Foo()

Member declarations in current class

to identify uses of fields or methods

Local declarations in current method

to identify uses of parameters or local variables

Member declarations in other classes

to identify qualified references, �e.g. Foo.field x.y.z

26 of 40

Identification Traversal

At each node, we can update the ID table.
Updates can be to a global ID table, or you can return an updated table while traversing.

27 of 40

Example

28 of 40

Example

29 of 40

Identification Traversal – Method Body

What should happen when you encounter a VarDeclStmt in a Method Body?

30 of 40

Identification Traversal – Method Body

What should happen when you encounter a VarDeclStmt in a Method Body?

visit the VarDecl and add that identifier to the top-most IDTable in your Scoped Id Table!�

If that identifier already exists at scope level 2+, then that is an identification error!

31 of 40