Class: LexerKit::DFA::DFABuilder

Inherits:
Object
  • Object
show all
Defined in:
lib/lexer_kit/dfa/dfa_builder.rb

Overview

DFABuilder converts NFA to DFA using subset construction, then compresses using byte classes.

Instance Method Summary collapse

Constructor Details

#initialize(nfa) ⇒ DFABuilder

Returns a new instance of DFABuilder.



8
9
10
11
12
13
14
 
# File 'lib/lexer_kit/dfa/dfa_builder.rb', line 8

def initialize(nfa)
  @nfa = nfa
  @dfa_states = {}
  @dfa_transitions = {}
  @dfa_accept = {}
  @state_count = 1
end

Instance Method Details

#build ⇒ IR::DFATable

Build DFA from NFA

Returns:



18
19
20
21
22
 
# File 'lib/lexer_kit/dfa/dfa_builder.rb', line 18

def build
  initial_set = @nfa.epsilon_closure(Set[@nfa.start_state])
  run_subset_construction(initial_set)
  create_dfa_table
end