Step 3: Symbol Table Generation - Due: Friday, September 29th, 11:59pm

Introduction

Your goal in this step is to process variable declarations and create Symbol Tables. A symbol table is a data structure that keeps information about non-keyword symbols that appear in source programs. Variables and String Variables are examples of such symbols. Other example of symbols kept by the symbol table are the names of functions or procedures. The symbols added to the symbol table will be used in many of the further phases of the compilation. The diagram below shows the progress in our compiler construction at the end of this step:

symbol table

The Task: The Compiler's Symbol Table

In Step 2 you didn't need token values since only token types are used by parser generator tools to guide parsing. But in this step your parser needs to get token values such as identifier names and string literals from your scanner. You also need to add semantic actions to create symbol table entries and add those to the symbol table.

In the LITTLE programming language, there are multiple scopes where variables can be declared:

Your task in this step of the project is to construct symbol tables for each scope in your program. For each scope, construct a symbol table, then add entries to that symbol table as you see declarations. The declarations you have to handle are integer/float declarations, which should record the name and type of the variable, and string declarations, which should additionally record the value of the string. Note that typically function declarations/definitions would result in entries in the symbol table, too, but you do not have to record them for this step.

Nested symbol tables

Note that the scopes in the program are nested (function scopes are inside global scopes, and block scopes are nested inside function scopes, or each other). You will have to keep track of this nesting so that when a piece of code uses a variable named "x" you know which scope that variable is from.

Handling errors

Your compiler should output the string "DECLARATION ERROR <var_name>" if there are two declarations with the same name in the same scope.

Output format

For each symbol table in your program, use the following format:

 
  Symbol table <scope_name>
  name <var_name> type <type_name>
  name <var_name> type <type_name> value <string_value>
  ...

The global scope should be named "GLOBAL", function scopes should be given the same name as the function name, and block scopes should be called "BLOCK X" where X is a counter that increments every time you see a new block scope. Function parameters should be included as part of the function scope.

The order of declarations matters! We expect the entries in your symbol table to appear in the same order that they appear in the original program. Keep this in mind as you design the data structures to store your symbol tables.

Test cases and outputs

Submitting your project

First, make sure that your directory structure is correct and you are submitting only the required files. Then, follow the instructions about the turnin command and note that the step name for this step is step3 (use -p step3). Also, if you are working in a pair, submit from the same login (also called your group account) every time.

References