Class: Kleene::OnlineMatchTracker

Inherits:
Object
  • Object
show all
Defined in:
lib/kleene/online_dfa.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ OnlineMatchTracker

Returns a new instance of OnlineMatchTracker.



262
263
264
 
# File 'lib/kleene/online_dfa.rb', line 262

def initialize
  reset
end

Instance Attribute Details

#candidate_match_start_positions ⇒ Object

The NFA keys in the following two structures are not the original NFAs supplied to the MultiMatchDFA. They are the original NFAs that have been augmented with a dead end error state, so the keys are objects that are the internal state of a MultiMatchDFA



243
244
245
 
# File 'lib/kleene/online_dfa.rb', line 243

def candidate_match_start_positions
  @candidate_match_start_positions
end

#empty_matches ⇒ Object

: Hash(NFA, Array(Int32)) # NFA -> Array(IndexPositionOfEmptyMatch)



255
256
257
 
# File 'lib/kleene/online_dfa.rb', line 255

def empty_matches
  @empty_matches
end

#match_end_positions ⇒ Object

The end positions are indices at which, after handling the character, the DFA was observed to be in a match/accept state;

however, the interpretation is ambiguous, because the accepting state may be as a result of (1) transitioning to an error state that is also marked final/accepting,
OR it may be as a result of transitioning to (2) a non-error final state.
In the case of (1), the match may be an empty match, where after transitioning to an error state, the DFA is in a state that
is equivalent to the error state and start state and final state (e.g. as in an optional or kleene star DFA),
while in the case of (2), the match may be a "normal" match.
The ambiguity is problematic because it isn't clear whether the index position of the match is end inclusive end of a match
or the beginning of an empty match.
This ambiguity is all due to the construction of the composite DFA in the MultiMatchDFA - the dead end error states are epsilon-transitioned
to the composite DFA's start state.



254
255
256
 
# File 'lib/kleene/online_dfa.rb', line 254

def match_end_positions
  @match_end_positions
end

#matches ⇒ Object

The NFA keys in the following structure are the original NFAs supplied to the MultiMatchDFA. This is in contrast to the augmented NFAs that are used as keys in the candidate_match_start_positions and match_end_positions structures, documented above ^^^.



260
261
262
 
# File 'lib/kleene/online_dfa.rb', line 260

def matches
  @matches
end

Instance Method Details

#add_empty_match(nfa_with_dead_end, token_index) ⇒ Object 



302
303
304
305
 
# File 'lib/kleene/online_dfa.rb', line 302

def add_empty_match(nfa_with_dead_end, token_index)
  positions = empty_match_positions(nfa_with_dead_end)
  positions << token_index
end

#add_end_of_match(nfa_with_dead_end, token_index) ⇒ Object

the end positions are inclusive of the index of the last character matched, so empty matches are not accounted for in the match_end_positions array



296
297
298
299
300
 
# File 'lib/kleene/online_dfa.rb', line 296

def add_end_of_match(nfa_with_dead_end, token_index)
  # puts "add_end_of_match(#{nfa.object_id}, #{token_index})"
  positions = end_positions(nfa_with_dead_end)
  positions << token_index
end

#add_match(nfa, match) ⇒ Object 



318
319
320
321
 
# File 'lib/kleene/online_dfa.rb', line 318

def add_match(nfa, match)
  matches = matches_for(nfa)
  matches << match
end

#add_start_of_candidate_match(nfa_with_dead_end, token_index) ⇒ Object 



289
290
291
292
293
 
# File 'lib/kleene/online_dfa.rb', line 289

def add_start_of_candidate_match(nfa_with_dead_end, token_index)
  # puts "add_start_of_candidate_match(#{nfa.object_id}, #{token_index})"
  positions = start_positions(nfa_with_dead_end)
  positions << token_index
end

#empty_match_positions(nfa) ⇒ Object 



281
282
283
 
# File 'lib/kleene/online_dfa.rb', line 281

def empty_match_positions(nfa)
  empty_matches[nfa] ||= Array.new
end

#end_positions(nfa) ⇒ Object 



277
278
279
 
# File 'lib/kleene/online_dfa.rb', line 277

def end_positions(nfa)
  match_end_positions[nfa] ||= Array.new
end

#invert_candidate_match_start_positions ⇒ Object

: Hash(Int32, Array(NFA))



307
308
309
310
311
312
313
314
315
316
 
# File 'lib/kleene/online_dfa.rb', line 307

def invert_candidate_match_start_positions # : Hash(Int32, Array(NFA))
  index_to_nfas = Hash.new
  candidate_match_start_positions.each do |nfa_with_dead_end, indices|
    indices.each do |index|
      nfas = index_to_nfas[index] ||= Array.new
      nfas << nfa_with_dead_end
    end
  end
  index_to_nfas
end

#matches_for(nfa) ⇒ Object 



285
286
287
 
# File 'lib/kleene/online_dfa.rb', line 285

def matches_for(nfa)
  matches[nfa] ||= Array.new
end

#reset ⇒ Object 



266
267
268
269
270
271
 
# File 'lib/kleene/online_dfa.rb', line 266

def reset
  @candidate_match_start_positions = Hash.new
  @match_end_positions = Hash.new
  @empty_matches = Hash.new
  @matches = Hash.new
end

#start_positions(nfa) ⇒ Object 



273
274
275
 
# File 'lib/kleene/online_dfa.rb', line 273

def start_positions(nfa)
  candidate_match_start_positions[nfa] ||= Array.new
end