Class: ActionDispatch::Journey::NFA::TransitionTable

Inherits:
Object
  • Object
show all
Includes:
Dot
Defined in:
lib/action_dispatch/journey/nfa/transition_table.rb

Overview

:nodoc:

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Dot

#to_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

Returns:

  • (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.flat_map(&:keys).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).flat_map { |s| inverted[s][a] }.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.flat_map(&:keys)).uniq
end

#transitions ⇒ Object 



133
134
135
136
137
 
# File 'lib/action_dispatch/journey/nfa/transition_table.rb', line 133

def transitions
  @table.flat_map { |to, hash|
    hash.map { |from, sym| [from, sym, to] }
  }
end