Class: Aurum::Builder::DigraphTraverser

Inherits:
Object
  • Object
show all
Defined in:
lib/aurum/grammar/builder/parsing_table_builder.rb

Instance Method Summary collapse

Constructor Details

#initialize(&condition) ⇒ DigraphTraverser

Returns a new instance of DigraphTraverser.



147
148
149
150
 
# File 'lib/aurum/grammar/builder/parsing_table_builder.rb', line 147

def initialize &condition
  @indicitor, @result, @stack = {}, {}, []
  @condition = condition
end

Instance Method Details

#traverse(node) ⇒ Object 



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/aurum/grammar/builder/parsing_table_builder.rb', line 152

def traverse node
  return @result[node] if @indicitor[node]
  to_be_continued, @result[node], @indicitor[node] = @condition.call(node)
  if to_be_continued
    @stack.push(node)
    @indicitor[node] = (cycle_indicitor = @stack.length)
    @result[node] = node.map_to_set
    node.result_each do |new_node|
      traverse(new_node) unless @indicitor[new_node]
      @indicitor[node] = [@indicitor[node], @indicitor[new_node]].min
      @result[node] |= @result[new_node]
    end
    node_in_cycle = nil
    until node_in_cycle == node
      node_in_cycle = @stack.pop
      @result[node_in_cycle] = @result[node].dup
      @indicitor[node_in_cycle] = 65535
    end if @indicitor[node] == cycle_indicitor
  end
  @result[node]
end