CSCE 434 Lecture 26

« previous | Wednesday, October 23, 2013 | next »

Lecture Slides

Exam on Friday over Chapters 1–4

Symbol Tables

Be sure to allocate enough space (better languages take care of this for you)

Operations:

• insert(name,p) — create record for name at level p
• lookup(name) — returns pointer or index
• delete(p) — deletes entry.

Hash Functions

• Ideal uniform distribution
• Avoid collisions as much as possible, but they are inevitable when mapping to a smaller domain.

Dealing with collisions:

• linear rehashing
• quadratic rehashing
• add value of secondary hash

Bucket Hashing

Collisions just added to list at position

Insert at front or at end

Promotion (performance enhancement)

• move item to front on each lookup
• move item up by one position each lookup (proven to work as well as anything else)

Scope Nesting

Levels of Scopes:

• Current scope (innermost scope)
• Open scope (all scopes surrounding the current scope)
• Closed Scope (All other scopes)

Only variables within open scope should be visible for lookup.

New declarations are added to current scope

Closed scope is inaccessible

Use only one table per scope, chain sub-scopes to parent scope

• Stack structure may be used
• lookup(name) will walk up chain of tables until it finds name.
• delete(p) will throw away table for level p

String Storage

Storing identifiers in symbol table entries requires one of:

• variable sized entries
• hard small limit on size
• much wasted space

Solution: store character strings in a string space and refer to them with simple fixed size descriptors

• maintained by symbol table
• temporary entries added (by scanner) at end of string space.

Procedure Abstraction

Lecture Slides

Separate compilation:

• allows us to build large programs
• reasonable compile times
• requires independent procedures

Linkage convention:

• "contract"
• Largely machine dependent
• divides responsibility

Procedures inherit a valid run-time environment and that they restore one for their parents

Linkages happen at run time, but code to make linkage generated at compile time

Essentials

1. on entry, establish p's environment
2. on call, preserve p's environment
3. on exit, destroy p's environment

Procedure Linkages

Each procedure has an activation record or a frame:

1. parameters
2. return value
3. return address
4. access link
5. (current frame pointer)
6. caller frame pointer →
7. locals

This assumes call-by-reference