Class: ActionDispatch::Journey::NFA::TransitionTable
- Inherits:
-
Object
- Object
- ActionDispatch::Journey::NFA::TransitionTable
- Includes:
- Dot
- Defined in:
- lib/action_dispatch/journey/nfa/transition_table.rb
Overview
:nodoc:
Instance Attribute Summary collapse
-
#accepting ⇒ Object
Returns the value of attribute accepting.
-
#memos ⇒ Object
readonly
Returns the value of attribute memos.
Instance Method Summary collapse
- #[]=(i, f, s) ⇒ Object
- #accepting?(state) ⇒ Boolean
- #accepting_states ⇒ Object
- #add_memo(idx, memo) ⇒ Object
- #alphabet ⇒ Object
-
#eclosure(t) ⇒ Object
Returns a set of NFA states reachable from some NFA state
s
in sett
on nil-transitions alone. -
#following_states(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol
a
from some states
int
. -
#generalized_table ⇒ Object
Returns a generalized transition graph with reduced states.
-
#initialize ⇒ TransitionTable
constructor
A new instance of TransitionTable.
- #memo(idx) ⇒ Object
- #merge(left, right) ⇒ Object
-
#move(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol
a
from some states
int
. - #states ⇒ Object
- #transitions ⇒ Object
Methods included from Dot
Constructor Details
#initialize ⇒ TransitionTable
Returns a new instance of TransitionTable.
12 13 14 15 16 17 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 12 def initialize @table = Hash.new { |h,f| h[f] = {} } @memos = {} @accepting = nil @inverted = nil end |
Instance Attribute Details
#accepting ⇒ Object
Returns the value of attribute accepting.
9 10 11 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 9 def accepting @accepting end |
#memos ⇒ Object (readonly)
Returns the value of attribute memos.
10 11 12 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 10 def memos @memos end |
Instance Method Details
#[]=(i, f, s) ⇒ Object
35 36 37 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 35 def []=(i, f, s) @table[f][i] = s end |
#accepting?(state) ⇒ Boolean
19 20 21 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 19 def accepting?(state) accepting == state end |
#accepting_states ⇒ Object
23 24 25 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 23 def accepting_states [accepting] end |
#add_memo(idx, memo) ⇒ Object
27 28 29 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 27 def add_memo(idx, memo) @memos[idx] = memo end |
#alphabet ⇒ Object
109 110 111 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 109 def alphabet inverted.values.map(&:keys).flatten.compact.uniq.sort_by { |x| x.to_s } end |
#eclosure(t) ⇒ Object
Returns a set of NFA states reachable from some NFA state s
in set t
on nil-transitions alone.
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 115 def eclosure(t) stack = Array(t) seen = {} children = [] until stack.empty? s = stack.pop next if seen[s] seen[s] = true children << s stack.concat(inverted[s][nil]) end children.uniq end |
#following_states(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol a
from some state s
in t
.
95 96 97 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 95 def following_states(t, a) Array(t).map { |s| inverted[s][a] }.flatten.uniq end |
#generalized_table ⇒ Object
Returns a generalized transition graph with reduced states. The states are reduced like a DFA, but the table must be simulated like an NFA.
Edges of the GTG are regular expressions.
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 52 def generalized_table gt = GTG::TransitionTable.new marked = {} state_id = Hash.new { |h,k| h[k] = h.length } alphabet = self.alphabet stack = [eclosure(0)] until stack.empty? state = stack.pop next if marked[state] || state.empty? marked[state] = true alphabet.each do |alpha| next_state = eclosure(following_states(state, alpha)) next if next_state.empty? gt[state_id[state], state_id[next_state]] = alpha stack << next_state end end final_groups = state_id.keys.find_all { |s| s.sort.last == accepting } final_groups.each do |states| id = state_id[states] gt.add_accepting(id) save = states.find { |s| @memos.key?(s) && eclosure(s).sort.last == accepting } gt.add_memo(id, memo(save)) end gt end |
#memo(idx) ⇒ Object
31 32 33 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 31 def memo(idx) @memos[idx] end |
#merge(left, right) ⇒ Object
39 40 41 42 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 39 def merge(left, right) @memos[right] = @memos.delete(left) @table[right] = @table.delete(left) end |
#move(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol a
from some state s
in t
.
101 102 103 104 105 106 107 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 101 def move(t, a) Array(t).map { |s| inverted[s].keys.compact.find_all { |sym| sym === a }.map { |sym| inverted[s][sym] } }.flatten.uniq end |
#states ⇒ Object
44 45 46 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 44 def states (@table.keys + @table.values.map(&:keys).flatten).uniq end |
#transitions ⇒ Object
133 134 135 136 137 |
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 133 def transitions @table.map { |to, hash| hash.map { |from, sym| [from, sym, to] } }.flatten(1) end |