Class: MiniKraken::Core::SymbolTable

Inherits:
Object
  • Object
show all
Defined in:
lib/mini_kraken/core/symbol_table.rb

Overview

A symbol table is basically a mapping from a name onto an object that holds information associated with that name. It is a data structure that keeps track of variables and their respective scope where they are declared. The key requirements for the symbol are:

  • To perform fast lookup operations: given a name, retrieve the corresponding object.

  • To allow the efficient insertion of names and related information

  • To support the nesting of scopes

  • To handle the entry scope and exit scope events,

  • To cope with variable redefinition in nested scope

The terminology ‘symbol table’ comes from the compiler design community.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(aScope = nil) ⇒ SymbolTable

Build symbol table with given scope as root.

Parameters:

  • aScope (Core::Scope, NilClass) (defaults to: nil) —

    The top-level Scope



32
33
34
35
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 32

def initialize(aScope = nil)
  @name2scopes = {}
  init_root(aScope) # Set default (global) scope
end

Instance Attribute Details

#current_scope ⇒ Scope (readonly)

Returns The current scope.

Returns:

  • (Scope) —

    The current scope.



28
29
30
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 28

def current_scope
  @current_scope
end

#name2scopes ⇒ Hash{String => Array<Scope>} (readonly)

Mapping between a name and the scope(s) where it is defined

Returns:

  • (Hash{String => Array<Scope>}) 


22
23
24
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 22

def name2scopes
  @name2scopes
end

#root ⇒ Scope (readonly)

Returns The top-level scope (= root of the tree of scopes).

Returns:

  • (Scope) —

    The top-level scope (= root of the tree of scopes)



25
26
27
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 25

def root
  @root
end

Instance Method Details

#all_variables ⇒ Object

Return all variables defined in the current .. root chain. Variables are sorted top-down and left-to-right.



113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 113

def all_variables
  vars = []
  skope = current_scope
  while skope
    vars_of_scope = skope.defns.select { |_, item| item.kind_of?(LogVar) }
    vars = vars_of_scope.values.concat(vars)
    skope = skope.parent
  end

  vars
end

#empty? ⇒ Boolean

Returns iff there is no entry in the symbol table

Returns:

  • (Boolean) 


39
40
41
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 39

def empty?
  name2scopes.empty?
end

#enter_scope(aScope) ⇒ Object

Use this method to signal the interpreter that a given scope to be a child of current scope and to be itself the new current scope.

Parameters:



46
47
48
49
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 46

def enter_scope(aScope)
  aScope.parent = current_scope
  @current_scope = aScope
end

#insert(anEntry) ⇒ String

Add an entry with given name to current scope.

Parameters:

Returns:

  • (String) —

    Internal name of the entry



71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 71

def insert(anEntry)
  current_scope.insert(anEntry)
  name = anEntry.name
  if name2scopes.include?(name)
    name2scopes[name] << current_scope
  else
    name2scopes[name] = [current_scope]
  end

  anEntry.i_name
end

#leave_scope ⇒ Object

Raises:

  • (StandardError) 


51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 51

def leave_scope
  # TODO: take dependencies between scopes into account

  current_scope.defns.each_pair do |nm, _item|
    scopes = name2scopes[nm]
    if scopes.size == 1
      name2scopes.delete(nm)
    else
      scopes.pop
      name2scopes[nm] = scopes
    end
  end
  raise StandardError, 'Cannot remove root scope.' if current_scope == root

  @current_scope = current_scope.parent
end

#lookup(aName) ⇒ Core::LogVar

Search for the object with the given name

Parameters:

  • aName (String)

Returns:



86
87
88
89
90
91
92
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 86

def lookup(aName)
  scopes = name2scopes.fetch(aName, nil)
  return nil if scopes.nil?

  sc = scopes.last
  sc.defns[aName]
end

#lookup_i_name(anIName) ⇒ Core::LogVar

Search for the object with the given i_name

Parameters:

  • anIName (String)

Returns:



97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/mini_kraken/core/symbol_table.rb', line 97

def lookup_i_name(anIName)
  found = nil
  scope = current_scope

  begin
    found = scope.defns.values.find { |e| e.i_name == anIName }
    break if found

    scope = scope.parent
  end while scope

  found
end