..

Symbol Table

Notes

Questions

[!question]- 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]- 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]- 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]- What are the things that a compiler should store about a variable?

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

[!question]- 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]- What are the things that a compiler should store about a struct

  • List of fields

[!question]- What are the things that a compile should store about a function

  • Return type
  • Number of args and their types

[!question]- How would you get the functionality of a symbol table using a parse tree Using annotations

[!question]- 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]- 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]- 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]- What is scope? The portion of a program where an identifier is visible

[!question]- What is lexical scope? The textual block a program to which an identifier belongs to

[!question]- Give examples for some lexical scopes

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

[!question]- What are the scopes in a OO language

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

[!question]- What are the two broad ways to implement a symbol table?

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

[!question]- 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]- 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]- 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]- 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]- 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]- What are the various probing techniques in open addressing?

  • Linear
  • Quadratic
  • Double

[!question]- 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]- 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]- 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.