Symbol Table Management Questions and Answers

Answer: A

Correct answer: a store of the names in a program together with their attributes

The symbol table is the compiler’s record of what every name means: its type, its scope, its storage, its parameters if it is a procedure. Nearly every phase consults it, which is why it is a data structure shared across the whole compiler rather than belonging to any one pass.

Answer: B

Correct answer: the number of times the name appears in the source text

A count of occurrences serves no purpose in translation and is not kept. The attributes recorded are those the later phases need - type for checking, scope for resolution, storage location for code generation - and each earns its place by being consulted.

Answer: C

Correct answer: the scanner, at the moment the identifier is first recognised

The scanner recognises the identifier and enters it in the table, returning a pointer to the entry as part of the token. Later phases fill in the attributes as they become known: the parser and semantic analyser supply type and scope, and the code generator the storage.

Answer: D

Each phase touches the table for its own purpose, writing what it knows and reading what an earlier phase recorded. Because the one structure is shared across the whole compiler, its design has to satisfy every one of those needs at once rather than being tuned for any single phase.

Answer: A

A tree keeps its keys ordered, which a hash table does not. Compilers do not need ordered traversal, so the faster average lookup of a hash table is bought at no real cost, and only a cross reference tool would miss the ordering.

Answer: B

Every entry may have to be examined. The simplicity is attractive for a very small table, but the cost becomes unacceptable once a program declares more than a handful of names. Real programs declare thousands, so the structure is of historical interest only.

Answer: C

Correct answer: logarithmic in the number of entries

A balanced tree halves the search space at each step, giving \( O(\log n) \) lookup, and it keeps the entries in order - useful for producing a sorted listing. A hash table is faster still, at constant average cost, but loses the ordering.

Answer: D

The comparison is what drives the choice in practice. A hash table wins on average but degenerates to a list in the pathological case, which is why the hash function matters. A well chosen function makes that case vanishingly unlikely in practice.

Answer: A

Distinct names sharing a bucket is unavoidable once the number of possible names exceeds the number of buckets. Chaining and open addressing are the two standard responses. The pigeonhole principle makes collisions unavoidable in any real table.

Answer: B

Each bucket holds a pointer to a list of the entries that hashed there. Lookup hashes once and then walks a short list, which stays cheap provided the load factor is kept modest. Unlike open addressing, chaining continues to work when the table is overfull.