Symbol Table Design and Implementation in Ruby
-
19-04-2021 - |
Frage
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
Lösung
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
Andere Tipps
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
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.