Implementation Of Symbol Table

Diesel:

● Diesel is a programming language that is designed for high-performance applications such as games and simulations.

● It is a statically-typed language that is similar in syntax to Rust, and it aims to provide a simpler and more efficient alternative to C++.

● Diesel is also the name of a popular Object-Relational Mapping (ORM) library for Rust.

● An ORM is a tool that allows developers to interact with a database using an object-oriented programming interface, rather than writing SQL directly.

Implementation:

The symbol table in Diesel is implemented using four different tables:

1. Hashtable:

The hashtable is a data structure that maps symbols to their corresponding entries in the symbol table. It uses a hash function to generate an index into the table, making it a fast way to look up symbols.

2. Symbol Table (parameter-index to string table, hash link):

The symbol table contains the actual symbol definitions, including their names, types, and other attributes. Each symbol is represented as an entry in the table, with a unique index that is used to reference it. This table is implemented as a combination of a parameter-index to string table and a hash link.

3. Block Table:

The block table is used to keep track of the different blocks of code in a program. It is used to ensure that symbols are only visible within their respective blocks and are not visible outside of their scope. Each entry in the block table corresponds to a single block of code.

4. String Table:

The string table is used to store strings used in the program. It is used to avoid duplicating strings in memory, reducing the overall memory usage of the program. Each entry in the string table corresponds to a single string. When a new symbol is added to the symbol table, its name is first added to the string table, and a new entry is created in the symbol table. The entry contains information about the symbol, such as its type and scope.

A new entry is also created in the hashtable, which maps the symbol’s name to its entry in the symbol table. Overall, these four tables work together to form the structure of the symbol table in Diesel, allowing for efficient and type-safe code generation for interacting with databases.

Implementation Steps of Symbol Table

Step 1: Empty Symbol Table

The symbol table is initially empty and contains no symbols.

Step 2: Installing REAL into the Symbol Table

The “real” is likely a type representing real numbers in the programming language. The symbol “real” is inserted into the symbol table and assigned a position in the string table, which holds the actual string names of the symbols. Since the hash table is initially empty, the hash link for the symbol is set to NULL_SYM. The index to the symbol is saved in the hash table, and the sym_pos variable is increased by one.

Step 3: Installing WRITE into the Symbol Table

The symbol “write” is inserted into the symbol table in the same way as “real”, with its position in the string table being stored in the symbol’s pool_pos value. The index to the symbol is saved in the hash table, and the sym_pos variable is increased by one.

Step 4: Installing READ into the Symbol Table and Linking Back to REAL

The symbol “read” is inserted into the symbol table and happens to have the same hash value as “real”. A hash table collision occurs, so the symbol is inserted and assigned an id equal to the pool_pos value of “read”. The index to the symbol is saved in the hash table, and the previous index that pointed to “real” is removed. The hash link of the installed symbol is set to point to “real”, and the sym_pos variable is increased.

Step 5: Installing PROG and Entering a New Lexical Level

The identifier “prog” is installed into the symbol table as a procedure, and the lexical level is increased to 1. The block table is updated so that its first element points to the last object inserted, which is the procedure “prog”.

Step 6: Installing Variables A, B, and C

This diagram shows the fifth step in building a symbol table: installing variables “a”, “b”, and “c”. The variables are installed in the same manner as “read”, with hash collisions occurring and the hash links being updated to point to the previous symbols.

Step 7:

The symbol “a” is added to the symbol table. Since this is the first time this symbol is encountered, a new entry is created with a unique identifier and the symbol’s attributes are stored, including its type and scope.

Step 8:

The symbol “b” is added to the symbol table. A new entry is created for this symbol, similar to step 6.

Step 9:

The symbol “c” is added to the symbol table. Again, a new entry is created for this symbol.

Step 10:

The symbol table is printed, showing all the symbols that have been added so far. This is useful for debugging and ensuring that all the symbols are being properly added to the symbol table.

Step 11:

This diagram shows the final state of the symbol table after all symbols have been installed. It shows the updated information for “a”. Since “b” and “c” have not been redefined, their entries in the symbol table remain unchanged.

References:

1. “Compiler Design: Symbol Table” by Tutorials Point https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm
2. “Symbol Tables” by Stanford University https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/07/Slides07.pdf
3. “Symbol Tables” by Khan Academy https://www.khanacademy.org/computing/computer-science/algorithms/hash-tables/v/symbol-tables
4. “Data Structures for Symbol Tables” by GeeksforGeeks https://www.geeksforgeeks.org/data-structures-for-symbol-tables/

TY-70

Vedant Jagtap (53)

Tanaya Naik(62)

Khushi Nikumbh(64)

Shraddha Shaha(73)