symtab.cc

PL/0源码

//////////////////////////////////////////////////////////////////////////////
//
//  symtab.cc - Symbols and the symbol table.
//

#include "plzero.h"
#include "inpbuf.h"
#include "symtab.h"
#include "codegen.h"
#include <iostream>
#include <iomanip>

////////
//  input_symbol and output_symbol are globally visible.  They represent the
//  PL/0 pseudo-variables "INPUT" and "OUTPUT".  They belong to the
//  predefined_scope because the are linked in and don't actually exist in the
//  PL/0 source code.  If seperate compilation were someday included in PL/0,
//  the predefined_scope could be used for all external variables.
//
//  global_scope is used for all identifiers defined in the outermost scope of
//  a PL/0 program.
//
se_variable_t   *   input_symbol;
se_variable_t   *   output_symbol;
scope_number_t          predefined_scope;
scope_number_t          global_scope;

////////
//  Local Variables and Constants
//
#define HASH_TABLE_SIZE         3001    // must be a prime number
#define MAX_OPEN_SCOPES     30

static symbol_entry_t * sym_hash_table[1 + HASH_TABLE_SIZE];

static struct {
    symbol_entry_t *    head;
    symbol_entry_t *    tail;
}                       scope_headers[MAX_SCOPES + 1];
//  All symbol_entry_t's for scope "s" are on a linked list starting
//  with scope_headers[s].head and ending with scope_headers[s].tail.
//  They're on the list in the order in which they were declared.

static int              scope_stack_top = 0;  // last used entry
static scope_number_t   scope_stack[MAX_OPEN_SCOPES + 1];
static scope_number_t   next_scope_number = 0;
//  next_scope_number is the first one that hasn't been used

//////////////////////////////////////////////////////////////////////////////
//
//  master hash table for pl0 symbol table
//
//  Uses closed chaining, with addative reprobing (depends on prime
//      size of table).
//
//  Keys are (string_number_t, scope_number_t) pairs
//
//  This code bears a strong resemblance to the hash table code in
//      scanner.cc; the two could probably be combined.
//

////////
//  Look in hash table for given symbol in given scope.  If "entry" is NULL
//  then we are just trying to recall a previous table entry.  If "entry" is
//  not NULL then we are trying to add the new entry to the table.
//  If "entry" is NULL, return symbol table pointer if found else NULL.
//  If "entry" is not NULL, return NULL if found, else return "entry" after
//  inserting it into the table.
//
symbol_entry_t * search_hash_table(scope_number_t scope_num,
                                   string_number_t symbol,
                                   symbol_entry_t *entry)
{
    int hash_value = 1 + ((scope_num * symbol) % HASH_TABLE_SIZE);
    int bucket = hash_value;

    for (;;) {
        if (sym_hash_table[bucket] == NULL) {
            //  We've found where the symbol should be and it's table entry is
            //  empty.
            if (entry) {
                sym_hash_table[bucket] = entry;
                if (scope_headers[scope_num].tail == NULL) {
                    scope_headers[scope_num].tail = sym_hash_table[bucket];
                    scope_headers[scope_num].head = sym_hash_table[bucket];
                }
                else {
                    scope_headers[scope_num].tail->next_in_scope
                        = sym_hash_table[bucket];
                    scope_headers[scope_num].tail = sym_hash_table[bucket];
                }
                return sym_hash_table[bucket];
            }
            break;
        }
        else if (sym_hash_table[bucket]->name == symbol
                 && sym_hash_table[bucket]->scope == scope_num) {
            //  We've found the symbol in the table.
            if (!entry)
                return sym_hash_table[bucket];
            break;
        }
    else {
            // We have a collision and must re-hash.
            bucket = (bucket + hash_value) % HASH_TABLE_SIZE + 1;
            if (bucket == hash_value)
                die_compiler("Out of room in symbol hash table.");
        }
    }
    return NULL;
}

////////
//  Create predefined_scope and its contents (i.e "INPUT" and "OUTPUT").
//  To finish initialization we open global_scope.
//
void init_symbol_table(void)
{
    location_t          dummy_loc;

    predefined_scope = new_scope();
    open_scope(predefined_scope);

    dummy_loc.line = NULL;      // "INPUT" and "OUTPUT" aren't in this file so
    dummy_loc.column = 1;       //  we give them a dummy location.

    input_symbol = new se_variable_t(predefined_scope,
                                     define_ident(INPUT_NAME), dummy_loc);
    output_symbol = new se_variable_t(predefined_scope,
                                      define_ident(OUTPUT_NAME), dummy_loc);

    global_scope = new_scope();
    open_scope (global_scope);
}

////////
//  Create a new scope and return its scope number.
//
scope_number_t new_scope(void)
{
    scope_headers[next_scope_number].head = NULL;  // nothing in it yet
    scope_headers[next_scope_number].tail = NULL;
    return next_scope_number++;
}

////////
//  Open a scope by pushing it onto the scope_stack.
//
void open_scope(scope_number_t scope)
{
    if (scope_stack_top >= MAX_OPEN_SCOPES)
        die_compiler ("Too many open scopes.");
    scope_stack_top = scope_stack_top + 1;
    scope_stack[scope_stack_top] = scope;
}

////////
//  Close a scope by popping one entry off the scope_stack.
//
void close_scope(void)
{
    assert(scope_stack_top > predefined_scope);
        // forbid underflow of scope stack
    scope_stack_top = scope_stack_top - 1;
}

////////
//  Determine how many levels deep from the current scope the specified
//  scope lies -- i.e. how many times one should dereference the static
//  chain to find variables in that scope.
//  Die if specified scope is not open.
//
int scope_depth(scope_number_t scope)
{
    int  i;

    for (i = scope_stack_top; scope_stack[i] > scope; i--) {
        if (i == 0) {
            die_compiler("Scope not found on stack.");
    }
    }
    return scope_stack_top - i;
}

////////
//  Look symbol up in the symbol table, obeying PL/0 scope rules,
//  and return a pointer to its symbol table record;
//  return NULL if not found.
//
symbol_entry_t * symbol_look_up(string_number_t symbol)
{
    for (int i = scope_stack_top; i >= 0; i--) {
        if (symbol_entry_t *rtn = search_hash_table(scope_stack[i],
                                                    symbol, NULL))
            return rtn;
    }
    return NULL;
}

////////
//  Return a pointer to the first symbol entry in the list of symbols for
//  the given scope.  Subsequent symbols can be found by using the
//  symbol_entry_t member function "next()".
//
symbol_entry_t * first_in_scope(scope_number_t scope)
{
    return scope_headers[scope].head;
}

////////
//  Return number of last scope used in program.
//
scope_number_t last_scope(void)
{
    return next_scope_number - 1;
}

////////
//  Dump the complete symbol table to stdout (for debugging) by stepping
//  through the scopes calling first_in_scope for each scope and then stepping
//  through the symbol_entry_t's for the scope.  We dump each symbol_entry_t
//  by calling its member function dump_object_data, thus each subclass of
//  symbol_entry_t can have its own unique dump function.
//  Wow, isn't object-orientation cool?!
//
void dump_symbol_table (void)
{
    for (scope_number_t s = predefined_scope; s <= last_scope(); s++) {
        cout << "scope " << s << ":\n";
        for (symbol_entry_t *p = first_in_scope(s); p != NULL; p = p->next()) {
            cout << "  " << hex << setfill('0') << setw(8)
                << (unsigned int)p << ":" << setfill(' ') << dec;
            p->dump_object_data();
        }
    }
}

//////////////////////////////////////////////////////////////////////////////
//
//  Symbol Table Entry Classes
//
//  symbol_entry_t is the root class for a entries in the symbol table.  It
//  defines a number of common member varaibles and functions.  There should
//  never actually be a member of symbol_entry_t allocated, but instead all
//  symbols should be members of its subclasses.  In other words,
//  symbol_entry_t is an abstract type and its subclasses are concrete types.
//  Currently PL/0 supports the following subclasses of symbol_entry_t:
//      se_constant_t: PL/0 constants (always integer constants)
//      se_variable_t: PL/0 variables (always integers)
//      se_procedure_t: PL/0 procedures.
//
//  Some possible future extensions to PL/0 might be adding string constants.
//  This could easily be done by creating two new subclasses of se_constant_t,
//  one for integers and another for strings.  Another extension might be to
//  added integer arrays.  These could probably be added by subclassing
//  se_variable_t by turning it into a abstract type.
//

////////
//  symbol_entry_t : super class from which all other symbols are created.
//  Create a symbol_entry_t with the given scope, symbol_name and location of
//  its declaration in the source program.  Other member varaibles are assigned
//  reasonable default values.  Also adds it to the symbol table if there are
//  no name conflicts.
//
symbol_entry_t::symbol_entry_t(scope_number_t in_scope,
                               string_number_t symbol_name,
                               location_t loc)
{
    name = symbol_name;
    scope = in_scope;
    declaration = loc;
    used = false;
    next_in_scope = NULL;
    code_gen_info = NULL;

    if (!search_hash_table(scope, name, this))
        issue_error(loc, "Identifier already declared in this scope.");
}

////////
//  Return a pointer to the symbol_entry_t's code generation information
//  record.  symbol_code_t is defined in codegen.[h,cc].
//
const symbol_code_t *symbol_entry_t::get_code_gen_info(void)
{
    return code_gen_info;
}

////////
//  Return the symbol's name.
//
string_number_t symbol_entry_t::get_name(void) const
{
    return name;
}

////////
//  Return the symbol's scope.  All symbols belong to the scope in which they
//  were declared.
//
scope_number_t symbol_entry_t::get_scope(void) const
{
    return scope;
}

////////