../

Symbol Table

Notes

Questions

Question 1: What is syntax directed translation

SDT is a technique where the translation from source code is done completely by the parser. This is accomplished by adding actions to each parser rule.

Question 2: What is SDD?

Syntax Directed Definition is the parser grammar of a language combined with the actions to be performed as part of SDT

Question 3: How does SDT differs from code generation?

In code generation it is assumed that there is an abstract model of the program’s namespace. SDT builds that model

Question 4: What are the things that a compiler should store about a variable?

  • Name
  • Type
  • Storage class
  • Lexical scope
  • Base address and offset

Question 5: What are the things that a compiler should store about an array?

  • All the things that are stored for a regular variable
  • Number of dimensions
  • Upper bound of each dimension

Question 6: What are the things that a compiler should store about a struct

  • List of fields

Question 7: What are the things that a compile should store about a function

  • Return type
  • Number of args and their types

Question 8: How would you get the functionality of a symbol table using a parse tree

Using annotations

Question 9: What are the pros and cons of using the AST of the parser as a makeshift symbol table?

  • Pros
    • A single data structure for everything
  • Cons
    • A single data structure for everything
    • Every time we want to look up something we have to traverse the tree which is costly

Question 10: We know that traversal of a tree is costly but there is another disadvantage when using AST as a symbol table. It impacts the memory needed significantly. What is that disadvantage?

We will have variable declaration somewhere Every time we reference this variable we need to include the pointer back to the original declaration. This increases memory significantly

Question 11: What are the two problems solved by using a symbol table?

  • Efficient lookup
  • No redundancy. The information about a variable is store only once and there are no extra pointers

Question 12: What is scope?

The portion of a program where an identifier is visible

Question 13: What is lexical scope?

The textual block a program to which an identifier belongs to

Question 14: Give examples for some lexical scopes

  • Local block
  • Method body
  • Class
  • File
  • Module
  • Whole program

Question 15: What are the scopes in a OO language

  • Global Scope
  • Class scope
    • Instance scope
    • Static scope
  • Method scope
  • Local block

Question 16: What are the two broad ways to implement a symbol table?

  • bunch of small tables. one for each scope
  • One central table

Question 17: In the one central table pattern, suppose a variable is redeclared how will we be differentiate this new variable from the old?

The entries to the table are (name, scope) where scope can be like a number

Question 18: What are some ways to implement a lexically scoped symbol table?

  • Stack
  • Sheaf of tables
  • Open hashing
    • With stack
    • w/o stack
  • Open addressing
  • 2-D hash table

Question 19: What are the pros and cons of stack?

  • Pros
    • Memory efficient
  • Cons
    • Can’t look up easily
    • $O(N)$ where N is the size of the symbol table

Question 20: What is the need for a stack in open hashing?

To perform a finalizeScope() we need to traverse the entire symbol table searching for symbols that are in the scope to be deleted. This ay get costly. But if we were to use a stack, due to its LIFO nature, we would only need to traverse the things that are in the scope and no more.

Question 21: What is the difference between open hashing and open-addressing?

In open hashing the collisions are handled using separate chaining In open addressing the collisions are handled using rehashing techniques such as linear probing, quadratic probing etc… There is also another difference. Consider the following scenario

  • Suppose there are two different identifiers x and y
  • $h(x) = h(y) = \mathcal{k}$
  • In open hashing, the re-declarations of x and y will be in the chain connected to $\mathcal{k}$
    • k->(x,3)->(y,2)->(x,1)
  • This is not so clean. But in open addressing, $y$ will be put in a new slot and all of $y$’s entries will be in that slot

Previous Year Questions

  1. Draw the Open hashing with stack data structures with the hash key as h(identifier) = (ASCII code of first letter + ASCII code of last letter) mod 11 and a secondary hash function using linear probing with a probe size 1. (Note: ASCII code of lower case a is 97, b is 98 until z is 122)
procedure main
integer(a, b, c);
begin 
    procedure f1 (a, b);
    begin
        integer a, b;
        call f2 (b, a);
    end;
    procedure f2 (y, z);
        begin integer y, z;
        procedure f3 (m, n);
        begin 
            integer m, n;
        end;
        procedure f4 (m, n);
        begin
            integer m, n;
        end;
        call f3 (c, z);
        call f4 (c, z);
    end;
    call f1 (a, b);
end;

Demo

Misc Questions

Question 22: What are the various probing techniques in open addressing?

  • Linear
  • Quadratic
  • Double

Question 23: In open addressing how does lookup occurs? For inserting we check if the slot is occupied and if it is we probe. But when looking up how will we know when to probe and when not to?

In open addressing the slot contains two things - the key and a pointer to head of the linked list. We will know to probe by seeing the key

Question 24: What is condition on the size of a table that uses open-addressing?

Since each element needs to have its own slot, at any point of time the table should have enough slots for all the keys

Question 25: Why is open addressing better than open hashing when used for symbol table

In open hashing the table size is constant. The collisions are handled by traversing the linked list. In open addressing the table size is dynamic. We can expand the table whenever we want. Though this has some computational cost, notice that it only occurs if the table is full. So by amortization this is essentially O(n) if we used a scheme similar to what we use in dynamic arrays. But in open hashing the traversal happens every time we lookup. Suppose there are 10 x’s and 1 y. They have the same hash. Also assume that the x’s occur after the y. Now there is an expression involving y. We need the information about y. In open hashing the compiler has to go through 10 x’s to find the y. In open addressing it gets y on the first lookup.