Symbol Table Design and Implementation in Ruby

Question

I am building a lexical analyzer in Ruby and am about to start gathering and storing symbols in the symbol table. My main question about the design of the symbol and as to whether it should be static table (meaning that all of the data will be held at the class level) or whether it should be on an instance to instance basis.

Option 1: Class level data structure

require 'SymbolTableEntry.rb'

class SymbolTable
  @sym_table = Array.new(500)
  def initialize()
  end

  def SymbolTable.add(element, index)
    @sym_table[index] = element if element.is_a? SymbolTableEntry
  end

  def SymbolTable.to_s
    pp @sym_table
  end
end

With this scheme, the SymbolTable class has a sort of 'static' functionality, meaning that I don't actually create an instance of a SymbolTable, the only object that exists is the class level one.

(Assume that SymbolTableEntry is a valid object even though I don't define it here)

Ex:

irb(main):002:0> require 'SymbolTable.rb'
=> true

irb(main):003:0> ste = SymbolTableEntry.new
=> #<SymbolTableEntry:0x7ef36884>

irb(main):004:0> SymbolTable.add(ste, 10)
=> #<SymbolTableEntry:0x7ef36884>

irb(main):005:0> SymbolTable.to_s
[nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 #<SymbolTableEntry:0x7ef36884>]
=> nil

Option 2: Instance level data structure

require 'rubygems'
require 'backports'
require 'SymbolTableEntry.rb'

class SymbolTable
  def initialize()
    @sym_table = Array.new(10)
  end

  def add(element, index)
    @sym_table[index] = element if element.is_a? SymbolTableEntry
  end

  def to_s
    pp @sym_table
  end
end

With this scheme I would actually need to instantiate an instance of the SymbolTable class in order to add values to the symbol table.

irb(main):001:0> require 'SymbolTable.rb'
=> true

irb(main):002:0> st = SymbolTable.new
=> #<SymbolTable:0x7eeb6c9c @sym_table=[nil, nil, nil, nil, nil, 
                                        nil, nil, nil, nil, nil]>

irb(main):003:0> ste=SymbolTableEntry.new
=> #<SymbolTableEntry:0x7eeb4d5c>

irb(main):004:0> st.add(ste,10)
=> #<SymbolTableEntry:0x7eeb4d5c>

irb(main):007:0> st.to_s
[nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 nil,
 #<SymbolTableEntry:0x7eeb4d5c>]
=> nil

I would love to hear any and all input on which design you would use or prefer to use, as well any comments on the ruby code in general.

Thanks

Answer 1

Prefer instance variables over class variables, if for no other reason than that classes using class variables are a bit more of a pain to unit test.

You can use instance variables and still have one symbol table to rule them all. One way is by assigning your symbol table to a global variable:

$symbol_table = SymbolTable.new

In some languages, classes that use global variables are difficult to test. In Ruby, they're not so bad, since duck typing lets you assign mock objects to global variables before executing the object under test.

Or, you can use the singleton pattern. Ruby comes with a library to make this easy:

require 'singleton'
class SymbolTable
  include Singleton
  ...
end

To retrieve the one-and-only instance of SymbolTable, created it if needed:

SymbolTable.instance

Answer 2

Use instance variables. But not (at least not only) for reasons of test handling. Rather because

• every parse process will produce it's own symbol table, so you may have more than one at a time
• the symbol table is only needed as long as the parse process is under way
• class variables introduce the necessity to do synchronization to achieve thread safety - even though every parse process can live perfectly well with its own set of symbols

Cheers

robert

Answer 3

Just a quick clarification to a couple of the answers given by Robert and Wayne, both of which mention class variables.

The original question doesn't propose to use class variables at all but does ask about using class instance variables. The first choice Hunter presented used the class object itself as the single instance of the symbol table (with state stored in the class instance variables) while the second option used a more typical class/instance framework with the state stored in an instance of the Symbol table.

Ruby's class variables are not the same thing as class instance variables and should generally be avoided.