清华大学：《编译原理》课程教学资源_（英文译文）Chapter 6.3 The Symbol Table

COMPILER CONSTRUCTION Principles and practice Kenneth C. louden

COMPILER CONSTRUCTION Principles and Practice Kenneth C. Louden

6. Semantic Analysis PART TWO

6. Semantic Analysis PART TWO

Contents Part One 6. 1 Attributes and Attribute grammars 6.2 Algorithms for Attribute Computation Part two 6.3 The Symbol Table 6.4 Data Types and Type Checking 6.5 A Semantic analyzer for the tiny language

Contents Part One 6.1 Attributes and Attribute Grammars 6.2 Algorithms for Attribute Computation Part Two 6.3 The Symbol Table 6.4 Data Types and Type Checking 6.5 A Semantic Analyzer for the TINY Language

6.3 The Symbol Table

6.3 The Symbol Table

Symbol table: major inherited attribute and major data structure in a compiler Principal operations: Insert: store the information provided by name declarations when processing these declarations Lookup: retrieve the information associated to a name when that name is used in the associated code Delete: remove the information provided by a declaration when that declaration no longer applies · Information stored: Include data type information, information on region of applicability(scope), and information on eventual location in memory

• Symbol table: major inherited attribute and major data structure in a compiler • Principal operations: – Insert: store the information provided by name declarations when processing these declarations – Lookup: retrieve the information associated to a name when that name is used in the associated code. – Delete: remove the information provided by a declaration when that declaration no longer applies. • Information stored: – Include data type information, information on region of applicability (scope), and information on eventual location in memory

6.3.1 The Structure of The Symbol Table

6.3.1 The Structure of The Symbol Table

Typical dictionary data structure Linear list Provide easy and direct implementations of the three basic operations Operation time is linear in the size of the list Good for a compiler implementation in which speed is not a major concern such as a prototype or experimental compiler or an interpreter for a very small program Various search tree structures (binary search trees, AVL trees, B trees) Don,'t provide best case efficiency The delete operation is very complexity Less useful

Typical dictionary data structure • Linear list – Provide easy and direct implementations of the three basic operations; – Operation time is linear in the size of the list; – Good for a compiler implementation in which speed is not a major concern such as a prototype or experimental compiler or an interpreter for a very small program. • Various search tree structures – (binary search trees, AVL trees, B trees) – Don't provide best case efficiency; – The delete operation is very complexity; – Less useful

Hash tables All three operation can be performed in almost constant time Most frequently in practice, best choice Main idea An array of entries(called buckets), indexed by an Integer range a hash function turns the search key into an integer hash value in the index range and the item corresponding to the search key is stored in the bucket at this index The efficiency greatly depends on the design of the hash function Main problem Collision resolution: two keys are mapped to the same index by the hash function

• Hash tables – All three operation can be performed in almost constant time – Most frequently in practice, best choice • Main idea – An array of entries (called buckets), indexed by an integer range – A hash function turns the search key into an integer hash value in the index range – And the item corresponding to the search key is stored in the bucket at this index – The efficiency greatly depends on the design of the hash function • Main problem – Collision resolution: two keys are mapped to the same index by the hash function

The methods to deal with the collision Open addressing Inserting the collided new items in successive buckets Will cause a significant degradation in performance and make delete operation difficult Separate chaining Each bucket is a linear list; collisions are resolved by inserting the new item into the bucket list Perhaps it is the best scheme for compiler construction

The methods to deal with the collision • Open addressing – Inserting the collided new items in successive buckets – Will cause a significant degradation in performance and make delete operation difficult • Separate chaining – Each bucket is a linear list; collisions are resolved by inserting the new item into the bucket list • Perhaps it is the best scheme for compiler construction

6.3.2 Declarations

6.3.2 Declarations