data structure of symbol table.pptx

Useful for study

1. NADAR SARAWATHI COLLEGE OF ARTS AND SCIENCE,THENI. DEPARTMENT OF COMPUTER SCIENCE DATA STRUCTURE OF SYMBOL TABLE BY: B.POORANI I-MSC(CS)

2. Symbol tables A data structure used by a compiler to keep track of semantic of names. Determine whether the variable is defined already or not. Determine the scope Search : access the information associated with given name. Insert: add a name into the table. Delete : remove a name when its scope is closed.

3. Block structured languages Two basic operation : set and reset The set operation is invoked when the beginning of a block is recognized during compilation. The reset operation ,is applied when the end of a block is encountered.

4. Four structure Unordered symbol table Ordered symbol table Tree structured symbol table Hash symbol table

5. Unordered list: For a very small set of variable. Coding is easy , but performance is bad for large number of variables. Ordered linear list: Use binary search on arrays, Insertion and deletion are expensive. Coding is relatively easy.

6. Binary search tree: O(log n) time per operation (search ,insert or delete)for n variables. Coding is relatively different. Hash table: Most commonly used. Very efficient provided the memory space is adequately larger than the number of variable. Coding is not too difficult.

7. Content in a symbol table Possible entries in a symbol table: Name : a string Attribute: Reserved word Variable name Type name Procedure name Constant name

8. Thank you