Question

a) Arrays as data structures are considered to have better performance in comparison to symbol tables. In the lecture, you might have noticed an example of a symbol table defined for keys of type Integer (e.g. , ). Provide an example that justifies the use of the symbol table that utilizes Integer as a key over an array. Explain your choice.\

b)One of many potential use cases for symbol tables discussed in the lecture is its implementation for a compiler, where one of the features a symbol table can be used for is value propagation. Describe the role of a symbol table in value propagation process that takes place within a compiler and provide an example of a scenario where value propagation might not result in performance improvement.

Populate a symbol table using the textbook's symbol table API.

(c) Use the table below to determine the proper operations to create and fill a symbol table with courses that Professor Ruben will be teaching for Spring of 2019.

COURSE	SEATS OCCUPIED
SER222	47
SER315	63
SER334	38
SER401	40
SER415	42

(d) Before the beginning of the semester starts SER222 is canceled and will need to be removed from the symbol table. The number of occupied seats for SER401 have increased from 40 to 60students and the number of occupied seats for SER315 have decreased from 63 to 58. Provide the code that would update your data symbol table with the provided scenario. Also provide the code that will print out all the keys located in the updated symbol table.

e) reasoning behind this? Also provide an scenario for which the value of null might be useful in your symbol table?

Answer 1

a.answer:

Symbol Tables

The main operations of a symbol table are put, get, delete, contains & isEmpty.

The put operation inserts a key-value pair into the table (remove key from table if value is null), get returns a value given it’s key (null if not exist), delete or removes key and it’s value from table, and contains checks if there’s a value paired with a given key.

Symbol Table Conventions

There are several choices we’ve made for our implementations to make our code consistent, and useful.

— Generics

Key and Value type is any generic type.

— Duplicate Keys

Only one value is associated with each key (no duplicate keys in a table).

This convention is directly tied to put operation; overrides the old value with the new value if the that key already exists in the table.

— Null Values

No key can be associated with the value null.

This convention is directly tied to get operation; returns null for keys not in the table. The (intended) consequences of not having null values are:

1. We can check if a key exists or not by testing whether get returns null.
2. We can implement lazy version of delete by calling put passing null as the value.

— Deletion

Deletion in symbol tables generally involves either one of two strategies: lazydeletion, where we associate keys in the table with null (as we’ve just said), then perhaps remove all such keys later, and eager deletion, where we remove the key from the table immediately.

— Iterators

We can iterate over keys in the table. This can be done by defining a method for example called keys(), which returns an Iterable object.

b. answer:Symbol Table in Compiler

Prerequisite – Phases of a Compiler

Symbol Table is an important data structure created and maintained by the compiler in order to keep track of semantics of variable i.e. it stores information about scope and binding information about names, information about instances of various entities such as variable and function names, classes, objects, etc.

• It is built in lexical and syntax analysis phases.
• The information is collected by the analysis phases of compiler and is used by synthesis phases of compiler to generate code.
• It is used by compiler to achieve compile time efficiency.
• It is used by various phases of compiler as follows :-
  1. Lexical Analysis: Creates new table entries in the table, example like entries about token.
  2. Syntax Analysis: Adds information regarding attribute type, scope, dimension, line of reference, use, etc in the table.
  3. Semantic Analysis: Uses available information in the table to check for semantics i.e. to verify that expressions and assignments are semantically correct(type checking) and update it accordingly.
  4. Intermediate Code generation: Refers symbol table for knowing how much and what type of run-time is allocated and table helps in adding temporary variable information.
  5. Code Optimization: Uses information present in symbol table for machine dependent optimization.
  6. Target Code generation: Generates code by using address information of identifier present in the table.

Symbol Table entries – Each entry in symbol table is associated with attributes that support compiler in different phases.
Items stored in Symbol table:

• Variable names and constants
• Procedure and function names
• Literal constants and strings
• Compiler generated temporaries
• Labels in source languages

Information used by compiler from Symbol table:

• Data type and name
• Declaring procedures
• Offset in storage
• If structure or record then, pointer to structure table.
• For parameters, whether parameter passing by value or by reference
• Number and type of arguments passed to function
• Base Address

Operations of Symbol table – The basic operations defined on a symbol table include: